生成函数其实并非和 FFT 等内容强相关？我猜的。
普通生成函数（OGF）
假设我们有一个下标从0开始的序列 \(\{a_i\}\) ，那我们就定义它的生成函数为 \(F(x)=\sum_i a_ix^i\)。我们其实从来不关心 \(x\) 的具体值，也基本不会真正带入一个 \(x\) 求值。这只是一个工具，用来转化问题的。
例如，\(\{7,2,3\}\) 的生成函数就是 \(F(x)=7+2x+3x^2\)。
\(\{a_i\}\) 当然也可以是一个无穷序列。比如 \(\{0,1,2,3,\cdots\}\) 的生成函数就是 \(F(x)=\sum_{i=0}^\infty ix^i\)。
这种无穷项的多项式一般可以叫做形式幂级数。其实只是取了一个高级的名字，加法减法乘法都和普通有限项多项式是一样的。
OGF 化为封闭形式
写无限项求和实在是太困难了。我们可能希望更简洁地表示一个 OGF。
相信大家都了解过 \(1+\frac12+\frac14+\frac18+\cdots\) 的推导吧。
有一种方式大概是是设这个求和结果为 \(S\)，然后我们会发现 \(2S=2+1+\frac12+\frac14+\cdots\)，居然和原来的式子有这么多一样的！于是我们两式相减。
OGF的推导也用到了同样的思想。
比如说 \(F(x)=\sum_{i=0}^\infty x^i\)，它是一个全 \(1\) 序列的OGF。
几乎和上面那个问题一样地，我们发现 \(xF(x)=\sum_{i=1}^\infty x^i\) 和原本的 \(F(x)\) 只差了一个 \(1\)。
于是我们有 \(xF(x)+1=F(x)\)。从而我们解出 \(F(x)=\frac1{1-x}\)。这样我们就将一个无穷项的式子变成了一个封闭的式子。
但是我们前文提到，我们其实并不会真的将 \(x\) 代入，我们关心的只是 \(x\) 的每一项系数。这个封闭形式帮助我们的方式其实是，有了封闭形式之后我们可以直接计算两个生成函数的和、差、积、etc。
我现在突然想要计算 \(G(x)=\sum_{i=0}^\infty (i+1)x^i\) 的封闭形式。
我们可以像上面一样推导，\(G(x)-xG(x)=F(x)\)，从而 \(G(x)=\frac1{1-x}F(x)=\frac1{(1-x)^2}\)。
但是我们也可以注意到 \(\sum_{j=0}^i 1\times 1=i+1\)，从而 \(G(x)=F(x)^2=\frac1{(1-x)^2}\)。
这启示我们，如果一个函数你很难瞪出来他的封闭形式，你可以瞪出来另外一个的生成函数的封闭形式辅助推导。
以及，上面这个 \(F(x)\) 其实是等比数列 \(a_i=p^i\) 在 \(p=1\) 时的特例。\(H(x)=\sum_{i=0}^\infty (px)^i=\frac1{1-px}\) 也都是成立的。
小练习
在 OI-wiki 上搬的（试试看！
-
\(F(x)=\sum_{i=1}^\infty x^i\)
答案
和上面的例子几乎一模一样吧？可以理解为减掉了一个 \(1\)，或是乘上了一个 \(x\)。当然重推的话过程也跟上面差不多。
\[F(x)=1-\frac1{1-x}=\frac x{1-x} \] -
\(F(x)=\sum_{i=0}^\infty[i\bmod 2=0]x^i\)
答案
只有偶数位上才有值，那我只需要乘上 \(x^2\) 就又可以消了！
\[x^2F(x)+1=F(x)\\ (1-x^2)F(x)=1\\ F(x)=\frac1{1-x^2} \] -
\(F(x)=\sum_{i=0}^n \binom{n}{i}x^i\)，其中 \(n\) 是一个给定的正整数。
答案
这不是我们二项式定理吗，配一下就变成
\[F(x)=\sum_{i=0}^n \binom{n}{i}x^i\cdot1^{n-i}\\ F(x)=(x+1)^n \] -
\(F(x)=\sum_{i=0}^\infty \binom{n+i}{i}x^i\)，其中 \(n\) 是一个给定的正整数。
提示：如果您没有学习过广义二项式定理，可能只能瞪出答案然后数学归纳证明。
答案
广义二项式定理
然后我们发现这就是负二项式定理的模板。
\[F(x)=\sum_{i=0}^\infty \binom{(n+1)+i-1}{i} 1^{-(n+1)-i}x^{i}\\ F(x)=(1-x)^{-n-1}=\frac{1}{(1-x)^{n+1}} \] -
\(F(x)=\sum_{i=0}^\infty f_ix_i\)，\(f_i=\begin{cases}1& i=0,1\\f_{i-1}+f_{i-2}& \text{otherwise.}\end{cases}\)，即斐波那契数列的生成函数。
答案
发现 \(xF(x)=\sum_{i=1}^\infty f_{i-1}x_i\)，则
\[xF(x)+F(x)=1+\sum_{i=1}^\infty (f_i+f_{i-1})x^i\\ xF(x)+F(x)=1+\sum_{i=1}^\infty f_{i+1}x^i\\ x^2F(x)+xF(x)=x+\sum_{i=2}^\infty f_ix^i\\ x^2F(x)+xF(x)=\sum_{i=0}^\infty f_ix^i-1\\ (x^2+x-1)F(x)=-1\\ F(x)=\frac{1}{1-x-x^2} \]前往oiwiki发现算的不太一样，原理是我的第零项为 \(1\)，而oiwiki是第零项为 \(0\)。我的斐波那契数列右移一位就是他的。而右移等价于 \(\times x\)，所以并不矛盾。
OGF 封闭形式展开
常用的展开工具主要就是广义二项式定理和上面的那个等比数列 \(\sum_{i=0}^\infty (px)^i=\frac1{1-px}\)。
比如前文算出来的 \(G(x)=\frac1{(1-x)^2}\)，我们发现
然后就展开了。
比如说刚刚练习里的一个函数 \(F(x)=\frac{1}{1-x^2}\)，无法用广义二项式定理展开，但是我们发现！
然后我们发现，和原来的式子是相符的。
部分分式分解
其实我们刚刚就是利用的部分分式分解。它的原理是把一个高次项分母的分式搞成一堆 \(\frac{1}{1-ax}\) 相加，这样就可以做了。
比如，现在让我们来推斐波那契数列通项公式吧！为了统一口径我们还是用 oiwiki 的生成函数。
首先我们知道 \(F(x)=\frac x{1-x-x^2}\)，那我们就要把它变成两个分式相加。为了做到这一点，我们先要对分母进行因式分解。
注意到带入 \(a\) 的一个根后，\(b\) 等于另外一个根，所以我们不妨 \(a=\frac{1+\sqrt5}{2},b=\frac{1-\sqrt5}{2}\)
你当然可以像 oiwiki 一样再解一个方程。但是在项数变多时就又会很麻烦。这里我们介绍一种很神秘的做法作为参考。
参考资料
省流：对于如下的方程
如果不存在相同的 \(p\) 那我们就有
说白了就是把使得 \(1+p_ix\) 等于 \(0\) 的那个 \(x\) 带入左边乘上 \(1+p_ix\) 后的式子。
证明很简单。两边同时乘上 \((1+p_ix)\) 后右边的 \(\sum\) 就只剩第 \(i\) 项了，别的全变成 \(0\) 了。
这简直和我们的目的一模一样！让我们试试看：
秒了，和 oiwiki 算的是一样的。遇到次数更高的时候就更能明白这个的强大。
于是我们可以展开。