LGP3702题解

很容易想到容斥，计算不包含质数的方案数和总方案数。

设 \(f[n][i]\) 表示长度为 \(n\) 的序列，每个元素的和对 \(p\) 取模的结果。

容易有 \(f[n][i]=\sum_{j=0}^pf[n-1][i-j\bmod p]\times g[j]\)，\(g[j]\) 代表选出的数（非质数或 \([1,m]\) 的整数）对 \(p\) 取模为 \(j\) 的数的数量。

容易发现这是一个循环卷积，容易做到 \(O(p^2\log n)\)。

我们知道 \(DFT\) 做的也是循环卷积，所以我们把 \(w_n^{0\sim n-1}\) 拉出来，将 \(g\) 看做多项式，带入这些点值后快速幂，最后 \(IDFT\) 可以做到 \(O(p^2+p\log n)\)。

但是 \(20170408\) 不是质数 是省选的日期，进行质因数分解后可能系数没有下标，所以写了个 \(O(p^2\log n)\) 就溜了（

#include
typedef unsigned ui;
const ui M=105,N=2e7+5,mod=20170408;
ui n,m,p,g[M];bool zhi[N];
inline void times(ui*f,ui*g){
	static ui sav[M<<1];
	for(ui i=0;i>=1,times(g,g))if(n&1)times(f,g);
	return f[0];
}
signed main(){
	ui sum1,sum2;
	scanf("%u%u%u",&n,&m,&p);sieve(m);
	const ui&x=m%p,&y=m/p;
	for(ui i=0;i