Skip to content

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

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+63x+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)=11xF(x) = \frac{1}{1-x}

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

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

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

第二种表达形式:F(x)=11x=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=Ai1+Ai2,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}

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

让我先急。

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

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

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

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

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

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

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

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

加法/减法

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

乘法?

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

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

很神奇是不是,为什么呢?

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

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

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

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

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

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

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

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

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

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

首先将 1xx21-x-x^2 因式分解(也就是求出它的根),得到 (x1+52)(x152)-(x-\frac{1+\sqrt{5}}{2})(x-\frac{1-\sqrt{5}}{2})

再应用待定系数法,列出方程:

x(x1+52)(x152)=ax1+52+bx152\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(x1+52)(x152)=(x152)a(x1+52)(x152)+(x1+52)b(x1+52)(x152)\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=axaa52+bxb+b52-x = ax - \frac{a-a\sqrt{5}}{2} + bx - \frac{b+b\sqrt{5}}{2}

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

{aa52+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=5510\begin{cases}a=-\frac{5+\sqrt{5}}{10} \\ b=\frac{\sqrt{5}-5}{10}\end{cases}

也就是说,F(x)=5+510x1+52+5510x152F(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,]xF(x)[0,a,aq,aq2,aq3,]qxF(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=0aqixixF(x)=i=0aaixi+1=i=1aqi1xiqxF(x)=i=1aqixiqxF(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}

则我们得到了:

qxF(x)+a=F(x)(qx1)F(x)=aF(x)=a1qx\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+510x1+52+5510x152F(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)=15121+5x+151215xF(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}})^iBi=15(215)iB_i = -\frac{1}{\sqrt{5}} \cdot (\frac{2}{1-\sqrt{5}})^i,我们将其求和便得到了通项公式:

Fi=15((21+5)i+(215)i)Fi=15((1+52)i(152)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 某年的初赛真题

有数列 fff0=0,f1=1,fi=fi1+fi22f_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=0fixixF(x)=i=1fi1xix2F(x)=i=2fi2xi(x+x2)F(x)=2i=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)=2x2xx2\begin{aligned}\dfrac{x+x^2}{2}F(x)+x &= F(x) \\ F(x) &= \dfrac{2x}{2-x-x^2}\end{aligned}

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

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

原先想用这个解斐波那契数列那道题,但是 55mod109+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 就是该矩阵的一个特征值。

比如 [0110]\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(152)n)=2n[0510]1([1511]n[1511]n)=2n[01150]([1511]n[1511]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(logn)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,jfi+1,j+vif_{i,j} \rightarrow f_{i+1,j+v_i},而不选择硬币,方案数不变,也就是 fi,jfi+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)=11x2F(x) = \dfrac{1}{1-x^2},而我们又知道封闭形式是等价于展开形式的,所以将它代替原来的多项式带入即可。

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

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

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

可是我们没有学过这样的式子啊,我们知道乘上 11x\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=0aibki(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} },但是这并不能解决我们的问题,因为我们实际上要展开的是 (1x)4(1-x)^{-4},而组合数在我们的定义中是 (nm)=n!m!(nm)!{ {n} \choose {m} } = \dfrac{n!}{m!(n-m)!}。阶乘只有在自然数中的定义,不符合带入负数的条件,所以我们需要修改它的定义。

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

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

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

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

1(1x)4=(1x)4=i=0(x)i(4i)=i=0(1)i4ii!xi=i=0(1)i(4)×(3)××(4i+1)i!xi=i=0(1)2i4×3××(4+i1)i!xi=i=0(4+i1)ii!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(1x)4\dfrac{x}{(1-x)^4},所以我们最后再转化一下:

1(1x)4=i=0(i+3i)xix(1x)4=i=0((i+1)+2(i+1)1)x(i+1)=i=0(i+2i1)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+=11x61+x+x2++x9=1x101x1+x+x2+x3+x4+x5=1x61x1+x4+x8+=11x41+x+x2++x7=1x81x1+x2+x4+x6+=11x21+x=1x21x1+x8+x16+x24=11x81+x10+x20+x30=11x101+x+x2+x3=1x41x\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(1x)5\dfrac{1}{(1-x)^5},接下来像上面一样展开就好了,答案在本文末尾。

例题5 ABC276G Count Sequences

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

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

2N107,1M1072 \le N \le 10^7,1 \le M \le 10^7

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

fi,j={1i=1k[0,j],3(jk)otherwisef_{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,]11xF_i(x) \leftrightarrow [1,1,1,1,\cdots] \leftrightarrow \dfrac{1}{1-x}

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

也就是说在 i1i \neq 1 的情况下,Fi(x)=(x+x2+x4+x5+x7+x8+)Fi1(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=(1x3)F(x)F(x)=x2+x1x3\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)={11xi=1x2+x1x3Fi1(x)otherwiseF_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)=11x(x2+x1x3)n1F_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)

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

j=0m[xj]Fn(x)=[xm]1(1x)2(x2+x1x3)n1=[xm]1(1x)2(x(x+1)1x3)n1=[xmn+1]1(1x)2(x+11x3)n1=[xmn+1]1(1x)2(x+1)n11(1x3)n1\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}

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

那么接下来我们来看 (x+1)n1(x+1)^{n-1}1(1x3)n1\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(1x)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

x1x[0,1,1,1,]2x2(1x)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=0i2xixF(x)=i=1(i1)2xi=i=1(i22i+1)xi=i=1i2xi2i=1ixi+i=1xi=F(x)2x(1x)2+x1x\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)+x1x+2x2(1x)2=F(x)x2+x(1x)2=(1x)F(x)F(x)=x2+x(1x)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=Ai1+Ai2,A0=1A = [1,1,2,3,5,8,\cdots],A_i = A_{i-1}+A_{i-2},A_0=1

因为 Ai=Ai1+Ai2A_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=0AixixF(x)=i=1Ai1xix2F(x)=i=2Ai2xi(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(1xx2)F(x)=xF(x)=x1xx2\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 某年的初赛真题 答案

还是先因式分解:

2xx2=(x1)(x+2)2-x-x^2 = -(x-1)(x+2)
2x2xx2=a1x+bx+22x=(x+2)a+(1x)b2x=x(ab)+(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}

则有 {ab=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)=231x+43x+2=231x+432(1)x=231x+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)=2323(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(1x5)=(1x)5=i=0(5i)(x)i=i=0(1)i5ii!xi=i=0(1)i5×(51)×(52)×(5i+1)i!xi=i=0(1)2i5×(5+1)×(5+2)×(5+i1)i!xi=i=0(5+i1)ii!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)n1=i=0(n1i)xi(x+1)^{n-1} = \sum_{i=0}{ {n-1} \choose {i} }x^i
1(1x3)n1=(1x3)1n=i=0(1ni)(x)3i=(1)ii=0(1n)ii!x3i=(1)ii=0(1n)(1n1)(1n2)(1ni+1)i!x3i=(1)2ii=0(n1)(n+11)(n+21)(n+i2)i!x3i=i=0(n+i2)ii!x3i=i=0(n+i2i)x3i=i=0(n+i2n2)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 协议共享,也就是转载时需要注明本文章的地址,并且引用本文章的文章也要使用相同的方式共享。