操作数列的强大工具——生成函数学习笔记

Posted on:2023年8月6日 at 14:00

本篇笔记的定位为：完全不知道或略微了解生成函数的竞赛选手。

不知道对高考数学有没有用。

学习该笔记，需要数列，函数，多项式相关知识（入门水平即可）。

由于作者个人实力原因，还不会 EGF 等高级生成函数，最近正在学习，等学会了一并更新。

前言

我们用一个简单的例子引入：斐波那契数列。

我们可以用矩阵快速幂的方式快速求解其第 nn 项，但是无论如何，在潜意识中，我们会认为它一定存在一个通项公式，且或多或少听说过它和黄金分割比有关系。

而在学会了它之后，我们可以有理有据地给出斐波那契数列的公式，并且可以类推，将任意递推式转移为通项公式。

形式幂级数——一切的开始

形式幂级数（ordinary generating function，OGF），是函数与数列的一种转换。

对于数列 AA，它的形式幂级数定义为：

∑i=0Aixi\sum_{i=0} A_ix^i

说的简单点，我们只是将数列的系数搬到了函数上，这里的数列，可以是有穷的，也可以是无穷的，不过我们更多讨论的是无穷数列，有穷数列也可以看成无穷数列。

为了避免抽象，我举几个例子：

很简单吧，也就是说，我们数列的通项，其实就是生成函数每一项的系数，也就是说 Ai=[xi]F(x)A_i = [x^i]F(x)（下文会使用这种表达方法，代表 xix^i 项的系数）。

再简单一点——封闭形式

上面的写法有点太复杂了，而且没有办法很好地结合函数和多项式的本质。 我们以数列 A=[1,1,1,⋯ ]A = [1,1,1,\cdots] 为例来讲解封闭形式。

封闭形式的生成函数是一个封闭形式的函数表达式（废话），有有限项字母和数字参与有限次运算得来的结果。

可以认为形式幂级数形式和封闭形式的作用是相同的，只是封闭形式由有限项组成，能更方便地运算。

如 x2+x+3x+6x^2+x+3x+6，3x+5\sqrt{3x+5} 这些是封闭形式，而 ∑i=1ai2i\sum_{i=1}\frac{a_i}{2^i} 这类则不是。

设数列 AA 的封闭形式为 F(x)F(x)，我们可以列出：

F(x)↔[1,1,1,⋯ ]F(x) \leftrightarrow [1,1,1,\cdots]

我们如果将两边同时乘上 xx，则可以得到：

xF(x)↔[0,1,1,1,⋯ ]xF(x) \leftrightarrow [0,1,1,1,\cdots]

首项为 00 的原因可以参照形式幂级数的理论理解，结论是两边同时乘 xix^i 就等于将数列向右移动 ii 位，左侧补 00。

我们把补充的的 00 变成 11，我们发现我们构造回了原序列。

xF(x)+1↔[1,1,1,1,⋯ ]xF(x)+1 \leftrightarrow [1,1,1,1,\cdots]

所以我们列方程得到：xF(x)+1=F(x)xF(x)+1 = F(x)，解得 F(x)=11−xF(x) = \frac{1}{1-x}。

于是我们得出了全 11 数列的生成函数的封闭形式： 11−x\frac{1}{1-x} 。

注意： 在本文中，形式幂级数的展开形式会同时使用两种方法表达，前一种不标准但较为直观，后一种是标准的数学写法。

第一种表达形式：F(x)=11−x↔[1,1,1,1,⋯ ]F(x) = \dfrac{1}{1-x} \leftrightarrow [1,1,1,1,\cdots]

第二种表达形式：F(x)=11−x=∑i=0xiF(x) = \dfrac{1}{1-x} = \sum_{i=0}x^i

如果您是新手，第一种方式很直观，适合第一次阅读，如果您已经对这部分内容有了解，第二种方式会很标准严谨。

所以在下面的封闭形式推导时，会同时出现两种形式，请选择自己适合的形式理解，或结合理解。

我要在这里放一个小练习，做不做由你，但是做了会让你更好地理解生成函数的本质。

答案和解析在文章末尾。

例题1——求出下列数列的形式幂级数和封闭形式

A=[0,1,2,3,4,⋯ ],Ai=iA=[0,2,4,6,8,10,⋯ ],Ai=2iA=[0,1,4,9,16,25,36,⋯ ],Ai=i2A=[1,1,2,3,5,8,⋯ ],Ai=Ai−1+Ai−2,A0=1\begin{aligned}A &= [0,1,2,3,4,\cdots],A_i = i \\ A &= [0,2,4,6,8,10,\cdots],A_i = 2i \\ A &= [0,1,4,9,16,25,36,\cdots],A_i = i^2 \\ A &= [1,1,2,3,5,8,\cdots],A_i = A_{i-1}+A_{i-2},A_0=1\end{aligned}

我知道你很急，但你先别急——一个可能的误区

让我先急。

拿到 11−x\frac{1}{1-x} 之后，不要尝试去研究函数的性质，不要去研究对称性，奇偶性，单调性，抛开那些东西。

因为研究它们没有用。这里的 xx 是一个形式记号，一个符号，仅仅是用于区分幂次的，所以带入值运算没有意义。

关于为什么代值不对的问题，我个人推测和群论有关，建议自行查阅相关资料。

绕过了这个误区，我们可以继续走下去了。

到底有什么用？——生成函数间的运算

我们之前说过一句话，封闭形式和形式幂级数形式是等价的。

所以对封闭形式进行运算和对形式幂级数进行运算也是等价的。（这句不是废话）

我们来看看我们可以进行怎么样的运算。

加法/减法

加减法很好理解，就是对对应的幂次进行加减，等价于数列和差。

乘法？

你可能会疑惑，形式幂级数乘起来是什么样的。

