题目描述

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

Alice还希望，这 $n$n 个数中，至少有一个数是质数。

Alice想知道，有多少个序列满足她的要求。

数据范围

对于 $100 \%$100% 的数据， $1 \le n \le 10^9,1 \le m \le 2 \times 10^7,1 \le p \le 100$1≤n≤109,1≤m≤2×107,1≤p≤100

题解

若没有质数的限制，考虑暴力 $dp$dp ， $f_{i,j}$fi,j​ 表示前 $i$i 个数的和在模 $p$p 下为 $j$j 的方案数

则 $f_{i,j}+=f_{i-1,k} \times cnt_{(j-k+p)\%p}$fi,j​+=fi−1,k​×cnt(j−k+p)%p​，其中 $cnt_{i}$cnti​ 表示模 $p$p 下为 $i$i的数的个数

发现 $p$p 很小，所以可以矩阵快速幂，发现是循环矩阵则可以优化，不用也可以

考虑质数的限制，则发现只要减去没有质数的情况即可，所以 $cnt$cnt 减去质数的个数，再做一遍上述过程即可

效率： $O(m+p^2logn)$O(m+p2logn)

代码

#include <bits/stdc++.h>
using namespace std;
const int N=105,P=20170408,M=2e7+5,Z=2e6+5;
int n,m,p,g[N],t,pr[Z],tp,mo[Z],ans;
bool F[M];struct O{int a[N];}s,f,V;
O C(O A,O B){
	for (int i=0;i<p;i++){
		V.a[i]=0;
		for (int k=0;k<p;k++)
			(V.a[i]+=1ll*A.a[k]*B.a[(i-k+p)%p]%P)%=P;
	}
	return V;
}
void work(){
	for (int j=0;j<p;j++)
		s.a[j]=0,f.a[j]=g[(p-j)%p];
	s.a[0]=1;
	for (int i=n;i;i>>=1,f=C(f,f))
		if (i&1) s=C(s,f);
}
int main(){
	scanf("%d%d%d",&n,&m,&p);g[t=(1%p)]++;
	for (int i=2;i<=m;i++){
		t++;if (t>=p) t-=p;g[t]++;
		if (!F[i]) pr[++tp]=i,mo[tp]=t;
		for (int j=1;j<=tp && pr[j]*i<=m;j++){
			F[i*pr[j]]=1;
			if (i%pr[j]==0) break;
		}
	}
	work();ans=s.a[0];
	for (int i=1;i<=tp;i++) g[mo[i]]--;
	work();ans-=s.a[0];
	printf("%d\n",(ans+P)%P);
	return 0;
}