生成函数浅讲

感觉这是一个非常牛逼的东西，写了点自己的感悟，可能讲得不是很清楚。

生成函数的定义就比较牛，将数列 \(\{a_i\}\) 写成一个函数 \(A(x)=\sum{a_ix^i}\) 的形式叫做普通生成函数。

此处的 \(x^i\) 没有实际意义，只是一个占位符。对于生成函数来说，绝大数多项式的运算法则都是可以用的。

比如：

\(A(x)+B(x) = \sum\limits{(a_i+b_i)x^i}\)

\(A(x)B(x)=\sum\limits_i\sum\limits_j(a_ib_j)x^{i+j}\)。

一些常见的数列都可以写作生成函数的形式，而且往往都有较为简单的封闭形式：

\(\{1,0,0\dots\}\rightarrow 1\)

\(\{0,1,0\dots\}\rightarrow x\)

\(\{1,1,1\dots\}\rightarrow 1+x+x^2+\dots=\frac{1}{1-x}\)

\(\{1,0,1,0,1\dots\}\rightarrow 1+x^2+x^4\dots=\frac{1}{1-x^2}\)

拓展一下它们的乘积有什么含义

乘 \(x^k\) 相当于将数列向后平移 \(k\) 位。

乘 \(\frac{1}{1-x}\) 相当于对数列做一次前缀和，而 \(\frac1{(1-x)^k}\) 就是求 \(k\) 次前缀和，把这个过程写出来就会发现很像一个旋转了一下的杨辉三角，第 \(i\) 就是 \({i+k-1}\choose{k-1}\) 。

乘 \(\frac1{1-x^p}\) 后第 \(i\) 位就是原数列第 \(i\) 位往前第 \(p\) 的整数倍的位的前缀和（听着很绕其实很简单，笔者试图用简洁的语言的描述但语文水平不允许），类似的 \(\frac1{(1-x^p)^k}\) 的数列只在 \(p\) 的整数倍的位上有值并且第 \(ip\) 位为 \({i+k-1}\choose{k-1}\) 。

然后我们就可以用生成函数做一些很牛的事情。

先看一道简单题：

P10780 食物

题意：在许多不同种类的食物中选出 \(n\) 个，每种食物的限制如下：

• 承德汉堡：偶数个

• 可乐：\(0\) 个或 \(1\) 个

• 鸡腿：\(0\) 个，\(1\) 个或 \(2\) 个

• 蜜桃多：奇数个

• 鸡块：\(4\) 的倍数个

• 包子：\(0\) 个，\(1\) 个，\(2\) 个或 \(3\) 个

• 土豆片炒肉：不超过一个。

• 面包：\(3\) 的倍数个

每种食物都是以「个」为单位，只要总数加起来是 \(n\) 就算一种方案。对于给出的 \(n\) ,你需要计算出方案数，对 \(10007\) 取模。（\(n\le 10^{500}\)）

\(sol\)：首先对于每种食物构造一个数列，数列的第 \(i\) 位表示总数为 \(i\) 时这种食物有多少选法，显然只有 \(0/1\) ，如下：

\(\{1,0,1,0,1\dots\}\rightarrow 1+x^2+x^4\dots=\frac1{1-x^2}\)

\(\{1,1,0,0,0\dots\}\rightarrow 1+x\)

\(\{1,1,1,0,0\dots\}\rightarrow 1+x+x^2\)

\(\{0,1,0,1,0\dots\}\rightarrow x+x^3+x^5\dots=\frac{x}{1-x^2}\)

\(\{1,0,0,0,1,0\dots\}\rightarrow 1+x^4+x^8\dots=\frac1{1-x^4}\)

\(\{1,1,1,1,0\dots\}\rightarrow 1+x+x^2+x^3\)

\(\{1,1,0,0,0\dots\}\rightarrow 1+x\)

\(\{1,0,0,1,0\dots\}\rightarrow 1+x^3+x^6\dots=\frac1{1-x^3}\)

然后把它们乘起来就把数量上的加法转化为了系数上的相加，所以总数为 \(n\) 的答案就变成了 \(x^n\) 的系数。结果化简一下就是 \(\frac x{(1-x)^4}\) ，然后结合上面总结的 \(\frac x{(1-x)^k}\) 的规律，可以得到答案就是 \({n+2\choose3}\)，边读入边取模即可。

这道题中的生产函数是比较显然的，但是很多题目需要我们通过生产函数转化一些其他做法，比如这道题：

[国家集训队] 整数的lqp拆分

定义 \(F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2} (n>1)\) (其实就是斐波那契数列)

\(\sum\prod\limits_{i=1}^m F_{a_i}\)

\(m>0\)

\(a_1,a_2...a_m>0\)
\(a_1+a_2+...+a_m=n\)
由于答案可能非常大，所以要对 \(10^9 + 7\) 取模。（\(1\le n \le 10^{10000}\)）

\(sol\) ：首先考虑DP，设 \(f_{i,j}\) 表示固定 \(m\) 为 \(i\) ，\(n\) 为 \(j\) 时的答案。然后就会发现一个非常显然的暴力转移：\(f_{i,j}=\sum\limits_{k=０}^jf_{i-1,k}F_{j-k}\)，按理来说这里的 \(k\) 只能从 \(1\) 枚举到 \(j-1\) 但是 \(F_0=0,f_{i,0}=0\) 所以对答案是没有影响的。最终答案就应该是 \(\sum\limits_{i=1}^nf_{i,n}\) 。我们把 \(f_{i-1}\) 到 \(f_i\) 的递推看成一次卷积操作，就会发现 \(f_i=F^i\) ，那么答案对应的生成函数就是 \(\sum\limits_{i=1}^nF^i\) 。看着似乎不太可做，但是我们发现当 \(i>n\) 时，\(F^i\) 的第 \(n\) 项显然为 \(0\) 所以可以改写成 \(\sum\limits_{i=1}^{\infty} F^i=\frac F{1-F}\) ，把斐波那契数列的生成函数 \(F=\frac{x}{1-x-x^2}\) 代进去就是 \(\frac x{1-2x-x^2}\) ，这个生成函数可以用特征根来解出来，这里详细讲一下。

分子就是平移一位是好处理的，而分母转换一下就是

\(f_0=1,f_1=2,f_{n+1}=2f_n+f_{n-1}\)

我们考虑把后面的式子写成一种等比数列的形式：

\(f_{n+1}-pf_n=q(f_n-pf_{n-1})\)

然后我们可以求出这个等比数列的通项：

\(f_{n+1}-pf_n=q^n(f_1-pf_0)\)

\(p\) 和 \(q\) 应该满足条件：

\(pq=-1,p+q=2\)

所以 \(p\) 和 \(q\) 是方程 \(x^2-2x-1=0\) 的两个根 \(1+\sqrt2\) 和 \(1-\sqrt2\) ，