BZOJ 4305 数列的GCD

题目链接：Click here

Solution:

设\(f[i]\)表示当\(d=i\)时的答案，\(c[i]\)表示\(a\)序列中有多少个\(i\)的倍数

首先我们要使恰好\(k\)个数互不相同，则表示其他\(n-k\)个数恰好相同，那么有\({c[i]\choose n-k}\)种方案

考虑剩下的\(c[i]-n+k\)个位\(i\)的倍数的位置，\([1,m]\)中\(i\)的倍数有\(\lfloor {m \over i} \rfloor\)个，但不能相同，所以要减去自己，方案数即\((\lfloor {m \over i} \rfloor-1)^{c[i]-n+k}\)，剩下的位置同理，但不用减去自己，即$\lfloor {m\over i} \rfloor ^{n-c[i]} $

到这里我们发现我们不仅统计了\(i\)自己，还把\(i\)的倍数也算进去了，所以要减掉，则

\[f[i]={c[i] \choose n-k}\times (\lfloor {m \over i} \rfloor -1)^{c[i]-n+k} \times \lfloor {m\over i} \rfloor ^{n-c[i]} - \sum_{j=2}^{\lfloor {m \over i}\rfloor} f[i\times j] \]

于是我们倒着算即可，时间复杂度\(O(n \log n)\)

Code:

#include
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=3e5+11;
int n,m,k,a[N],f[N],c[N],v[N];
int fac[N]={1},ifac[N];
int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}
    return x*f;
}
int qpow(int x,int y){
    int re=1;
    while(y>0){
        if(y&1) re=re*x%mod;
        y>>=1;x=x*x%mod;
    }return re;
}
int C(int x,int y){
    if(x