自动搬运

查看原文

来自洛谷，原作者为

	Petit_Souris 鼓励的话语 无论多少次我都会说给你听 | 你在名为弱小的深渊 究竟看见过什么 | 天空中出现了一种罕见的天文现象

搬运于2025-08-24 22:35:26，当前版本为作者最后更新于2023-05-27 10:06:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

和 CTSC 歌唱王国几乎一致的题目，我来推广一个（比较组合意义的）有趣解法。参考了 WYXkk 在那题的题解 和 知乎上的一个回答。

题意：给定一个字符串 $S$，长度为 $M$。字符集大小为 $N$。有一个字符串 $T$，初始为空。每秒随机在字符集当中选一个字符加到 $T$ 的末尾，对于每个 $S$ 的前缀 $p$ 求出期望几秒之后 $p$ 成为了 $T$ 的子串。$M\le 10^6,N\le 100$。

初看这道题感觉除了把 KMP 自动机建出来消元以外没有好的多项式复杂度做法，但是这个故事的解释很精妙。

我们先对一个单独的 $S$ 求解，不考虑前缀的问题。假设拥有这个会自动吐字符的字符串 $T$ 的人开了一座赌场，设计了这样一个游戏：

支付 $k$ 块钱玩一次游戏，猜 $T$ 的下一个出现的字符为 $x$。如果猜对了，返还 $Nk$ 块钱，否则游戏结束。

这个游戏显然是绝对公平的——每次有 $\frac{1}{N}$ 的概率猜对，因此赌场不赚不赔。

我们假设有无限多个赌徒依次进入赌场玩这个游戏。第 $1$ 位赌徒有 $1$ 块钱，在第 $1$ 秒进入，他猜测接下来会出现 $S_1$。如果猜对了，把刚刚获得的全部 $N$ 块钱押第 $2$ 秒出现 $S_2$。如果再猜对，把获得的全部 $N^2$ 块钱押第 $3$ 秒出现 $S_3$......对于其他赌徒也是相同的：第 $i$ 位赌徒在第 $i$ 秒进入赌场，把所有的 $N^j$ 块钱押接下来出现 $S_{j+1}$，依此类推......一旦有一位赌徒连续猜对了 $M$ 次，赌场老板就会因为觉得自己亏了而关闭赌场。

我们现在假设猜对了 $M$ 次的是第 $t$ 位赌徒，那么我们观察一下在赌场关门倒闭了以后，哪些赌徒手上还有钱，以及他们分别有几块钱：

• 第 $t-1$ 位以及之前的赌徒都空手而归。

• 第 $t$ 位赌徒有 $N^M$ 块钱。

• 在第 $t$ 位之后的赌徒还可能有钱，这时候他们猜的串是 $S$ 的一个后缀，它又应该和 $S$ 的前缀相同，因此如果第 $t+k$ 位赌徒没有空手而归，他应该代表了一个 border。且如果 border 长度为 $l$，他会拥有 $N^l$ 块钱。

不难发现按照这样的分析，$S$ 的每个 border 都会对应一位赚到钱的赌徒，并且每个 border 只会出现恰好一次。

如果我们假设 $S$ 的 border 长度集合为 $B$，那么所有赌徒手上的资金总和为 $\sum\limits_{x\in B}N^x$。

最后我们要将赌徒的钱和赌场老板的字符串 $T$ 的长度找出联系。赌场在这个游戏期望下不赚不赔，因此赌徒这个整体也是不赚不赔的。而又由于期望拥有 $\sum\limits_{x\in B}N^x$ 块钱，每个赌徒初始有 $1$ 块钱，所以赌徒的个数也是 $\sum\limits_{x\in B}N^x$。因此游戏的期望时长也是 $\sum\limits_{x\in B}N^x$ 秒，也即为所求的答案。

此时回到原题目，发现我们做一遍 KMP 求出 border，沿着 fail 指针跳 dp 就可以算出答案了，时间复杂度 $\mathcal O(M)$。（最后的实现如果有不理解的建议参考其他题解，这里不多赘述）。