給出一個長度為N的數列{a[n]}，1<=a[i]<=M(1<=i<=N)。 現在問題是，對于1到M的每個整數d，有多少個不同的數列b[1], b[2], …, b[N]，滿足： (1)1<=b[i]<=M(1<=i<=N)； (2)gcd(b[1], b[2], …, b[N])=d； (3)恰好有K個位置i使得a[i]<>bi 注：gcd(x1,x2,…,xn)為x1, x2, …, xn的最大公約數。 輸出答案對1,000,000,007取模的值。
我設f[i]表示d=i的答案 用一個g[i]表示所有i|d的d的答案和。 然后莫比烏斯反演一波。 所以我們只需要算g。 可以通過預處理求出不是d的倍數有t個。 那么這個t個一定不和原來相同 剩下n-t個中要有k-t個和原來相同 就是一個組合數咯
#include<cstdio>#include<algorithm>#include<cmath>#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;typedef long long ll;const int maxn=300000+10,mo=1000000007;int mu[maxn],cnt[maxn],b[maxn],PRi[maxn],f[maxn],g[maxn],fac[maxn],inv[maxn],a[maxn];bool bz[maxn];int i,j,k,l,t,n,m,top;int quicksortmi(int x,int y){ if (!y) return 1; int t=quicksortmi(x,y/2); t=(ll)t*t%mo; if (y%2) t=(ll)t*x%mo; return t;}int C(int n,int m){ if (n<m||n<0||m<0) return 0; return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;}int main(){ scanf("%d%d%d",&n,&m,&k); fo(i,1,n){ scanf("%d",&a[i]); b[a[i]]++; } fo(i,1,m) fo(j,1,m/i) cnt[i]+=b[i*j]; fac[0]=1; fo(i,1,n) fac[i]=(ll)fac[i-1]*i%mo; inv[n]=quicksortmi(fac[n],mo-2); fd(i,n-1,0) inv[i]=(ll)inv[i+1]*(i+1)%mo; top=0; mu[1]=1; fo(i,2,m){ if (!bz[i]){ pri[++top]=i; mu[i]=-1; } fo(j,1,top){ if ((ll)i*pri[j]>m) break; bz[i*pri[j]]=1; if (i%pri[j]==0){ mu[i*pri[j]]=0; break; } mu[i*pri[j]]=-mu[i]; } } fo(i,1,m){ t=n-cnt[i]; if (k<t) continue; g[i]=(ll)C(n-t,k-t)*quicksortmi(m/i-1,k-t)%mo*quicksortmi(m/i,t)%mo; } fo(i,1,m){ fo(j,1,m/i) f[i]=(f[i]+g[i*j]*mu[j])%mo; (f[i]+=mo)%=mo; printf("%d%c",f[i],i==m?'/n':' '); }}新聞熱點
疑難解答
