前言
一个挺早就知晓其存在的诡异科技，只不过当时遇到它的题目是用其他的做法搞过去的。
这次好好研读了一下杨懋龙神仙的论文《浅谈生成函数在掷骰子问题上的应用》，还是有不少收获的。（尽管看了一半就看不下去了）
基本定义
假设存在一个离散随机变量(X)满足(P(X=i)=a_i)，那么它的概率生成函数就应该是：
[F(x)=sum_{i=0}^{+infty}P(X=i)x^i
]
定义看起来很简单，更重要的是它的几个性质。
重要性质
性质一
(X)作为一个离散随机变量，显然它生成所有数的概率总和应当是(1)，也就是说：
[F(1)=sum_{i=0}^{+infty}P(X=i)=1
]
性质二
我们对于(F(x))求导，得到：
[F'(x)=sum_{i=0}^{+infty}iP(X=i)x^{i-1}
]
然后再代入(x=1)，得到：
[F'(1)=sum_{i=0}^{+infty}iP(X=i)
]
发现这玩意恰好是(X)的期望值！
也就是说：
[E(X)=F'(1)
]
性质三
我们继续对这个式子求导，可以发现：
[E(X^{underline{k}})=F^{(k)}(1)
]
性质四
对于方差有这样一个公式：
[Var(X)=E((X-E(X)))^2)=E(X^2-2XE(X)+E(X)^2)=E(X^2)-E(X)^2
]
考虑(E(X^2))，它可以这样表示：
[E(X^2)=E(X(X-1))+E(X)=E(X^{underline{2}})+E(X)=F''(1)+F'(1)
]
所以把这个式子代回原式，得到：
[Var(x)=F''(1)+F'(1)-(F'(1))^2
]
例题
讲完这些性质概率生成函数也就告一段落了，接下来就是例题。
这里就先列出一道吧：【洛谷4548】[CTSC2006] 歌唱王国（概率生成函数）。