[Luogu P4548 CTSC2006] 歌唱王国
提前约定：\(\text{border}\) 指的是公共前后缀。
题意
一个无限长的字符串 \(S\)，其中每个字符都是 \([1,n]\) 中的一个随机整数，求对于给定的字符串 \(t\)，\(S\) 中包含 \(t\) 的最短前缀的期望长度。
数据范围：\(1\le n\le 10^5\)，\(1\le m\le 10^5\)。有多测，数据不超过 \(50\) 组。
题解
有两种做法：
-
做法1：AC自动机上DP
做一个单串的AC自动机（KMP自动机），生成的显然是一张有向有环图，需要从根节点到达目标节点。
因为走每条边概率相等，可以参考早期学习概率与期望时的高斯消元算法来求解期望。
但是很显然这样的做法时间复杂度太高，没有办法通过本题。
那么我们现在开始好好看看如何优化。
如果我们设 \(g_i\) 表示到达 \(i\) 点所需的期望，那么此时显然我们能够得到DP式：
其中 \(j\) 是连到的所有点。上述的DP式的含义可以理解为要么从上一个点过来，要么在上一个点走错了从别的地方回到上一个点再来。
如果我们把 \(j\) 看作 \(\text{border}\) 的结尾，那么此时DP式变成：
接下来我们发现这样子时间复杂度从 \(\mathcal{O}(n^3)\)缩减到了 \(\mathcal{O}(nm)\)，还是不行，于是继续优化。
设 \(f_i=\sum g_j\)，我们如何求解 \(f_i\)？
此时我们观察AC自动机，发现上面的 \(\text{fail}\) 指针就是KMP的 \(\text{next}\) 指针，并且形成了一棵树，其父亲正好就是最长的 \(\text{border}\)（每个节点都是指向父亲的），进一步，所有的祖先其实都是 \(\text{border}\)。
考虑我们求解 \(f_i\) 实际上可以认为是在 \(i-1\) 的情况下额外加入了一个字符。在这些 \(\text{border}\) 中，有一些依旧是 \(\text{border}\)，但有些不是了。
现在我们加上所有的 \(\text{border}\) 的贡献，然后减去所有不合法的，就能得到答案。
此时能够得到DP式：
这里不做深入，因为我其实也没太弄懂，Luogu题解传送门。
随后你发现这就没了，时间复杂度 \(\mathcal{O}(n)\)，甚至简单到只需要跑一遍 \(next\) 数组。
给份代码：code。
-
做法2：概率生成函数（概率母函数，又称 \(\text{PGF}\)）
首先要明白生成函数是什么，如果你已经知道了，可以往下翻到下一个分割线，在这里浅谈一下关于生成函数我个人的理解。
生成函数实质上是一个多项式，常见的标准形态长这样：
考虑对于生成函数的操作，对于 \(F(x)\)，如果我们将其乘上一个 \(x\)，那么有：
当然，上面的操作可以逆着来，但是我们先暂时不进行讨论。注意观察，对于上面的式子，如果我们再次乘上一个 \(x\)，会发生什么？
此时其实可以发现，乘法可以看作 对 \(a\) 数列平移。
实际上，我们正是利用这一点来做题。举个简单的例子吧，我们的 \(\text{Fibbonacci}\) 数列的通项公式就是利用生成函数求解的。
设 \(F(x)=\sum\limits_{i=0}^{+\infty}f_ix^i\)，其中 \(f_i\) 表示 \(\text{Fibbonacci}\) 数列的第 \(i\) 项。
则我们发现：
我知道各位很懵逼，咱们来看看这是怎么得到的：
怎样？是不是更懵逼了。
那么接下来我们得到 \(F(x)=\dfrac{x}{1-x-x^2}\)。
有一个众所周知（并不）的结论：\(\sum\limits_{i=0}^{+\infty}x^i=\dfrac{1}{1-x}\)
证明很扯淡，但是天衣无缝：
于是我们可以考虑把上面求出的 \(F(x)\) 按照这个方法展开，此时两种方法（整体法及待定系数法）可以得到两种不同的通项公式，可以见OI-wiki中“普通生成函数”的介绍。
生成函数的一个好处在于它是多项式，我们不需要知道实际意义是怎样，只需要知道，这是对的，那也是对的，那么最后无论答案是什么，它就是对的。
可能答案甚至没有实际意义，就好比这道题最后由生成函数推出的答案谁也解释不了是什么，但是它就是对的，就像方程你也写不出实际意义一样。
我们回到本题，现在我们考虑如何利用生成函数来解决问题。
设 \(f_i\) 表示到 \(i\) 结束的期望，\(g_i\) 表示到 \(i\) 没结束的期望。
此时我们得到对应的两个生成函数 \(F(x)=\sum\limits_{i=0}^{+\infty}f_ix^i\) 和 \(G(x)=\sum\limits_{i=0}^{+\infty}g_ix^i\)，会发现一个特别的东西：\(F(1)=1\)。
这很显然，代入之后一眼就知道了，它在后面的解题中会起到作用，现在我们先不去管它。
接下来是这道题最关键的三个点：
- 1.\(G(1)\) 即为所求
相信各位看到这里都是一脸懵逼：啥玩意儿？这和答案有关系？
我们有简单的求导证明，但是各位都不会求导，那只能感性理解。
考虑到答案其实就是 \(\sum\limits_{i=0}^{+\infty}if_i\)，仔细想想会发现，\(g_i=\sum\limits_{j=i+1}^{+\infty}f_j\)。
那接下来各位不难发现 \(g\) 的总和就是答案，也就是 \(G(1)=\sum\limits_{i=0}^{+\infty}g_i\)。
具体来说，每一个 \(f_i\) 正好被 \(j\in [0,i-1]\) 中所有的 \(g_j\) 计算了一遍，总共就被计算了 \(i\) 遍。
接下来我们继续走，目标就很明确了，需要求解 \(G(1)\) 的值。
- 2.\(\dfrac{g_i}{n^m}=\sum\limits_{S_[1,t]\text{is S's border}}\dfrac{f_{i+t}}{n^{m-t}}\)
在这里我们设给出的字符串为 \(S\)，其长度为 \(m\)。
这个式子非常有意思，实际上它代表了一种情况的答案。
这种情况描述起来大概就是这样：（转自luogu博客）
有一天你开始随机，随机了 \(i\) 个字符还没有随机出 \(S\)，你失去了耐心，说：“无论如何，再给我随机 \(m\) 个！”然后 \(m\) 个过后，你发现这 \(m\) 个字符恰好是 \(S\)！
那么显然式子的左边就是这个玩意儿，它表示前 \(i\) 个字符没有结束，并且直接得到了一个 \(S\)，由于 \(S\) 的出现概率为 \(\dfrac{1}{n^m}\)，所以显然正确。
接着右边又是怎么回事呢？此时你其实在随机完之前就已经结束咧！但是你并没有选择结束，而是继续进行了。
由于 \(f_i\) 保证在 \(i\) 之前都没有结束（见定义），因此你会发现，右边这个式子也正好完美地表示了上述的情况（此处注意 \(S\) 也是 \(\text{S's border}\)）。
更详细地说，在随机完 \(m\) 个字符前想要结束就必须找到一个 \(\text{border}\)，在这个 \(\text{border}\) 的前面让它被其它字符补齐。
接下来把这个式子两边的分母去掉，得到 \(g_i=\sum\limits_{S_[1,t]\text{is S's border}}f_{i+t}n^t\)。
发现这个式子中出现了 \(f,g\)，尝试将其变成生成函数的形式。
- 3.\(x^mG(x)=\sum\limits_{S_[1,t]\text{is S's border}}x^{m-t}F(x)n^t\)
这里我们要用到一个定理：两个多项式每一项系数相等，则两个多项式相等。这很显然，就不证了（也不用证吧？）。
那么实际上由于上面得到的等式对于每一个 \(i\) 都成立，因此观察上面的生成函数，会发现乘完之后恰好每一项都是一致的。
其实换种说法，两个元素（\(g_i,f_{i+t}\)）的下标不同，将其转化为生成函数的时候 需要平移的距离也不同。
如此由于系数一一对应相等，得到生成函数相等的式子，我们就可以将 \(x=1\) 代入进去，得到 \(G(1)=\sum\limits_{S_[1,t]\text{is S's border}}F(1)n^t\)。
这个时候一开始被我们落下的 \(F(1)=1\) 派上用场了，上面的 \(F(1)\) 直接去掉，我们得到了我们所需求解的答案就是 \(\sum\limits_{S_[1,t]\text{is S's border}}n^t\)。
这各位要是还不会就回幼儿园学一学识字吧（无慈悲）。
可以用KMP算出所有的 \(\text{border}\)，也可以用字符串 \(\text{Hash}\) 乱搞，总之时间复杂度 \(\mathcal{O}(n)\)，随便过，code。
后记
看不见代码是不是很烦？