实际上，两个多项式相乘，等价于系数数列卷积。

很神奇是不是，为什么呢？

我们考虑形式幂级数 AA 乘 BB 等于 CC，那么显然有 [xn]C=∑i+j=n[xi]A[xj]B[x^n]C = \sum_{i+j=n}[x^i]A[x^j]B。

而这恰好就是卷积的式子！

现在我们构造数列的方法又多了一条：卷积。

有了这种强大的运算，我们可以构造出任意有通项公式的数列。

举个例子吧，上面提到了全 11 数列的封闭形式是 11−x\frac{1}{1-x}，那么将任意生成函数乘上它，就相当于和它卷积，也就是求前缀和。

很强大是不是，上面练习题的部分也可以用这个构造技巧。

不当标题党——封闭形式的展开

我们说了，生成函数的目的是为了求出数列通项。我们通过生成函数构造出了数列的封闭形式，自然要将其展开，得到数列的形式幂级数，也就是通项公式。

但是要将有限项的封闭形式变为无限项的形式幂级数绝非易事，我们可以通过如下套路化的方法来构造通项公式。

我们拿斐波那契数列的封闭形式 F(x)=x1−x−x2F(x) = \frac{x}{1-x-x^2} 举例。

首先将 1−x−x21-x-x^2 因式分解（也就是求出它的根），得到 −(x−1+52)(x−1−52)-(x-\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})。

再应用待定系数法，列出方程：

−x(x−1+52)(x−1−52)=ax−1+52+bx−1−52\frac{-x}{(x-\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})} = \frac{a}{x-\frac{1+\sqrt{5}}{2}} + \frac{b}{x-\frac{1-\sqrt{5}}{2}}

我们这样做的目的是缩小问题规模，将其转化为两个更容易求的生成函数。

将式子通分，得到

−x(x−1+52)(x−1−52)=(x−1−52)a(x−1+52)(x−1−52)+(x−1+52)b(x−1+52)(x−1−52)\frac{-x}{(x-\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})} = \frac{(x-\frac{1-\sqrt{5}}{2})a}{(x-\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})} + \frac{(x-\frac{1+\sqrt{5}}{2})b}{(x-\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})}

也就是

−x=ax−a−a52+bx−b+b52-x = ax - \frac{a-a\sqrt{5}}{2} + bx - \frac{b+b\sqrt{5}}{2}

按照 xx 的次数列出方程，我们得到了如下方程组：

