定义
定义概率生成函数为：
$$
P(x)=\sum_{i=0}^{\infty}p_ix^i
$$
其中 $p_i$ 表示某一离散随机变量取值为 $i$ 的概率
性质
首先概率之和应该为 $1$，即：
$$
P(1)=1
$$
根据期望的定义 $E(x)=\sum_{t}P(t)t$，于是有：
$$
E(x)=P’(1)
$$
因为求导的时候会出现 $p_i \times i$ 项
由于 $E \left(x ^ { \underline { k } } \right) = P ^ { ( k ) } ( 1 ) , k \neq 0$，于是 $x$ 的方差为：
$$
\operatorname { Var } ( x ) = P ^ { \prime \prime } ( 1 ) + P ^ { \prime } ( 1 ) - \left( P ^ { \prime } ( 1 ) \right) ^ { 2 }
$$
例题
设字符集大小为 $\Sigma$，给定一长度为 $n$ 的模板串 $T$，且 $T$ 的字符集亦为 $\Sigma$
现有一初始为空的串 $S$，每次在 $S$ 的末尾随机添加 $\Sigma$ 中的一个字符，直到 $S$ 中出现 $T$ 为止
求 $S$ 的长度的期望，答案模 $10000$
设 $f_i$ 表示长度为 $i$ 时停止的概率，其生成函数为 $F(x)$，同时答案就是 $F’(1)$
设 $g_i$ 表示长度为 $i$ 时还没停止的概率，其生成函数为 $G(x)$
那么有：
$$
f_i+g_i=g_{i-1}
$$
因为从长度为 $i-1$ 且还未停止到长度为 $i$，要么仍未停止，要么就停止了
用生成函数表示为：
$$
F(x)+G(x)=xG(x)+1
$$
对于字符串 $T$，设一数组 $A$，其中 $A_i=[T_{1,i}=T_{|T|-i+1,|T|}]$
设 $|T|=L$，字符集大小为 $\Sigma$，则有：
$$
G(x) \times \left(\frac{1}{\Sigma}x\right)^L=\sum_{i=1}^{L}A_i \times F(x) \times \left(\frac{1}{\Sigma}x\right)^{L-i}
$$
左式的意思是，对于某仍为结束的字符串，往后添加模板串的所有字符后一定会结束
右式的意思是，可能在添加的过程中已经提前结束了，此时的情况就是存在一个 $\text{border}$
对于第一个式子，有：
$$
F’(x)+G’(x)=G(x)+xG’(x) \Rightarrow F’(1)=G(1)
$$
对于第二个式子，有：
$$
\begin{aligned}
G(1) \left(\frac{1}{\Sigma}\right)^L=\sum_{i=1}^{L}A_iF(1) \left(\frac{1}{\Sigma}\right)^{L-i}
\end{aligned}
$$
由于 $F(1)=1$，于是有：
$$
\begin{aligned}
G(1)
=& \sum_{i=1}^{L}A_i\left(\frac{1}{\Sigma}\right)^{L-i}\left(\frac{1}{\Sigma}\right)^{-L} \
=& \sum_{i=1}^{L}A_i \Sigma^L
\end{aligned}
$$
