BZOJ 4305: 数列的GCD 组合+容斥

#include <bits/stdc++.h>   
#define ll long long  
#define N 300007   
#define mod 1000000007   
#define setIO(s) freopen(s".in","r",stdin) 
using namespace std;    
int a[N],n,m,k;      
int fac[N],inv[N],bu[N],sum[N],ans[N],sum2[N];              
int qpow(int x,int y) 
{
    int tmp=1; 
    for(;y;y>>=1,x=(ll)x*x%mod)   
        if(y&1)  
            tmp=(ll)tmp*x%mod;   
    return tmp;    
}   
int INV(int x) { return qpow(x,mod-2); }    
int C(int x,int y) 
{
    if(y>x||x<0) return 0;   
    return (ll)fac[x]*inv[y]%mod*inv[x-y]%mod;    
}
int main() 
{ 
    // setIO("input");                
    fac[0]=inv[0]=1;    
    for(int i=1;i<N;++i) 
    {
        fac[i]=(ll)fac[i-1]*i%mod;   
        inv[i]=INV(fac[i]);   
    }
    scanf("%d%d%d",&n,&m,&k);  
    int p=n-k;    // p 个位置相同   
    for(int i=1;i<=n;++i)  
        scanf("%d",&a[i]),bu[a[i]]++;      
    for(int i=1;i<=m;++i) 
    {
        for(int j=i;j<=m;j+=i) 
            sum[i]+=bu[j],sum2[i]++;        
    }
    for(int i=m;i>=1;--i) 
    {                 
        if(sum[i]<p) ans[i]=0;  
        else 
        {    
            ans[i]=(ll)C(sum[i],p)*qpow(sum2[i]-1,sum[i]-p)%mod*qpow(sum2[i],n-sum[i])%mod;        
            for(int j=i+i;j<=m;j+=i) ans[i]=(ll)(ans[i]-ans[j]+mod)%mod;   
        }
    }
    for(int i=1;i<=m;++i) printf("%d ",ans[i]);   
    return 0;    
}