我一眼就从这题看出了卷积，引起了我极大的兴趣，做到后面才发现就这么水。 题面
题意：问长为n，每个数字为1~m，至少有一个质数，和为p的倍数的序列有多少个，模1e9+7。n≤1e9，m≤2e7，p≤100。 看到“至少有一个质数”，大概就是容斥之类的东西，可将问题变成（1~m的结果）减去（合数与1的结果）。 设f[i][j]为长为i，模p为j的方案数。g=f[1]，枚举下一位模p的余数，就可以转移了。
f[i][j]=∑k=0pf[i−1][k]∗g[(j−k+p)模p] 大概可以倍增，不用crt+ntt，就搞定了。 #include #include #include #include #include #include #include #include using namespace std; #define mmst(a, b) memset(a, b, sizeof(a)) #define mmcp(a, b) memcpy(a, b, sizeof(b)) typedef long long LL; const int N=20020000,nn=2e7; const LL mo=20170408; int n,m,p; int prime[N],num; LL x[102],y[102],ans[102],by[102]; bool b[N]; void pre() { for(int i=2;i<=nn;i++) { if(!b[i]) prime[++num]=i; for(int j=1;j<=num&&i*prime[j]<=nn;j++) { b[prime[j]*i]=1; if(i%prime[j]==0) break; } } b[1]=1; } void cheng(LL *a,LL *b) { mmst(by,0); for(int i=0;ifor(int j=0;jint x) { mmst(ans,0); ans[0]=1; for(;x;x>>=1,cheng(a,a)) if(x&1) cheng(ans,a); return ans[0]; } int main() { pre(); cin>>n>>m>>p; for(int i=1;i<=m;i++) { x[i%p]++; if(b[i]) y[i%p]++; } cout<<(work(x,n)-work(y,n)+mo)%mo<return 0; }
这里是纱雾的水题专场。