P3702 SDOI2017 序列计数

P3702 [SDOI2017] 序列计数

Alice 想要得到一个长度为 \(n\) 的序列，序列中的数都是不超过 \(m\) 的正整数，而且这 \(n\) 个数的和是 \(p\) 的倍数。这 \(n\) 个数中，至少有一个数是质数。有多少个序列满足她的要求？

用一个简单的容斥，所有和是 \(p\) 倍数的序列减去和是 \(p\) 倍数并且只选合数的序列，就是至少有一个数是质数的序列。

不妨用两个桶 \(all[],npr[]\) 分别统计 \([1,m]\) 所有数、合数在 \(\operatorname{mod} p\) 意义下的个数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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\) 都可以这样处理，但是乘的桶不一样。

1
2
3
4
5
6
7
8
9
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} \]

（大部分的矩阵都是挺有规律的，推的时候举个小例子归纳一下就行） 不难看出下面的构造方法：

1
2
3
4
5
6
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];
    }
}