{a−a52+b+b52=0a+b=−1\begin{cases}\frac{a-a\sqrt{5}}{2} + \frac{b+b\sqrt{5}}{2} &= 0 \\ a+b &= -1\end{cases}

解得 {a=−5+510b=5−510\begin{cases}a=-\frac{5+\sqrt{5}}{10} \\ b=\frac{\sqrt{5}-5}{10}\end{cases}。

也就是说，F(x)=−5+510x−1+52+5−510x−1−52F(x) = \frac{-\frac{\sqrt{5}+5}{10}}{x-\frac{1+\sqrt{5}}{2}} + \frac{\frac{\sqrt{5}-5}{10}}{x-\frac{1-\sqrt{5}}{2}}，接下来我们只需展开两项。

问题是，这两项如何展开呢？其实这是一个等比数列的形式，我们来推一下。

等比数列的封闭形式

我们来现推一下：

F(x)↔[a,aq,aq2,aq3,⋯ ]x⋅F(x)↔[0,a,aq,aq2,aq3,⋯ ]qx⋅F(x)+a↔[a,aq,aq2,aq3,aq4,⋯ ]\begin{aligned} F(x) &\leftrightarrow [a,aq,aq^2,aq^3,\cdots] \\ x \cdot F(x) &\leftrightarrow [0,a,aq,aq^2,aq^3,\cdots] \\ qx \cdot F(x) + a &\leftrightarrow [a,aq,aq^2,aq^3,aq^4,\cdots] \end{aligned} F(x)=∑i=0aqixix⋅F(x)=∑i=0aaixi+1=∑i=1aqi−1xiqx⋅F(x)=∑i=1aqixiqx⋅F(x)+a=a+∑i=1aqixi=∑i=0aqixi=F(x)\begin{aligned}F(x) &= \sum_{i=0}aq^ix^i \\ x \cdot F(x) &= \sum_{i=0}aa^ix^{i+1} &= \sum_{i=1}aq^{i-1}x^i \\ qx \cdot F(x) &= \sum_{i=1}aq^ix^i \\ qx \cdot F(x)+a &= a + \sum_{i=1}aq^ix^i &= \sum_{i=0}aq^ix^i &= F(x) \end{aligned}

则我们得到了：

qx⋅F(x)+a=F(x)(qx−1)F(x)=−aF(x)=a1−qx\begin{aligned} qx\cdot F(x) + a &= F(x) \\ (qx-1)F(x)&=-a \\ F(x)&=\frac{a}{1-qx} \end{aligned}

答案近在眼前！

我们整理下 F(x)=−5+510x−1+52+5−510x−1−52F(x) = \frac{-\frac{\sqrt{5}+5}{10}}{x-\frac{1+\sqrt{5}}{2}} + \frac{\frac{\sqrt{5}-5}{10}}{x-\frac{1-\sqrt{5}}{2}} 这个式子，我们得到了：

F(x)=−151−21+5x+151−21−5xF(x) = -\frac{\frac{1}{\sqrt{5}}}{1-\frac{2}{1+\sqrt{5}}x}+\frac{\frac{1}{\sqrt{5}}}{1-\frac{2}{1-\sqrt{5}}x}

而两项代表的数列分别为 Ai=−15⋅(21+5)iA_i = -\frac{1}{\sqrt{5}} \cdot (\frac{2}{1+\sqrt{5}})^i 和 Bi=−15⋅(21−5)iB_i = -\frac{1}{\sqrt{5}} \cdot (\frac{2}{1-\sqrt{5}})^i，我们将其求和便得到了通项公式：

Fi=15⋅(−(21+5)i+(21−5)i)Fi=15⋅((1+52)i−(1−52)i)\begin{aligned} F_i &= \frac{1}{\sqrt{5}} \cdot (-(\frac{2}{1+\sqrt{5}})^i + (\frac{2}{1-\sqrt{5}})^i) \\ F_i &= \frac{1}{\sqrt{5}} \cdot ((\frac{1+\sqrt{5}}{2})^i-(\frac{1-\sqrt{5}}{2})^i) \end{aligned}

例题2 某年的初赛真题

有数列 ff，f0=0,f1=1,fi=fi−1+fi−22f_0=0,f_1=1,f_i=\dfrac{f_{i-1}+f_{i-2}}{2}，可以证明数列是收敛的，求出数列最终收敛于哪个值。

我们如果能解出这个数列的通项公式，则就能得到答案。

F(x)↔[f0,f1,f2,f3,⋯ ]xF(x)↔[0,f0,f1,f2,⋯ ]x2F(x)↔[0,0,f0,f1,⋯ ](x+x2)F(x)↔[0,0,2f2,2f3,⋯ ]\begin{aligned}F(x) & \leftrightarrow [f_0,f_1,f_2,f_3,\cdots] \\ xF(x) & \leftrightarrow [0,f_0,f_1,f_2,\cdots] \\ x^2F(x) & \leftrightarrow [0,0,f_0,f_1,\cdots] \\ (x+x^2)F(x) & \leftrightarrow [0,0,2f_2,2f_3,\cdots]\end{aligned} F(x)=∑i=0fixix⋅F(x)=∑i=1fi−1xix2⋅F(x)=∑i=2fi−2xi(x+x2)⋅F(x)=2∑i=2fixi\begin{aligned}F(x) &= \sum_{i=0}f_ix^i \\ x \cdot F(x) &= \sum_{i=1}f_{i-1}x^i \\ x^2 \cdot F(x) &= \sum_{i=2}f_{i-2}x^i \\ (x+x^2) \cdot F(x) &= 2\sum_{i=2} f_ix^i\end{aligned} x+x22F(x)+x=F(x)F(x)=2x2−x−x2\begin{aligned}\dfrac{x+x^2}{2}F(x)+x &= F(x) \\ F(x) &= \dfrac{2x}{2-x-x^2}\end{aligned}

过程和求解斐波那契数列类似，所以答案放在末尾。

【选读】我不服！——矩阵特征值硬解斐波那契数列

原先想用这个解斐波那契数列那道题，但是 55 在 mod  109+7\mod 10^9+7 意义下没有二次剩余，因此不能直接做，所以我考虑了使用矩阵特征值来用有理矩阵模拟带根号数的做法。

由于矩阵特征值不是本文的重点，所以我们简单讲一下。

若有方阵 AA 和竖向量 xx 与实数 λ\lambda 使得 Ax=λxAx =\lambda x，则我们称 λ\lambda 为矩阵 AA 的特征值。

我们对上面的式子进行一个变形：

Ax=λxAx=λIx(A−λI)x=0A−λI=0\begin{aligned}Ax &= \lambda x \\ Ax &= \lambda I x \\ (A-\lambda I)x &= 0 \\ A-\lambda I &= 0 \end{aligned}

也就是说，对于一个矩阵，我们将其对角线的值都减去 λ\lambda，若该矩阵的行列式为 00，则 λ\lambda 就是该矩阵的一个特征值。

比如 [0−110]\begin{bmatrix}0 & -1 \\ 1 & 0 \end{bmatrix} 的特征值为 ii，我们就可以将其当作矩阵运算意义下的 ii。

而 [0510]\begin{bmatrix}0 & 5 \\ 1 & 0\end{bmatrix} 的特征值为 5\sqrt{5}，所以我们可以将其当作矩阵运算意义下的 5\sqrt{5}。

我们对上面的式子做个推导：

Fi=15((1+52)n−(1−52)n)=2−n[0510]−1([1511]n−[1−5−11]n)=2−n[01150]([1511]n−[1−5−11]n)\begin{aligned}F_i &= \frac{1}{\sqrt{5}}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n) \\ &= 2^{-n} \begin{bmatrix}0 & 5 \\ 1 & 0\end{bmatrix}^{-1}(\begin{bmatrix}1 & 5 \\ 1 & 1\end{bmatrix}^n-\begin{bmatrix}1 & -5 \\ -1 & 1\end{bmatrix}^n) \\ &= 2^{-n} \begin{bmatrix}0 & 1 \\ \frac{1}{5} & 0\end{bmatrix}(\begin{bmatrix}1 & 5 \\ 1 & 1\end{bmatrix}^n-\begin{bmatrix}1 & -5 \\ -1 & 1\end{bmatrix}^n)\end{aligned}

于是套用这个公式我们就得到了斐波那契数列的另一种 O(log⁡n)O(\log n) 求法：

#include <stdio.h>

#define int long long

typedef long long i64;

const i64 mod = 1000000007;

#define maxn 2
struct matrix
{
    i64 data[maxn][maxn];
    matrix() { data[0][0] = data[0][1] = data[1][0] = data[1][1] = 0; }
    i64 *operator[](int index) { return data[index]; }
};

matrix operator*(matrix a, matrix b);
matrix pow(matrix x, i64 p);
int fpow(int x,int p);

matrix linv,ad,mi;
int n;
signed main()
{
	scanf("%lld", &n);

	linv[0][1] = 1;
	linv[1][0] = fpow(5,mod-2);
	// 1 / sqrt(5)

	ad[0][0]= 1;ad[0][1]= 5;
	ad[1][0]= 1;ad[1][1]= 1;
	//1+sqrt(5)

	mi[0][0]= 1;mi[0][1]= mod-5;
	mi[1][0]= mod-1;mi[1][1]= 1;
	//1-sqrt(5)

	ad = pow(ad,n);
	mi = pow(mi,n);

	ad[0][0] = ((ad[0][0] - mi[0][0])%mod+mod)%mod;
	ad[0][1] = ((ad[0][1] - mi[0][1])%mod+mod)%mod;
	ad[1][0] = ((ad[1][0] - mi[1][0])%mod+mod)%mod;
	ad[1][1] = ((ad[1][1] - mi[1][1])%mod+mod)%mod;
	// (1+sqrt(5))^n-(1-sqrt(5))^n

	linv = linv * ad;

	printf("%lld",linv[0][0]*fpow(fpow(2,n),mod-2)%mod);

	return 0;
}

这份代码结合了很多数学知识，如通项公式，矩阵特征值等，各位不一定要写，但是理解了一定有所收获。

牛顿二项式定理——生成函数的组合意义

生成函数不仅可以用来处理数列通项公式的问题，还可以用于解决有组合意义的一类问题。

本文章的原标题叫“求数列通项的强大工具——生成函数学习笔记”，我认为不太恰当，有点以偏概全，就改为了现在这个标题：“操作数列的强大工具——生成函数学习笔记”。

现在考虑如下一个问题：

用 11 元，33 元，55 元，77 元的硬币支付 88 元，有多少可能的方式？

这是一个背包问题，我们当然可以用背包求解。

不过，这个问题在数学意义上也有对应的说法。

我们回到背包的思路，这样思考：

定义 fi,jf_{i,j} 为前 ii 个物品，支付 jj 元的方式。

选择一个硬币，会让更高价值的方案增加，也就是 fi,j→fi+1,j+vif_{i,j} \rightarrow f_{i+1,j+v_i}，而不选择硬币，方案数不变，也就是 fi,j→fi+1,jf_{i,j} \rightarrow f_{i+1,j}。

如果我们从数学（确切地说，多项式）的角度来看呢？

初始时，支付 00 元的方案数为 11，若有物品价值为 vv，我们将答案乘上 (1+xv)(1+x^v)，相当于将答案加上答案多项式向高次移 vv 位的值，这和上面的 dp 公式不谋而合。

在乘上 nn 个物品之后，支付 rr 元的方式就是结果多项式中 xrx^r 项的系数。

比如上面的问题，它的多项式就是 (1+x)(1+x3)(1+x5)(1+x7)(1+x)(1+x^3)(1+x^5)(1+x^7)，答案就是展开后 x8x^8 项的系数。

所以，生成函数可以用于求解类似于背包的大量级数学问题，这也正是它的组合意义。

我们来看 BZOJ 上的一道题（本部分灵感 from OI-wiki，但并非完全搬运）：

例题3 BZOJ 3028 食物

在许多不同种类的食物中选出 nn 个，每种食物的限制如下： 承德汉堡：偶数个

可乐：00 个或 11 个

鸡腿：00 个，11 个或 22 个

蜜桃多：奇数个

鸡块：4 的倍数个

包子：0 个，1 个，2 个或 3 个

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

面包：3 的倍数个

每种食物都是以「个」为单位，只要总数加起来是 n 就算一种方案。对于给出的 n 你需要计算出方案数，对 10007 取模。

我们当然可以用上面的方法求解，比如“承德汉堡”的多项式就是 (1+x2+x4+⋯ )(1+x^2+x^4+\cdots)，可乐的多项式就是 1+x1+x，以此类推。

这样的话，中间会出现项数为无穷的项，如“承德汉堡”，“蜜桃多”这些，不利于我们计算，也不利于程序处理。

这个时候，不要忘了生成函数的杀手锏——封闭形式！

我们再看“承德汉堡”的多项式：

(1+x2+x4+⋯ )↔[1,0,1,0,1,0,1,⋯ ]F(x)↔[1,0,1,0,1,0,1,⋯ ]x2F(x)↔[0,0,1,0,1,0,1,⋯ ]\begin{aligned}(1+x^2+x^4+\cdots) &\leftrightarrow [1,0,1,0,1,0,1,\cdots] \\ F(x) &\leftrightarrow [1,0,1,0,1,0,1,\cdots] \\ x^2F(x) &\leftrightarrow [0,0,1,0,1,0,1,\cdots]\end{aligned} F(x)=∑i=0x2ix2F(x)=∑i=1x2ix2F(x)+1=∑i=0x2i\begin{aligned}F(x) &= \sum_{i=0}x^{2i} \\ x^2F(x) &= \sum_{i=1}x^{2i} \\ x^2F(x)+1 &= \sum_{i=0}x^{2i}\end{aligned}

即有 1+x2F(x)=F(x)1+x^2F(x) = F(x)，解得 F(x)=11−x2F(x) = \dfrac{1}{1-x^2}，而我们又知道封闭形式是等价于展开形式的，所以将它代替原来的多项式带入即可。

最后我们可以得到每种食物的多项式如下：

我们将它们全部乘起来，得到答案为 x(1−x)4\dfrac{x}{(1-x)^4}。

现在的问题在于将它展开。

可是我们没有学过这样的式子啊，我们知道乘上 11−x\dfrac{1}{1-x} 的因子代表求前缀和，所以上面这个式子就等同于数列 [0,1,0,0,0,0,⋯ ][0,1,0,0,0,0,\cdots] 的四阶前缀和，可以在线性时间内求解。

那如果我们想要一个通项公式呢？除了找规律之外，我们还能有更加理性且严谨的方式得到这个公式吗？

显然是有的，这种 (a+b)k(a+b)^k 的每一项我们可以用牛顿二项式定理求解。

牛顿二项式定理是这样的：

(a+b)k=∑i=0aibk−i(ki)(a+b)^k = \sum_{i=0}a^ib^{k-i} { {k} \choose {i} }

例如 (1+x)4=∑i=0xi(4i)(1+x)^4 = \sum_{i=0} x^i{ {4} \choose {i} }，但是这并不能解决我们的问题，因为我们实际上要展开的是 (1−x)−4(1-x)^{-4}，而组合数在我们的定义中是 (nm)=n!m!(n−m)!{ {n} \choose {m} } = \dfrac{n!}{m!(n-m)!}。阶乘只有在自然数中的定义，不符合带入负数的条件，所以我们需要修改它的定义。

如何修改呢？在我们的新定义中，仍然需要保证在自然数中组合数的值与原来相同，且 (nm){ {n} \choose {m} } 在 m>nm>n 的情况下为 00。

我们再看原来的式子：(nm)=n!m!(n−m)!{ {n} \choose {m} } = \dfrac{n!}{m!(n-m)!}，其中 n!(n−m!)=n×(n−1)×(n−2)×(n−3)×⋯×(n−m+1){\dfrac{n!}{(n-m!)}} = n \times (n-1) \times (n-2) \times (n-3) \times \cdots \times (n-m+1) 是下降幂的形式，可以简写为 nm‾n^{\underline{m}}，读作：nn 直降 mm 次。

而下降幂在整数域内都有定义，所以我们组合数的定义就可以推广了，变为 (nm)=nm‾m!{ {n} \choose {m} } = \dfrac{n^{\underline{m}}}{m!}，其中 n∈Z,m∈Nn \in \Z,m \in \N。

有了这个推广，我们就可以展开上面的式子了。

1(1−x)4=(1−x)−4=∑i=0(−x)i(−4i)=∑i=0(−1)i−4i‾i!xi=∑i=0(−1)i(−4)×(−3)×⋯×(−4−i+1)i!xi=∑i=0(−1)2i4×3×⋯×(4+i−1)i!xi=∑i=0(4+i−1)i‾i!xi=∑i=0(i+3i)xi\begin{aligned}\dfrac{1}{(1-x)^4} &= (1-x)^{-4} \\ &= \sum_{i=0} (-x)^i { {-4} \choose {i} } \\ &= \sum_{i=0} (-1)^i \dfrac{ {-4}^{\underline{i}} }{i!} x^i \\ &= \sum_{i=0} (-1)^i \dfrac{(-4)\times(-3)\times \cdots \times (-4-i+1)}{i!} x^i \\ &= \sum_{i=0} (-1)^{2i} \dfrac{4\times3\times \cdots \times (4+i-1)}{i!} x^i \\ &= \sum_{i=0} \dfrac{(4+i-1)^{\underline{i}}}{i!}x^i \\ &= \sum_{i=0} { {i+3} \choose {i} } x^i\end{aligned}

但是不要忘了原来的式子是 x(1−x)4\dfrac{x}{(1-x)^4}，所以我们最后再转化一下：

1(1−x)4=∑i=0(i+3i)xix(1−x)4=∑i=0((i+1)+2(i+1)−1)x(i+1)=∑i=0(i+2i−1)xi=∑i=0(i+23)xi\begin{aligned}\dfrac{1}{(1-x)^4} &= \sum_{i=0} { {i+3} \choose {i} } x^i \\ \dfrac{x}{(1-x)^4} &= \sum_{i=0} { {(i+1)+2} \choose {(i+1)-1} } x^{(i+1)} \\ &= \sum_{i=0} { {i+2} \choose {i-1} } x^{i} \\ &= \sum_{i=0} { {i+2} \choose {3} } x^{i} \end{aligned}

所以选出 nn 项的方案数就为 (n+23){ {n+2} \choose {3} }，线性推一下即可。

例题4 P2000 拯救世界

题意有精简。

要摆两个阵，求用的石子数量为 nn 时可能的摆阵方案。

第一个阵的限制：

  • 金神石的块数必须是 66 的倍数；
  • 木神石最多用 99 块；
  • 水神石最多用 55 块；
  • 火神石的块数必须是 44 的倍数；
  • 土神石最多用 77 块。

第二个阵的限制：

  • 金神石的块数必须是 22 的倍数；
  • 木神石最多用 11 块；
  • 水神石的块数必须是 88 的倍数；
  • 火神石的块数必须是 1010 的倍数；
  • 土神石最多用 33 块。

和食物那道题是一样的。

我们列出所有生成函数的封闭形式（从上到下）：

1+x6+x12+⋯=11−x61+x+x2+⋯+x9=1−x101−x1+x+x2+x3+x4+x5=1−x61−x1+x4+x8+⋯=11−x41+x+x2+⋯+x7=1−x81−x1+x2+x4+x6+⋯=11−x21+x=1−x21−x1+x8+x16+x24=11−x81+x10+x20+x30=11−x101+x+x2+x3=1−x41−x\begin{aligned}1+x^6+x^{12}+\cdots &= \dfrac{1}{1-x^6} \\ 1+x+x^2+\cdots+x^9 &= \dfrac{1-x^{10}}{1-x} \\ 1+x+x^2+x^3+x^4+x^5 &= \dfrac{1-x^6}{1-x} \\ 1+x^4+x^8+\cdots &= \dfrac{1}{1-x^4} \\ 1+x+x^2+\cdots+x^7 &= \dfrac{1-x^8}{1-x} \\ \\ 1+x^2+x^4+x^6+\cdots &= \dfrac{1}{1-x^2} \\ 1+x &= \dfrac{1-x^2}{1-x} \\ 1+x^8+x^{16}+x^{24} &= \dfrac{1}{1-x^8} \\ 1+x^{10}+x^{20}+x^{30} &= \dfrac{1}{1-x^{10}} \\ 1+x+x^2+x^3 &= \dfrac{1-x^4}{1-x}\end{aligned}

将它们乘起来，我们就得到了 1(1−x)5\dfrac{1}{(1-x)^5}，接下来像上面一样展开就好了，答案在本文末尾。

例题5 ABC276G Count Sequences

翻译来源于洛谷题目，思路与该题目使用生成函数的题解类似。

计算有多少个 NN 个元素的数组 A=(a1,...,aN)A = (a_1,...,a_N) 满足以下条件，并且将结果对 998244353998244353 取模。

2≤N≤107,1≤M≤1072 \le N \le 10^7,1 \le M \le 10^7

我们先考虑最基本的 dp，定义 fi,jf_{i,j} 为数列长度为 ii，数列最后一个数为 jj 时的答案，则我们的转移应该写成：

fi,j={1i=1∑k∈[0,j],3∤(j−k)otherwise⁡f_{i,j} = \begin{cases} & 1 & i=1 \\ & \sum_{k \in [0,j],3 \nmid (j-k)} & \operatorname{otherwise} \end{cases}

答案就是 ∑j=0mfn,j\sum_{j=0}^m f_{n,j}。

这个 dp 太慢了，不过全程递推式，应该可以用生成函数进行优化。

定义 Fi(x)F_i(x) 为数列 [fi,0,fi,1,fi,2,fi,3,⋯ ][f_{i,0},f_{i,1},f_{i,2},f_{i,3},\cdots] 的普通生成函数，则我们可以得到 Fi(x)↔[1,1,1,1,⋯ ]↔11−xF_i(x) \leftrightarrow [1,1,1,1,\cdots] \leftrightarrow \dfrac{1}{1-x}。

那剩下的部分呢？我们发现 3∤(j−k)3 \nmid (j-k) 这个式子实际上就是在要求转移过来的位和当前位不能间隔 33 的倍数，也就是说可以从上 11 位，上 22 位，上 44 位，上 55 位，上 77 位等转移过来。

也就是说在 i≠1i \neq 1 的情况下，Fi(x)=(x+x2+x4+x5+x7+x8+⋯ )Fi−1(x)F_i(x) = (x+x^2+x^4+x^5+x^7+x^8+\cdots)F_{i-1}(x)

同样将展开形式化成封闭形式：

x+x2+x4+x5+x7+x8+⋯↔[1,1,1,0,1,1,0,1,1,0,⋯ ]F(x)↔[0,1,1,0,1,1,0,1,1,0,⋯ ]x3F(x)↔[0,0,0,0,1,1,0,1,1,0,⋯ ]\begin{aligned}x+x^2+x^4+x^5+x^7+x^8+\cdots &\leftrightarrow [1,1,1,0,1,1,0,1,1,0,\cdots] \\ F(x) &\leftrightarrow [0,1,1,0,1,1,0,1,1,0,\cdots] \\ x^3F(x) &\leftrightarrow [0,0,0,0,1,1,0,1,1,0,\cdots] \end{aligned} F(x)=∑i=0x3i+1+∑i=0x3i+2x3F(x)=∑i=1x3i+1+∑i=1x3i+2x3F(x)+x2+x=(x+∑i=1x3i+1)+(x2+∑i=1x3i+1)=∑i=0x3i+1+∑i=0x3i+2=F(x)\begin{aligned}F(x) &= \sum_{i=0}x^{3i+1} + \sum_{i=0}x^{3i+2} \\ x^3F(x) &= \sum_{i=1}x^{3i+1} + \sum_{i=1}x^{3i+2} \\ x^3F(x) + x^2 + x &= (x+\sum_{i=1}x^{3i+1}) + (x^2+\sum_{i=1}x^{3i+1}) &= \sum_{i=0}x^{3i+1} + \sum_{i=0}x^{3i+2} = F(x) \end{aligned} x3F(x)+x+x2=F(x)x2+x=(1−x3)F(x)F(x)=x2+x1−x3\begin{aligned}x^3F(x)+x+x^2 &= F(x) \\ x^2+x &= (1-x^3)F(x) \\ F(x) &= \dfrac{x^2+x}{1-x^3}\end{aligned}

所以我们的生成函数递推式如下：

Fi(x)={11−xi=1x2+x1−x3Fi−1(x)otherwise⁡F_i(x) = \begin{cases}&\dfrac{1}{1-x} &i=1 \\ &\dfrac{x^2+x}{1-x^3}F_{i-1}(x) & \operatorname{otherwise}\end{cases}

所以 Fn(x)=11−x(x2+x1−x3)n−1F_n(x) = \dfrac{1}{1-x}(\dfrac{x^2+x}{1-x^3})^{n-1}，答案就是 ∑j=0m[xj]Fn(x)\sum_{j=0}^m [x^j]F_n(x)。

这个地方大家想到了什么？前缀和！所以我们可以通过乘上 11−x\dfrac{1}{1-x} 来优化，然后就是化简式子。

∑j=0m[xj]Fn(x)=[xm]1(1−x)2(x2+x1−x3)n−1=[xm]1(1−x)2(x(x+1)1−x3)n−1=[xm−n+1]1(1−x)2(x+11−x3)n−1=[xm−n+1]1(1−x)2(x+1)n−11(1−x3)n−1\begin{aligned}\sum_{j=0}^m [x^j]F_n(x)&=[x^m]\dfrac{1}{(1-x)^2}(\dfrac{x^2+x}{1-x^3})^{n-1} \\ &= [x^m]\dfrac{1}{(1-x)^2}(\dfrac{x(x+1)}{1-x^3})^{n-1} \\ &= [x^{m-n+1}]\dfrac{1}{(1-x)^2}(\dfrac{x+1}{1-x^3})^{n-1} \\ &= [x^{m-n+1}]\dfrac{1}{(1-x)^2}(x+1)^{n-1}\dfrac{1}{(1-x^3)^{n-1}}\end{aligned}

式子就这样被拆成了三段。第一段是对数列进行二阶前缀和，而第二段第三段都是组合数的形式，我们需要求出它们卷积后的二阶前缀和的 xm−n−1x^{m-n-1} 次项，同样也可以求出先对一个数列进行二阶前缀和再卷积的 xm−n−1x^{m-n-1} 次项，复杂度是线性的，可以通过本题。

那么接下来我们来看 (x+1)n−1(x+1)^{n-1} 和 1(1−x3)n−1\dfrac{1}{(1-x^3)^{n-1}} 该如何化简，使用广义牛顿二项式定理即可，答案和详细的推导过程会放在文章末尾，你……要不要自己试试？

结语

感谢您耐心读到这里。

其实生成函数的用法远不止于此，但碍于时间和篇幅，我只能写到这里了，参考资料里有很多我认为很优秀的资料，也欢迎大家进一步学习。

那就先到这里了，拜拜。

参考资料

其实我觉得参考资料比我讲得好。

因为 B 站的强制搜索追踪缘故，这里只给了 bvid。

普通生成函数 - OI Wiki

生成函数论：第一章 入门概念和例子（1）生成函数的基本方法 - 知乎 (zhihu.com)

【乱写】浅谈生成函数 - 知乎 (zhihu.com)

[算法竞赛入门] 生成函数：函数与数列之间的桥梁 (蒋炎岩) BV16X4y1N74M

到底什么是“闭合解（Closed-form Solution）” - 知乎 (zhihu.com)

《具体数学 计算机科学基础（第二版）》 Ronald L. Graham , Donald E.Knuth , Oren Patashnik

【【官方双语/合集】线性代数的本质 - 系列合集】 BV1ys411472E

练习答案

例题1

A=[0,1,2,3,4,⋯ ],Ai=iA = [0,1,2,3,4,\cdots],A_i = i

发现 A=[0,1,1,1,⋯ ]∗1A = [0,1,1,1,\cdots] * 1，所以 F(x)=x(1−x)2F(x) = \frac{x}{(1-x)^2}。

A=[0,2,4,6,8,10,⋯ ],Ai=2iA = [0,2,4,6,8,10,\cdots],A_i = 2i

就是上一个的结果乘 22。

A=[0,1,4,9,16,25,36,⋯ ],Ai=i2A = [0,1,4,9,16,25,36,\cdots],A_i = i^2

发现 (a+1)2=a2+2a+1(a+1)^2 = a^2 + 2a + 1，所以 Ai+1=2Ai+2i+1A_{i+1} = 2A_i + 2i + 1。

x1−x↔[0,1,1,1,⋯ ]2x2(1−x)2↔[0,0,2,4,6,8,⋯ ]F(x)↔[0,1,4,9,16,⋯ ]xF(x)↔[0,0,1,4,9,16,⋯ ]\begin{aligned}\frac{x}{1-x} &\leftrightarrow [0,1,1,1,\cdots] \\ \frac{2x^2}{(1-x)^2} &\leftrightarrow [0,0,2,4,6,8,\cdots] \\ F(x) &\leftrightarrow [0,1,4,9,16,\cdots] \\ xF(x) &\leftrightarrow [0,0,1,4,9,16,\cdots] \end{aligned} F(x)=∑i=0i2xix⋅F(x)=∑i=1(i−1)2xi=∑i=1(i2−2i+1)xi=∑i=1i2xi−2∑i=1ixi+∑i=1xi=F(x)−2x(1−x)2+x1−x\begin{aligned}F(x) &= \sum_{i=0}i^2x^i \\ x\cdot F(x) &= \sum_{i=1}(i-1)^2x^i \\ &= \sum_{i=1}(i^2-2i+1)x^i \\ &= \sum_{i=1}i^2x^i - 2\sum_{i=1}ix^i + \sum_{i=1}x^i \\ &= F(x) - 2\dfrac{x}{(1-x)^2} + \dfrac{x}{1-x}\end{aligned} xF(x)+x1−x+2x2(1−x)2=F(x)x2+x(1−x)2=(1−x)F(x)F(x)=x2+x(1−x)3\begin{aligned}xF(x) + \frac{x}{1-x} + \frac{2x^2}{(1-x)^2} &= F(x) \\ \frac{x^2+x}{(1-x)^2} &= (1-x)F(x) \\ F(x) &= \frac{x^2+x}{(1-x)^3}\end{aligned} A=[1,1,2,3,5,8,⋯ ],Ai=Ai−1+Ai−2,A0=1A = [1,1,2,3,5,8,\cdots],A_i = A_{i-1}+A_{i-2},A_0=1

因为 Ai=Ai−1+Ai−2A_i = A_{i-1} + A_{i-2}，所以我们考虑如下构造：

F(x)↔[0,1,1,2,3,5,8,⋯ ]xF(x)↔[0,0,1,1,2,3,5,8,⋯ ]x2F(x)↔[0,0,0,1,1,2,3,5,8,⋯ ]\begin{aligned}F(x) &\leftrightarrow [0,1,1,2,3,5,8,\cdots] \\ xF(x) &\leftrightarrow [0,0,1,1,2,3,5,8,\cdots] \\ x^2F(x) &\leftrightarrow [0,0,0,1,1,2,3,5,8,\cdots] \end{aligned} F(x)=∑i=0Aixix⋅F(x)=∑i=1Ai−1xix2⋅F(x)=∑i=2Ai−2xi(x+x2)F(x)=∑i=1Aixi\begin{aligned}F(x) &= \sum_{i=0}A_ix^i \\ x \cdot F(x) &= \sum_{i=1}A_{i-1}x^i \\ x^2 \cdot F(x) &= \sum_{i=2}A_{i-2}x^i \\ (x+x^2)F(x) &= \sum_{i=1}A_ix^i\end{aligned} F(x)=xF(x)+x2F(x)+x(1−x−x2)F(x)=xF(x)=x1−x−x2\begin{aligned}F(x) &= xF(x) + x^2 F(x) + x \\ (1-x-x^2)F(x) &= x \\ F(x) &= \frac{x}{1-x-x^2} \end{aligned}

例题2 某年的初赛真题 答案

还是先因式分解：

2−x−x2=−(x−1)(x+2)2-x-x^2 = -(x-1)(x+2) 2x2−x−x2=a1−x+bx+22x=(x+2)a+(1−x)b2x=x(a−b)+(2a+b)\begin{aligned}\dfrac{2x}{2-x-x^2} &= \dfrac{a}{1-x} + \dfrac{b}{x+2} \\ 2x &= (x+2)a+(1-x)b \\ 2x &= x(a-b) + (2a+b)\end{aligned}

则有 {a−b=22a+b=0\begin{cases}a-b = 2 \\ 2a+b = 0\end{cases}，解得 {a=23b=−43\begin{cases}a = \frac{2}{3} \\ b = -\frac{4}{3}\end{cases}，带回原式子算：

F(x)=231−x+−43x+2=231−x+−432−(−1)x=231−x+−231−(−12)x\begin{aligned}F(x) &= \dfrac{\dfrac{2}{3}}{1-x} + \dfrac{-\dfrac{4}{3}}{x+2} \\ &= \dfrac{\dfrac{2}{3}}{1-x} + \dfrac{-\dfrac{4}{3}}{2-(-1)x} \\ &= \dfrac{\dfrac{2}{3}}{1-x} + \dfrac{-\dfrac{2}{3}}{1-(-\dfrac{1}{2})x}\end{aligned}

结合上面讲过的等比数列生成函数，我们就得到了：

fn=[xn]F(x)=23−23(−12)nf_n = [x^n]F(x) = \dfrac{2}{3} - \dfrac{2}{3} (-\dfrac{1}{2})^n

在 nn 趋于无穷大时，第二项趋于 00，所以数列的值趋近于 23\dfrac{2}{3}。

例题4 P2000 拯救世界 答案

三道题的套路其实是一样的。

1(1−x5)=(1−x)−5=∑i=0(−5i)(−x)i=∑i=0(−1)i−5i‾i!xi=∑i=0(−1)i−5×(−5−1)×(−5−2)⋯×(−5−i+1)i!xi=∑i=0(−1)2i5×(5+1)×(5+2)⋯×(5+i−1)i!xi=∑i=0(5+i−1)i‾i!xi=∑i=0(4+i4)xi\begin{aligned}\dfrac{1}{(1-x^5)} &= (1-x)^{-5} \\ &= \sum_{i=0} { {-5} \choose {i} }(-x)^i \\ &= \sum_{i=0}(-1)^i \dfrac{ {-5}^{\underline{i}} }{i!}x^i \\ &= \sum_{i=0}(-1)^i \dfrac{ -5 \times (-5-1) \times (-5-2) \cdots \times (-5-i+1) }{i!}x^i \\ &= \sum_{i=0}(-1)^{2i} \dfrac{ 5 \times (5+1) \times (5+2) \cdots \times (5+i-1) }{i!}x^i \\ &= \sum_{i=0} \dfrac{ (5+i-1)^{\underline{i}} }{i!}x^i \\ &= \sum_{i=0} { {4+i} \choose {4} }x^i \end{aligned}

例题5 ABC276G Count Sequences 答案

(x+1)n−1=∑i=0(n−1i)xi(x+1)^{n-1} = \sum_{i=0}{ {n-1} \choose {i} }x^i 1(1−x3)n−1=(1−x3)1−n=∑i=0(1−ni)(−x)3i=(−1)i∑i=0(1−n)i‾i!x3i=(−1)i∑i=0(1−n)(1−n−1)(1−n−2)⋯(1−n−i+1)i!x3i=(−1)2i∑i=0(n−1)(n+1−1)(n+2−1)⋯(n+i−2)i!x3i=∑i=0(n+i−2)i‾i!x3i=∑i=0(n+i−2i)x3i=∑i=0(n+i−2n−2)x3i\begin{aligned}\dfrac{1}{(1-x^3)^{n-1}} &= (1-x^3)^{1-n} \\ &= \sum_{i=0}{ {1-n} \choose {i} }(-x)^{3i} \\ &= (-1)^i \sum_{i=0}\dfrac{(1-n)^{\underline{i}}}{i!}x^{3i} \\ &= (-1)^i \sum_{i=0}\dfrac{(1-n)(1-n-1)(1-n-2)\cdots(1-n-i+1)}{i!}x^{3i} \\ &= (-1)^{2i} \sum_{i=0}\dfrac{(n-1)(n+1-1)(n+2-1)\cdots(n+i-2)}{i!}x^{3i} \\ &= \sum_{i=0}\dfrac{(n+i-2)^{\underline{i}}}{i!}x^{3i}\\ &= \sum_{i=0}{ {n+i-2} \choose {i} }x^{3i}\\ &= \sum_{i=0}{ {n+i-2} \choose {n-2} }x^{3i}\end{aligned}


在 Rickyxrc's blog 出现的文章，若无特殊注明，均采用 CC BY-NC-SA 4.0 协议共享，也就是转载时需要注明本文章的地址，并且引用本文章的文章也要使用相同的方式共享。