食物

给定一个有穷或者让无穷数列{\(a_0,a_1,...\)}，则称\(g(x)=a_0+a_1x+a_2x^2+...(-1<x<1)\)为原数列的一个生成函数

本质就是将问题转换为多项式问题，从而利用多项式的性质去解决问题

一些生成函数的化简见OI-wiki封闭形式

例题：现有\(1g,2,g,3g\)的砝码各一个，问能称出多重的物品，以及每个重量的物品被称出的方法数

我们先用DP的角度看待这个问题，设\(f[i][j]\)表示用前\(i\)个砝码可以称出重量为\(j\)的物品的方案数，则\(f[i][j]=f[i-1][j-weight[i]]+f[i-1][j]\)

然后我们再用多项式的角度去看待这个问题，设系\(a_i\)表示称出重量为\(i\)的物品的方案数，此时我们像DP一样，一个阶段一个阶段地考虑问题。对于第一个砝码，有\(f_1(x)=1+x\)（常数项的系数\(a_0\)为\(1\)，表示用第一个砝码称出重量为\(0\)的物品的方案数是\(1\)；\(x\)的系数\(a_1\)为\(1\)，表示用第一个砝码称出重量为\(1\)的物品的方案数是\(1\)）；对于前两个砝码有\(f_2(x)=f_1(x)(1+x^2)=1+x+x^2+x^3\)（\((1+x^2)\)与上面的解释一样，这里之所以要两者乘起来就是利用了多项式相乘指数相加的原理，即\(f_1(x)\)中的\(a_ix^i\)的\(a_i\)已经存储了用前一个砝码称出重量为\(i\)的物品的方案数，我们现在又知道了用第二个砝码称出重量为\(j\)的方案数\(a_j\)，那么这一个组合对“用前两个砝码称出重量为\(i+j\)的物品的方案数”的贡献就是\(a_ia_j\)，此时系数刚好相乘即乘法原理而\(x\)的指数相加刚好表示称出\(i+j\)的物品的方案数）；对于前三个砝码有\(f_3(x)=f_2(x)(1+x^3)=1+x+x^2+2x^3+x^4+x^5+x^6\)。最终得到的这个式子的系数就分别说明了方案数；或者也可以用整体来考虑，直接写出\(f(x)=(1+x)(1+x^2)(1+x^3)\)，\(f(x)\)的展开式是从三个因子中各选一项来组成的，而三个因子各选一项也就代表了三个砝码的不同选择，相乘时用了乘法原理，合并同类项时用了加法原理

又比如三个砝码的数量分别是\(2,+\infty,1\)，那么生成函数就是\(f(x)=(1+x+x^2)(1+x^2+x^4+x^6+...)(1+x^3)\)

另一道例题：现有\(n\)个不同的苹果，每种苹果都有无穷多个，选出\(k\)个苹果，请求出方案数，要求用生成函数解决这个问题

不难知道\(f_i(x)=(1+x+x^2+...)=\frac{1}{1-x}\)，于是\(f(x)=\overset{n}{\underset{i=1}{\prod}}f_i(x)\)

用组合数学的角度看问题，即\(x_1+x_2+...+x_n=n+k(x_i≥1)\)，隔板法求得为\(C_{n+k-1}^{n-1}\)，也就是说\(f(x)\)展开式\(x^k\)对应的系数就是\(C_{n+k-1}^{n-1}\)（这也就是OI-wiki封闭形式五）

理解了上面的过程后，这道题目就非常简单了，具体见OI-wiki的解答就好了

注意化简的过程，最好把有穷级数也写成分数的形式，这样更好化简