P3702 SDOI2017 序列计数
Alice 想要得到一个长度为 \(n\) 的序列，序列中的数都是不超过 \(m\) 的正整数，而且这 \(n\) 个数的和是 \(p\) 的倍数。这 \(n\) 个数中，至少有一个数是质数。有多少个序列满足她的要求？
用一个简单的容斥，所有和是 \(p\) 倍数的序列减去和是 \(p\) 倍数并且只选合数的序列，就是至少有一个数是质数的序列。
不妨用两个桶 \(all[],npr[]\) 分别统计 \([1,m]\) 所有数、合数在 \(\operatorname{mod} p\) 意义下的个数。
notprime[1]=1;
for(int i=2; i<=m; i++) {
if(!notprime[i]) {
for(int j=i+i; j<=m; j+=i) notprime[j]=1;
}
}
for(int i=1; i<=m; i++) {
all[i%p]++;
if(notprime[i]) npr[i%p]++;
}
设 \(f[i][j]\) 表示填完前 \(i\) 个数，和为 \(j\) （\(\operatorname{mod} p\) 意义下）的序列总数（填所有数），\(g[i][j]\) 填所有合数。
初值 \(f[0][0]=g[0][0]=1\) ，结果 \(f[n][0]-g[n][0]\) 。这里的第一维可以滚掉。
考虑枚举前一个数是 \(k\) 来转移，则有 \(O(n*q^2)\) 的朴素方法（保证下标非负）：
\[
f'[j]=\sum^{p-1}_{k=0}f[(j-k+p)\%{p}]*w[k]
\]
其中 \(w[]\) 为上面说的桶，\(f,g\) 都可以这样处理，但是乘的桶不一样。
f[0][0]=g[0][0]=1;
for(int i=1; i<=n; i++) {
for(int j=0; j<p; j++) {
for(int k=0; k<p; k++){
(f[i][j] += f[i-1][(j-k+p)%p]*all[k]) %=mod;
(g[i][j] += g[i-1][(j-k+p)%p]*npr[k]) %=mod;
}
}
}
将整个过程视为 \(n\) 个阶段，则每次 \(p^2\) 转移共涉及到 \(p\) 个已知变量，若 \(p=4\)：
\[
\begin{bmatrix}
f_0 & f_1 & f_2 & f_3
\end{bmatrix}
\cdot
\begin{bmatrix}
w[0] & w[1] & w[2] & w[3] \\
w[3] & w[0] & w[1] & w[2] \\
w[2] & w[3] & w[0] & w[1] \\
w[1] & w[2] & w[3] & w[0]
\end{bmatrix}
=
\begin{bmatrix}
f'_0 & f'_1 & f'_2 & f'_3
\end{bmatrix}
\]
（大部分的矩阵都是挺有规律的，推的时候举个小例子归纳一下就行） 不难看出下面的构造方法：
for(int i=0;i<p;i++){
for(int j=0;j<p;j++){
F[i][j]=all[(j-i+p)%p]; // 确实可以这么构造
G[i][j]=npr[(j-i+p)%p];
}
}