自动搬运

查看原文

来自洛谷，原作者为

	飞雨烟雁 尽管我们走不了最短路，但图仍是连通图，TLE之前，没有一个节点叫失败。

搬运于2025-08-24 22:33:23，当前版本为作者最后更新于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

1. 事实上，那个「状态集递推定理」不能保证「数列初值的长度一定小于递推式阶数」。不过 Berlekamp–Massey 算法在面临这种情况下仍可以正确给出答案（BM 算法会自己在前端补 $0$）。但有理分式拟合的做法就有可能出错了（详见这个帖子），除非转移矩阵是可逆的（可逆时必有初值长度小于递推阶数）。

2. 本题有另一种做法。Cayley-Hamilton 定理证明「状态集递推定理」的过程告诉我们：转移矩阵的特征多项式必是数列的递推式。所以我们结合 P7776 可得一个 $\Theta(T(m^3+m\log m\log n))$ 的做法，但是无法通过此题。