1.概述
取值处概率的生成函数。
\(F(1)=1,F'(1)=E\)
2.分析
设 \(F(i)\) 为 \(i\) 时刻结束概率的生成函数，\(G(i)\) 为 \(i\) 时刻未结束概率的生成函数，那么有：
\[f_i+g_i=g_{i-1} \\ \Rightarrow F(x)+G(x)=xG(x)+1 ~~~~~ (1) \]然后我们强行钦定结束位置，得到第二个方程（如 [CTSC2006]歌唱王国）
令 \(a_i\) 表示 \(S[...i]\) 是否为一个 \(\text{border}\)，有
\[G(x)(\frac{x}{m})^n=\sum_{i=1}^n a_i F(x) (\frac{x}{m})^{n-i} \](个人理解是：在未结束的串后加入 \(S\) 使之结束，但每一个不同的长为 \(i\) 的未结束串结束位置不一定同，所以枚举它们的结束位置,并且需要补位)
对 \((1)\) 式两端求导：
\[F'(x)+G'(x)=xG'(x)+G(x) \\ \Rightarrow F'(x)=(x-1)G'(x)+G(x) \\ \Rightarrow F'(1)=G(1) \](其实就是期望与概率的关系)
然后考虑解 \(G(1)\)，
\[G(1)(\frac{1}{m})^n=\sum_{i=1}^n a_i F(1) (\frac{1}{m})^{n-i} \]\[G(1)=\sum_{i=1}^n a_i m^{i} \] 标签：PGF,概率,结束,函数,sum,生成,frac,Rightarrow From： https://www.cnblogs.com/chihik/p/pgf.html