社论 - P1152 CTSC 2006 歌唱王国

本文同步发表于洛谷博客。

对于随机变量 $X$，定义其「概率生成函数」（下文称为 $\text{PGF}$）为形式幂级数 $F_X(x) = \sum\limits_{i = 0} ^ \infty P(X = i)x^i$，其中 $P(A)$ 表示条件 $A$ 的概率。

易知它有这些简单性质：

• $F_X(1) = \sum\limits_{i = 0} ^ \infty P(X = i) = 1$，对所有可能出现的情况的概率求和；
• $F_X'(1) = \sum\limits_{i = 1} ^ \infty iP(X = i) = E(X)$，其中 $E(X)$ 表示随机变量 $X$ 的值的数学期望。

---

设随机变量 $X$ 表示随机恰好 $X$ 个字符后，歌唱结束。

设 $F(x) = \sum\limits_{i = 1} ^ \infty P(X = i)x^i, G(x) = \sum\limits_{i = 0} ^ \infty P(X > i)x^i$，即随机恰好 $X$ 个数后歌唱结束/不结束的 $\text{PGF}$，那么易知 $F(x) + G(x)$ 的系数就是 $F(x)$ 系数的后缀和，于是现在既可以考虑它们表示的意义，也可以直接从这两个式子本身出发，得到下面这个式子，这里采用的是后者：

$$F(x) + G(x) = 1 + xG(x)$$

考虑 $F(x)$ 的系数后缀和又等于 $G(x)$ 系数整体向右偏移一位，然后再在最前面加上 $F(x)$ 所有系数的和，即 $F(1) = 1$。

再进行简单的变换就得到了

$$F(x) = (x - 1)G(x) + 1\\ F'(x) = G(x) + (x - 1)G'(x)\\ E(X) = F'(1) = G(1)$$

考虑在一个没有结束的序列上接下来强行接上 $S$ 使其结束，有：

$$\left(\dfrac{x}{n}\right)^{|S|}G(x) = \sum_{i = 1} ^ {|S|}\left[pre_i = suf_i\right]\left(\dfrac{x}{n}\right)^{|S| - i}F(x) $$

其中 $pre_i = suf_i$ 表示字符串 $S$ 存在长为 $i$ 的公共前后缀。

最后把 $x = 1$ 代入简单变形即得

$$\dfrac{1}{n^{|S|}}E(X) = \sum_{i = 1} ^ {|S|}[pre_i = suf_i]\dfrac{1}{n^{|S| - i}}\\ E(X) = \sum_{i = 1} ^ {|S|}[pre_i = suf_i]n^i$$