当初备战省选之前，草草地了解了一下生成函数，浅尝辄止，实际上对它的理解仅仅停留在“知道有这么个东西”的程度

现在对多项式科技、对计数有了一些新的理解，打过一些有难度的，涉及到生成函数的题之后，对这个东西有了一些新的理解

虽然也还不是很彻底就是了，轻喷

对生成函数的一些理解

生成函数在算法竞赛中常常是一种用来计算方案数的手段，具有多项式和封闭式两种形式，二者是等价的。

生成函数的各项系数往往对应着方案数。对于有着多种约束条件的方案，将这些约束条件分解成若干个简单的约束，写出它们的生成函数之后可以直接利用乘法原理和加法原理得到所求方案的生成函数。

或者也可以用FFT，NTT之类的一顿卷

实践中，对于每种简单约束条件，往往先写出它们的多项式生成函数，再转化成对应的封闭式，直接使用封闭式进行计算，再转换回多项式，该多项式的某一项的系数即是所求答案。

常用的生成函数一般有两类，分别为普通生成函数（ordinary generating function, OGF）和指数生成函数（exponential generating function, EGF），分别形如

F(x)=∑nanxnF(x)=\sum_n a_n x^n

F^(x)=∑nanxnn!\hat F(x)=\sum_n a_n \frac {x^n} {n!}

普通生成函数一般解决组合计数问题，指数生成函数主要解决排列计数问题

构造出简单约束的生成函数并找到其对应封闭形式往往是解题的关键

常见生成函数多项式形式及封闭式形式

对于没见过的生成函数，可以通过已知的生成函数进行构造，或者通过解方程的方法解出封闭式。

例如对于F(x)=∑n≥0xnF(x)=\sum_{n \ge 0}x^n，有xF(x)+1=F(x)xF(x)+1=F(x)，从而F(x)=11−xF(x)=\frac 1 {1-x}

也可以用泰勒展开。

F(x)=∑n≥0xn=11−xF(x)=\sum_{n \ge 0} x^n = \frac 1 {1-x}

F(x)=∑n≥1xn=x1−xF(x)=\sum_{n \ge 1} x^n = \frac x {1-x}

F(x)=∑n≥0x2n=x1−xF(x)=\sum_{n \ge 0} x^{2n} = \frac x {1-x}

F(x)=∑n≥1nxn−1=∑n≥0(xn)′=x(1−x)2F(x)=\sum_{n \ge 1} nx^{n-1} = \sum_{n \ge 0}(x^n)'=\frac x {(1-x)^2}

F(x)=∑n≥0(mn)xn=(1+x)mF(x)=\sum_{n \ge 0} \tbinom{m}{n}x^n = (1+x)^m（二项式定理）

F(x)=∑n≥0(m+nn)xn=1(1−x)m+1F(x)=\sum_{n \ge 0} \tbinom{m+n}{n}x^n = \frac 1 {(1-x)^{m+1}}

G^(x)=∑n≥01n!xn=ex\hat G(x)=\sum_{n \ge 0} \frac 1 {n!}x^n = e^x

G^(x)=∑n≥0(−1)nn!xn=e−x\hat G(x)=\sum_{n \ge 0} \frac {(-1)^n} {n!}x^n = e^-x

G^(x)=∑n≥01(2n)!x2n=ex+e−x2\hat G(x)=\sum_{n \ge 0} \frac 1 {(2n)!}x^{2n} = \frac {e^x + e^{-x}} 2

G^(x)=∑n≥01(2n+1)!x2n+1=ex−e−x2\hat G(x)=\sum_{n \ge 0} \frac 1 {(2n+1)!}x^{2n+1} = \frac {e^x - e^{-x}} 2

G^(x)=∑n≥1(−1)n−1n!xn=ln⁡(1+x)\hat G(x)=\sum_{n \ge 1} \frac {(-1)^{n-1}} {n!}x^{n} = \ln(1+x)