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

rickyxrc · 2023-08-06 19:38:29 · 算法·理论

写在前面：这篇文章是初学的时候写的，有很多地方使用了不标准的记号。

另外推荐一篇写得很好的文章：https://www.luogu.com/article/oy8l7j3n

已经退役，不会再有更新，错误也大概率不会再修正，抱歉。

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

不知道对高考数学有没有用。 事实上应该没有。

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

前言

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

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

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

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

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

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

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

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

• 序列 A = [1,1,1, \cdots ] 的形式幂级数为 \sum_{i=0}x^i。
• 序列 A = [1,2,3,\cdots] 的形式幂级数为 \sum_{i=0}ix^i。

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

再简单一点——封闭形式

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

答案和解析在文章末尾。

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

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

让我先急。

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

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

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

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

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

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

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

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

加法/减法

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

乘法？

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

将式子通分，得到

也就是

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

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

也就是说，F(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) = \frac{-\frac{\sqrt{5}+5}{10}}{x-\frac{1+\sqrt{5}}{2}} + \frac{\frac{\sqrt{5}-5}{10}}{x-\frac{1-\sqrt{5}}{2}} 这个式子，我们得到了：

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

例题2 某年的初赛真题

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

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

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

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

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

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

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

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

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

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

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

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

于是套用这个公式我们就得到了斐波那契数列的另一种 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;
}

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

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

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

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

现在考虑如下一个问题：

用 1 元，3 元，5 元，7 元的硬币支付 8 元，有多少可能的方式？

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

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

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

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

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

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

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

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

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

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

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

例题3 BZOJ 3028 食物

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

可乐：0 个或 1 个

鸡腿：0 个，1 个或 2 个

蜜桃多：奇数个

鸡块：4 的倍数个

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

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

面包：3 的倍数个

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

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

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

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

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

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

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

• 承德汉堡：\dfrac{1}{1-x^2}
• 可乐：1+x
• 鸡腿：1+x+x^2 = \dfrac{1-x^3}{1-x}（因为我们要将多项式乘起来，所以因式分解是明智的选择）
• 蜜桃多：1+x+x^3+x^5+x^7+\cdots = \dfrac{x}{1-x^2}
• 鸡块：1+x^4+x^8+x^{12}+\cdots = \dfrac{1}{1-x^4}
• 包子：1+x+x^2+x^3 = \dfrac{1-x^4}{1-x}
• 土豆片炒肉：1+x
• 面包：1+x^3+x^6+x^9+\cdots = \dfrac{1}{1-x^3}

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

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

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

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

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

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

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

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

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

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

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

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

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

例题4 P2000 拯救世界

题意有精简。

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

第一个阵的限制：

• 金神石的块数必须是 6 的倍数；
• 木神石最多用 9 块；
• 水神石最多用 5 块；
• 火神石的块数必须是 4 的倍数；
• 土神石最多用 7 块。

第二个阵的限制：

• 金神石的块数必须是 2 的倍数；
• 木神石最多用 1 块；
• 水神石的块数必须是 8 的倍数；
• 火神石的块数必须是 10 的倍数；
• 土神石最多用 3 块。

和食物那道题是一样的。

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

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

例题5 ABC276G Count Sequences

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

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

• 0 \le a_1 \le a_2 \le...\le a_N \le M
• 对于每一个 i = 1,2,..,N-1，满足 a_i 和 a_{i+1} 对 3 取模的余数不同。

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

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

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

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

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

也就是说在 i \neq 1 的情况下，F_i(x) = (x+x^2+x^4+x^5+x^7+x^8+\cdots)F_{i-1}(x)

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

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

所以 F_n(x) = \dfrac{1}{1-x}(\dfrac{x^2+x}{1-x^3})^{n-1}，答案就是 \sum_{j=0}^m [x^j]F_n(x)。

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

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

那么接下来我们来看 (x+1)^{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,1,1,\cdots] * 1，所以 F(x) = \frac{x}{(1-x)^2}。

就是上一个的结果乘 2。

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

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

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

还是先因式分解：

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

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

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

例题4 P2000 拯救世界 答案

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

例题5 ABC276G Count Sequences 答案