P7820 题解 / BM 算法的运用

飞雨烟雁 · 2024-05-24 19:09:45 · 题解

官方题解链接

我来补充一些官方题解没提到的细节，比如说为什么能用 Berlekamp–Massey 算法，以及那个神秘数字 4719 是怎么出现的。

朴素做法

首先我们明确一下动态规划是怎么做的。

我们设 f_{n,S} 为长度为 n 且最后 k-1 位恰为字符串 S 的合法 01 序列个数。举个例子，k=3,a=0 时 f_{5,01}=2，仅有的两种情况为 01101 和 11101。

按这样 dp 的时间复杂度是 \Theta (n2^k) 的。但是我们真的有必要把全部 2^{k-1} 个 S 拿来 dp 吗？

当然不用，比如当 k=3,a=0 时，f_{n,00} 始终是 0，因为它已经有两个零了，无论后一位是什么，都不可能恰好有 0 或 1 个零。也就是说，如果 S 中零的个数超过了 a+1，那我们没有必要考虑它。

除此之外，k=a=3 时，f_{n,11} 也始终是 0。原因是类似的。当 S 中零的个数低于 a-1，我们也没有必要考虑。

综上，我们只需考虑那些恰好含有 a 个零或含 a\pm 1 个零的字符串，一共有 m=\binom {k-1}{a-1}+\binom {k-1}{a}+\binom {k-1}{a+1} 个。

dp 结束后，我们要怎么得到答案呢？我们记答案为 g_n，则有含有 a-1 个零的 S 对答案的贡献为 f_{n-1,S}（因为它的下一位必须填零），含 a 个零的 S 的贡献为 2f_{n-1,S}（因为下一位填什么都行），含 a+1 个零的 S 的贡献为 f_{n-1,S}（下一位只能为一）。

在本题的数据范围之内，k=14,a=7 时 m 取得最大值，恰为 4719。下面，我们通过一个定理，来解释 m 与最短递推式长度之间的关系。

状态集递推定理

给定有限集 U 及系数 a_{s,t},b_{s}(s,t\in U)，若 f_{n,s} 有递推式 f_{n,s}=\sum_{t \in U}a_{s,t}f_{n-1,t}，则数列 g_n=\sum_{s\in U}b_sf_{n,s} 是至多 |U| 阶的线性递推数列。

详细证明见数学杂记【86 - 100】中的第 88 条，此外也可以用 Cayley-Hamilton 定理去证明。

在这道题里，这个有限集 U 就是那 m 个字符串构成的集合。套用该定理可得：答案序列 g_n 是至多 m 阶的线性递推数列，即最短递推式的长度不超过 m。

这样，我们就证明了这道题确实可以用 Berlekamp–Massey 算法来求解，并且最短递推式长度不超过 4719。那么我们就可以先 dp 求出 n=k,k+1,\cdots,k+2m 时的 g_n，然后上 BM 算法求解。

总时间复杂度为 \Theta(T(m^2+m\log m\log n))，核心代码如下：

int InvList[Mx], List[Mx], cnt; // [1, cnt]
int ZeroNum[Mx];
void Dfs(int Num, int ZeroCnt, int Pos, int a){
    if(!Pos){
        if(ZeroCnt - a <= 1 && ZeroCnt - a >= -1){
            List[++cnt] = Num, InvList[Num] = cnt;
            ZeroNum[cnt] = ZeroCnt;
        }
        return;
    }
    Dfs(Num << 1, ZeroCnt + 1, Pos - 1, a);
    Dfs(Num << 1 | 1, ZeroCnt, Pos - 1, a);
}

int Dp[2][Mx], Now; // k, k + 1, ..., k + 2 * cnt
ll Ans[Mx];
void Dfs2(int Num, int ZeroCnt, int Pos, int a, int k){
    if(!Pos){
        if(ZeroCnt == a || ZeroCnt == a + 1) ++Ans[k], ++Dp[0][InvList[Num >> 1]];
        return;
    }
    Dfs2(Num << 1, ZeroCnt + 1, Pos - 1, a, k);
    Dfs2(Num << 1 | 1, ZeroCnt, Pos - 1, a, k);
}

int Solve(int n, int k, int a){
    if(k == 1) return FastPow(2, n);
    cnt = 0, Now = 1;
    for(int i = 0; i < Mx; ++i) InvList[i] = List[i] = ZeroNum[i] = Ans[i] = Dp[0][i] = Dp[1][i] = 0;
    Dfs(0, 0, k - 1, a), Dfs2(0, 0, k, a, k);
    for(int i = k; i < k + cnt * 2; ++i){
        ll Sum1 = 0;
        for(int j = 1; j <= cnt; ++j) Dp[Now][j] = 0;
        for(int j = 1; j <= cnt; ++j){
            if(ZeroNum[j] == a) Sum1 += (Dp[Now ^ 1][j] << 1);
            else Sum1 += Dp[Now ^ 1][j];
            if(ZeroNum[j] == a + 1){
                Dp[Now][InvList[List[j] >> 1 | (1 << (k - 2))]] = (Dp[Now][InvList[List[j] >> 1 | (1 << (k - 2))]] + Dp[Now ^ 1][j]) % Mod;
            }
            else if(ZeroNum[j] == a){
                Dp[Now][InvList[List[j] >> 1 | (1 << (k - 2))]] = (Dp[Now][InvList[List[j] >> 1 | (1 << (k - 2))]] + Dp[Now ^ 1][j]) % Mod;
                Dp[Now][InvList[List[j] >> 1]] = (Dp[Now][InvList[List[j] >> 1]] + Dp[Now ^ 1][j]) % Mod;
            }
            else{
                Dp[Now][InvList[List[j] >> 1]] = (Dp[Now][InvList[List[j] >> 1]] + Dp[Now ^ 1][j]) % Mod;
            }
        }
        Ans[i + 1] = Sum1 % Mod, Now ^= 1;
    }
    if(n <= k + 2 * cnt) return Ans[n];
    return BMBM(Ans + k - 1, 2 * cnt + 1, n - k);
    // BMBM 用于求最短递推式，并返回数列远端的值
}

Remark

事实上，那个「状态集递推定理」不能保证「数列初值的长度一定小于递推式阶数」。不过 Berlekamp–Massey 算法在面临这种情况下仍可以正确给出答案（BM 算法会自己在前端补 0）。但有理分式拟合的做法就有可能出错了（详见这个帖子），除非转移矩阵是可逆的（可逆时必有初值长度小于递推阶数）。
本题有另一种做法。Cayley-Hamilton 定理证明「状态集递推定理」的过程告诉我们：转移矩阵的特征多项式必是数列的递推式。所以我们结合 P7776 可得一个 \Theta(T(m^3+m\log m\log n)) 的做法，但是无法通过此题。