CVBB ACM Team

设有一串 $S$，从一个空串开始，每次等概率随机往后面加一个字符，包含 $S$ 时停止，求串长度的期望。

设 $F(x)$ 表示恰在长度为 $x$ 停止的概率生成函数，$G(x)$ 表示长度为 $x$ 仍未停止的生成函数。那么有

$$ \begin{aligned} 1+xG(x)&=F(x)+G(x)\\ G(x)\cdot\frac{x^{n}}{|\Sigma|^{n}}&=F(x)\sum_{i=1}^{|S|}[1..i\text{ is border}]\frac{x^{n-i}}{|\Sigma|^{n-i}} \end{aligned} $$

所求为 $F'(1)$。对式 $1$ 求导得 $G(x)+xG'(x)=F'(x)+G'(x)$，即 $F'(1)=G(1)$。式 $2$ 中令 $x=1$ 即可得到结论。