Description

Alice想要得到一个长度为n的序列，序列中的数都是不超过m的正整数，而且这n个数的和是p的倍数。Alice还希望

，这n个数中，至少有一个数是质数。Alice想知道，有多少个序列满足她的要求。

Solution

补集转换

用没有质数限制的方案-一个质数都没有的方案

然后这个题是无序的,这样就非常好做了

设 \(f[i][j]\) 表示选 \(i\) 个数,和 \(\mod p=i\) 的方案数

\(f[i+1][(j+k)\mod P]=f[i][j]*g[k]\)

\(g[k]\) 表示 \(\mod P=k\) 的数的个数

矩阵快速幂优化一下即可

#include
    
     using namespace std;const int N=2e7+10,mod=20170408;int n,m,P,prime[N],num=0;bool vis[N];void priwork(){    vis[1]=1;    for(int i=2;i<=m;i++){        if(!vis[i])prime[++num]=i;        for(int j=1;j<=num && i*prime[j]<=m;j++){            vis[i*prime[j]]=1;            if(i%prime[j]==0)break;        }    }}struct mat{    int a[101];    mat(){memset(a,0,sizeof(a));}    void clear(){memset(a,0,sizeof(a));}    mat operator *(const mat &p){        mat ret;        for(int i=0;i
     
      >=1;    }}int main(){  freopen("pp.in","r",stdin);  freopen("pp.out","w",stdout);  cin>>n>>m>>P;  priwork();  mat S,T;  S.a[0]=1;  for(int i=1;i<=m;i++)T.a[i%P]++;  ksm(S,T,n);  int ans=S.a[0];  S.clear();T.clear();S.a[0]=1;  for(int i=1;i<=m;i++)if(vis[i])T.a[i%P]++;  ksm(S,T,n);ans=(ans-S.a[0]+mod)%mod;  printf("%d\n",ans);  return 0;}