概述
用生成函数刻画一些困难的概率期望问题，使用一些朴素的数学技巧来解出答案。
设 \(F(x)\) 为概率生成函数，定义为：
\[F(x)=\sum_{i\ge 0}P(X=i)x^i \]容易发现 \(F(1)=1\)。
将 \(F(x)\) 求导得到：
\[F'(x)=\sum_{i\ge 0}iP(X=i)x^{i-1} \]容易发现 \(E(X)=F'(1)=1\)。
同时根据高中数学知识可以得到：
\[\begin{aligned} Var(X)&=\sum_{i\ge 0}(i-E(X))^2P(X=i)\\ &=\sum_{i\ge 0}i^2P(X=i)-2iE(X)P(X=i)+E(X)^2P(X=i)\\ &=\sum_{i\ge 0}i^2P(X=i)-E(X)^2 \end{aligned}\]而 \(F(x)\) 的二阶导：
\[F''(x)=\sum_{i\ge 0}i(i-1)P(X=i)x^{i-2} \]于是 \(Var(X)=F'(1)+F''(1)-(F'(1))^2\)。
例题
Luogu-P4548 CTSC 2006 歌唱王国
设 \(f_i\) 表示在长度为 \(i\) 时完成的概率，\(g_i\) 表示在长度为 \(i\) 时尚未完成的概率，记 \(F(x),G(x)\) 为 \(f,g\) 的生成函数，结合常数项 \(f_0=0,g_0=1\) 可以得到：
\[F(x)+G(x)=xG(x)+1 \]考虑将一个未完成的串后面直接接上目标串，此时可能出现没有完全接完就已经完成了的情况（原来就有一部分前缀），已经接上的部分既是前缀也是后缀，即 \(\mathrm{border}\)，剩下的部分就浪费了，所以可以写成：
\[\dfrac{x^LG(x)}{m^L}=\sum_{i=1}^L \dfrac{x^{L-i}F(x)}{m^{L-i}}[s[1,i]\in\mathrm{Border}(s)] \]因为要求 \(F'(1)\)，所以对第一个式子求导，得到：
\[F'(x)+G'(x)=G(x)+G'(x) \]所以 \(F'(1)=G(1)\)，再把 \(x=1\) 代入第二个式子。
\[G(1)=\sum_{i=1}^Lm^i[s[1,i]\in\mathrm{Border}(s)] \]所以答案就是 \(m\) 的所有 \(\mathrm{border}\) 次幂之和。
可见 PGF 解决问题的流程大致是设计一些数列的生成函数，联立方程，求导，并将 \(x=1\) 代入解决问题，上面部分已经阐明 \(x=1\) 时的值有许多特殊之处。
标签：2P,函数,sum,笔记,生成,ge,mathrm From： https://www.cnblogs.com/SoyTony/p/17958685/Learning_Notes_about_Probability_Generating_Fun