[BZOJ4305]数列的GCD：莫比乌斯反演+组合数学

分析

一开始想的是对恰好\(k\)个位置容斥，结果发现对\(\gcd\)有些无从下手，想了想发现自己又sb了。

考虑对\(\gcd\)进行容斥处理，弱化条件，现在我们要求的是使\(\gcd\)是\(d\)的倍数的方案数，\(k\)个位置的限制可以用组合数算，最后莫比乌斯反演一下就好了。

时间复杂度为调和级数（\(O(n \log n)\)）。

代码

#include <bits/stdc++.h>
#define rin(i,a,b) for(register int i=(a);i<=(b);++i)
#define irin(i,a,b) for(register int i=(a);i>=(b);--i)
#define trav(i,a) for(register int i=head[a];i;i=e[i].nxt)
typedef long long LL;
using std::cin;
using std::cout;
using std::endl;inline int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}const int MAXN=300005;
const LL MOD=1e9+7;int n,m,k,cnt,a[MAXN],b[MAXN];
LL fac[MAXN],invf[MAXN],res[MAXN],ans[MAXN];
LL prm[MAXN],mo[MAXN];
bool vis[MAXN];inline LL qpow(LL x,LL y){
LL ret=1,tt=x%MOD;
while(y){
if(y&1) ret=ret*tt%MOD;
tt=tt*tt%MOD;
y>>=1;
}
return ret;
}inline LL binom(LL n,LL m){
if(n<0||m<0||n<m) return 0;
return fac[n]*invf[n-m]%MOD*invf[m]%MOD;
}void init(){
fac[0]=1;
rin(i,1,n) fac[i]=fac[i-1]*i%MOD;
invf[n]=qpow(fac[n],MOD-2);
irin(i,n-1,0) invf[i]=invf[i+1]*(i+1)%MOD;
mo[1]=1;
rin(i,2,n){
if(!vis[i]) prm[++cnt]=i,mo[i]=-1;
rin(j,1,cnt){
if(i*prm[j]>n) break;
vis[i*prm[j]]=true;
if(i%prm[j]==0){
mo[i*prm[j]]=0;
break;
}
mo[i*prm[j]]=-mo[i];
}
}
}int main(){
n=read(),m=read(),k=read();init();
rin(i,1,n) a[i]=read(),++b[a[i]];
rin(i,1,m){
int cnt=0;
for(register int j=i;j<=m;j+=i) cnt+=b[j];
cnt=n-cnt;
if(cnt>k){res[i]=0;continue;}
res[i]=qpow(m/i,cnt)*binom(n-cnt,k-cnt)%MOD*qpow(m/i-1,k-cnt)%MOD;
}
rin(i,1,m){
for(register int j=i,d=1;j<=m;j+=i,++d) ans[i]=(ans[i]+mo[d]*res[j]%MOD+MOD)%MOD;
}
rin(i,1,m) printf("%lld ",ans[i]);
printf("\n");
return 0;
}