题解 luogu 4548 & bzoj 1152 歌唱王国

在外站看到一个直接基于式子本身变换的方法，因此我按照自己的理解整理了一下，本文同步发表于 [Hydro bzoj](https://hydro.ac/d/bzoj/p/1152/solution)。 设随机变量 $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$$