P8043

Petit_Souris · 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)。（最后的实现如果有不理解的建议参考其他题解，这里不多赘述）。