国庆集训 DAY1 总结

· · 个人记录

几天的颓废让本就蒻的 zsw 蒻上加蒻，枯了。

前三题

水题而且 2,3 题都写过嘿嘿。

T1：稍作处理然后背包即可，注意细节。

T2：上次出过的题然后我还 A 过，不过这次比较懒写都没写，乐。是道背包题再加上组合数学，不算很难。

T3：洛谷就有，注意图不一定连通。

T4

题意：

给定一个整数 x(1<=x<=1e6)，求满足如下条件的序列的个数：

（1）序列长度为 y（1<=y<=1e6）, 且序列中每个元素为整数

（2）序列中所有的元素相乘恰好等于 x

思路：

笑死考场想歪了，不断在往斯特林数上靠，其实是插板法的题。

显然要质因数分解，不妨考虑 x=p^{c} 时的情况，也就是只有一种质因数。

把序列的元素看成箱子，要在 y 个箱子里放 c 个球，可以不放，显然有 cnt=C_{c+y-1}^{y-1} 种方法。

那么推广到 x=\prod {p_i}^{c_i} 的情况。我们知道每个整数的质因数分解都是唯一的，那可以采用分组处理的思想，由乘法原理有 ans=\prod cnt_i。

最后考虑正负的情况，x\ge0 所以只能存在偶数个负号，因此 s=\sum\limits_{i=0,i\bmod 2=0}^{y}C_y^i。

（聪明的同学都知道，还有 s=2^{y-1}。可以试着用组合推理的方式证明，也可以暴力证明）

然后用逆元求组合数就好了。

T5

题意：

有一条 n(1≤n≤1e5)个节点的链，编号相邻节点有边，每个点一个权值 a(i)(1≤a(i)≤n)。定义 f(l,r) 为删除点权值不在区间 [l,r] 的点以及相应的边之后，剩余的连通块的数目。

求所有的 f(l,r)（其中 1<=l<=r<=n）的和。

思路：

直接给出西格玛的题目一般都有两种做法：

  1. 拆掉一个西格玛，然后寻找相邻元素的递推关系。在这道题里就是：令 s_r=\sum f(l,r)，则答案为 \sum s_r，难点是 s_r 的求法。

  2. 贡献法，即考虑每个元素会被算入贡献多少次。此题的“元素”就是连通块。

回到本题。第一种方法可以快速得到一种 O(n^2) 的做法，然后俺不知道怎么优化。但是 myz 大佬整出来了，我膜拜（不过我没听懂嘿嘿）

那么把注意力聚集在第二种方法上，又能延伸出两种写法。

官方做法：注意到链的特殊性质：连通块数量 = 点数 - 边数，那么分开计算点的贡献和边的贡献即可（难在转化）

ljs 大佬做法：单独考虑每个连通块，发现单次贡献是 1，但是连通块内有多个点，需要去重。发现只让最左或最右的点计算一次贡献即可，这样便能将块的问题转化为点的问题，分类讨论即可。

代码

T4：

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int mod=1e9+7,N=2e6+5;
int t,x,y,jc[N]={1},zf,ans;

inline int qstp(int a,int p){
    int base=a,s=1;
    while(p){
        if(p&1) s=s*base%mod;
        base=base*base%mod;
        p>>=1;
    }
    return s;
}
inline int C(int n,int m){
    return jc[n]*qstp(jc[n-m],mod-2)%mod*qstp(jc[m],mod-2)%mod;
}
signed main(){
    for(int i=1; i<=2e6;i++) jc[i]=jc[i-1]*i%mod;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&x,&y);
        ans=1;
        for(int i=2; i*i<=x;i++){
            int c=0;
            while(x%i==0) ++c,x/=i;
            if(c) ans=(ans*C(c+y-1,y-1))%mod;
        }
        if(x>1) ans=(ans*C(y,y-1))%mod;
        printf("%lld\n",ans*qstp(2,y-1)%mod);
    }
    return 0;
}