题目大意：
Alice想要得到一个长度为(n)的序列，序列中的数都是不超过(m)的正整数，而且这(n)个数的和是(p)的倍数。
Alice还希望，这(n)个数中，至少有一个数是质数。
Alice想知道，有多少个序列满足她的要求。
对(100\%)的数据，(1leq n leq 10^9,1leq m leq 2 imes 10^7,1leq pleq 100)
直接求不太好求，容斥一下，先求出全部的方案，再除掉没有质数的
全部的方案怎么求？
考虑(dp)，设(f[i][j])表示(i)个数字，其和(mod p)为(j)的方案数，可以得到转移方程(f[i_1+i_2][(j_1+j_2)\%p]=f[i_1][j_1]*f[i_2][j_2])
然后跑一年就出来了
考虑第一维，发现好像挺像个指数的运算
那我们把第一维用快速幂优化掉
当然我们要提前求出(i=1)时的(f[i][j])，这个循环一遍就完了
设(g[i][j])表示(i)个数字，其和(mod p)为(j)的且不含质数方案数，转移方程相同，只是初始的时候质数不贡献答案
然后就好了～
#include<bits/stdc++.h>
using namespace std;
namespace red{
#define int long long
inline int read()
{
int x=0;char ch,f=1;
for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
if(ch=='-') f=0,ch=getchar();
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return f?x:-x;
}
const int N=2e7+10,p=20170408;
int n,m,k;
int f[233],g[233],F[233],G[233],c[233];
signed prime[N>>1],num;
bool vis[N];
inline void work(int *a,int *b,int *d)
{
for(int i=0;i<k;++i)
{
for(int j=0;j<k;++j)
{
(c[i+j]+=a[i]*b[j])%=p;
}
}
for(int i=0;i<k;++i)
{
d[i]=(c[i]+c[i+k])%p;
c[i]=c[i+k]=0;
}
}
inline void main()
{
n=read(),m=read(),k=read();
f[1]=g[1]=F[0]=G[0]=1;
for(int i=2;i<=m;++i)
{
++f[i%k];
if(!vis[i]) prime[++num]=i;
else ++g[i%k];
for(int j=1;j<=num;++j)
{
if(i*prime[j]>m) break;
vis[i*prime[j]]=1;
if(i%prime[j]==0) break;
}
}
while(n)
{
if(n&1) work(F,f,F),work(G,g,G);
work(f,f,f);
work(g,g,g);
n>>=1;
}
printf("%lld
",(F[0]-G[0]+p)%p);
}
}
signed main()
{
red::main();
return 0;
}
等等，我们发现了什么？
看这里
for(int i=0;i<k;++i)
{
for(int j=0;j<k;++j)
{
(c[i+j]+=a[i]*b[j])%=p;
}
}
一个卷积！在这里写个任意模数(ntt)岂不美哉
虽然对于这道题来说是没事找事
代码先鸽子了，毕竟我还不会任意模数(ntt)