如果你认真备过赛，多半会听过一句话：生成函数是计数题的终极武器。我第一次认真学它，是被一道递推题逼的。当时那道题的递推式里有多个系数，写矩阵快速幂写到一半发现矩阵维度稍高就变得很笨重，我就在想，有没有一种更"通吃"的办法。后来用了生成函数，很多看似烧脑的计数题突然变成三件事：把序列写成级数、用代数方程解出封闭形式、再把系数展开回来。这个专题我断断续续整理了很久，今天这篇就当总结笔记，从原理讲到上机，把该踩的坑尽量都写出来。
这篇内容适合正在备赛ACM的同学，也适合学了多项式但还没想清楚生成函数怎么用的朋友。你不需要有很深的基础，只要会一点多项式乘法、知道组合数怎么算，跟着走一遍就能上手。本文会覆盖OGF和EGF两条路线、必背的封闭式、几类经典题型的完整推导，以及NTT和多项式求逆的实操代码，最后是我平时用来debug的一堆经验。
1. 生成函数到底在解决什么问题
1.1 从递推数列说起
生成函数的核心思路并不玄乎。对于一个数列 (a_0, a_1, a_2, \dots)，我们把它包装成一个形式幂级数：
[ A(x)=\sum_{n\ge 0} a_n x^n ]
这叫普通生成函数，英文简称OGF。这里 (x) 只是一个形式符号，我们不关心它等于几，只关心它的指数和系数。
为什么要把数列包装成级数？因为很多数列都有递推关系，而递推关系写成级数之后，会变成关于 (A(x)) 的代数方程。解方程总比盯着递推式猜通项要机械得多。
举最经典的斐波那契例子。设 (F_0=0,F_1=1,F_n=F_{n-1}+F_{n-2})，令：
[ F(x)=\sum_{n\ge 0}F_n x^n ]
然后做一步关键操作：把 (F(x)) 减去 (xF(x)) 减去 (x^2F(x))。用到的原理是，乘以一次 (x) 会整体右移一项，恰好把递推式中下标差1的项对齐。整理后只有常数项和一次项剩下，其他项全因为递推关系抵消：
[ F(x)-xF(x)-x^2F(x)=x ]
所以：
[ F(x)=\frac{x}{1-x-x^2} ]
原本需要矩阵快速幂求的第n项，现在变成"对一个有理分式展开取系数"。这就是生成函数解决递推问题的最基本流程。
1.2 OGF与EGF：两条路线
OGF处理的是无标号对象，系数直接就是答案。比如若干个苹果和香蕉的组合，选3个苹果2个香蕉这类问题，乘积里每一项的自变量指数对应个数，系数对应方案数。
但算法竞赛里还有大量"有标号"对象：排列、有编号的节点、带标号的树。两种苹果的"选与不选"无所谓谁是谁，但两个编号不同的节点如果互换，方案算不同。这个时候普通生成函数会很难处理，需要换指数生成函数，英文简称EGF：
[ A(x)=\sum_{n\ge 0} a_n \frac{x^n}{n!} ]
这个除以 (n!) 不是多此一举，它让两个EGF相乘时，系数里自然冒出组合数，恰好对应"给两边选标号"的过程。我在第3章会拿错排问题详细演示，现在只需要记住判断口诀：无标号用OGF，有标号用EGF。
1.3 为什么值得投入时间
不少同学觉得生成函数是数学竞赛内容，ACM里很少考。这个想法我一度也有，但后来发现，现在很多计数题表面上是组合数学题，本质就是生成函数展开。尤其当题目里出现"长度为n的序列""把n个东西分成若干组""不超过m个某物体"这类条件时，生成函数几乎是最自然的建模语言。
另一个实际收益是它和多项式算法结合得非常紧。普通写法可能要 (O(n\sqrt n)) 甚至 (O(n^2)) 的DP，换成生成函数后很多都能用NTT优化到 (O(n\log n))。当你已经会NTT、多项式求逆、多项式exp这些工具时，生成函数就是让它们发挥威力的那个主战场。
2. 核心数学原理与常用操作
2.1 五个最常用的生成函数操作
用生成函数解题，本质是在做级数的代数运算。下面这五个操作我几乎每题都用，建议背下来。
第一，平移。如果 (B(x)=x^k A(x))，那么 (b_n=a_{n-k})。这用于处理递推式的边界项，比如斐波那契的 (F_1-F_0) 就是这么来的。
第二，前缀和。如果 (b_n=\sum_{i=0}^n a_i)，则：
[ B(x)=\frac{A(x)}{1-x} ]
因为除以 (1-x) 等价于乘上 (1+x+x^2+\cdots)，每乘一次 (x^k) 就贡献一次前缀和。反过来，想从原数列做差得到 (b_n=a_n-a_{n-1})，就乘 ((1-x))。
第三，乘以下标。如果 (b_n=n a_n)，则：
[ B(x)=x\frac{d}{dx}A(x) ]
这个用起来很顺手，尤其在处理期望时会出现。顺便一提，概率题的生成函数 (P(x)) 在 (x=1) 处取值是总概率1，而期望 (E[X]=P'(1))。
第四，卷积。这是最重要的一条。两个数列的卷积：
[ c_n=\sum_{i=0}^n a_i b_{n-i} ]
恰好对应OGF的乘积 (C(x)=A(x)B(x))。很多组合计数"先选一部分再选另一部分"的结构，写出来就是一个卷积。
第五，隔项与奇偶项提取。想从一个级数里只取偶数项对应系数，可以用 (\frac{A(x)+A(-x)}{2})，奇数项用 (\frac{A(x)-A(-x)}{2})。这招偶尔在期望题和容斥题里能救命。
2.2 必背的展开式与封闭式清单
下面这张表是我做题时翻得最多的一张表。没有它们，很多生成函数推到一半就卡住。
| 生成函数 | 展开结果 | 使用场景 |
|---|---|---|
| (\frac{1}{1-x}) | (1+x+x^2+\cdots) | 无限个同种物品 |
| (\frac{1}{1-x^{k}}) | 只含指数为k的倍数项 | 物品大小固定为k |
| (\frac{1}{(1-x)^{m+1}}) | (\sum C(n+m,m)x^n) | 多重组合数 |
| (\ln\frac{1}{1-x}) | (\sum \frac{x^n}{n}) | 环与连分数相关 |
| (\frac{x}{1-x-x^2}) | 斐波那契数列 | 线性递推典型例子 |
| (\frac{1-\sqrt{1-4x}}{2x}) | 卡特兰数 | 二叉树、括号序列 |
| (\frac{e^{-x}}{1-x}) | 错排数的EGF | 有标号乱序排列 |
注意，几乎所有求和上限都是无穷大，但程序里我们只关心前N项，所以到具体实现时都变成"截断到 (x^N)"的多项式运算。
2.3 从生成函数回到通项的三种手段
生成函数写得再漂亮，最后还是要拿系数。有三种常用路线。
第一种是部分分式分解。比如斐波那契的 (\frac{x}{1-x-x^2}) 可以分解成两个一次分式的和，再套用 (\frac{1}{1-cx}=\sum c^n x^n)，直接得到含根号的通项公式。
第二种是匹配已知展开式。卡特兰数的封闭形式化成二项式展开后，系数能直接写成组合数形式。这需要熟悉广义二项式定理：
[ (1-x)^{-m}=\sum_{n\ge0}\binom{n+m-1}{m-1}x^n ]
第三种是只算前N项的系数。竞赛题目大多只要求输出取模后的系数，不需要解析通项。这时候直接把生成函数当成多项式，用NTT做乘法、用牛顿迭代做逆元和exp，截断边界即可。后面第4章写的就是这条路线。
3. 三组经典题型的完整拆解
3.1 整数划分：生成函数与背包的相遇
整数划分问题是生成函数最经典的入门题之一。把正整数 (n) 拆成若干个正整数之和，顺序无关，求方案数 (p(n))。
它的生成函数是：
[ P(x)=\prod_{k=1}^{\infty}\frac{1}{1-x^k} ]
为什么？第 (k) 个因子 (\frac{1}{1-x^k}) 展开是 (1+x^k+x^{2k}+\cdots)，选 (j) 个 (k)，指数就是 (jk)，系数就是"用几个k"的方案数1。所有因子乘起来，(x^n) 的系数正好是各种用1、用2、用3……凑出n的方案数。
这个结构的程序含义比数学含义更重要。限制"只能用不超过m的数拆分"，就是把乘积截断到 (k\le m)。限制"每个数最多用c次"，一个因子就变成有限等比数列：
[ 1+x^k+x^{2k}+\cdots+x^{ck}=\frac{1-x^{(c+1)k}}{1-x^k} ]
这类问题本质上就是背包：第k个物品的重量是k，数量有限或无限，求装满n的方案数。你完全可以用DP做，但当n和m都很大、物品数量很多时，用NTT把多项式乘起来会快得多。我第一次用这种思路做一道拆分计数题时，DP要 (O(nm))，换成NTT后直接降到 (O(n\log n)) 级别，体感非常明显。
3.2 卡特兰数：封闭形式的来路与用法
卡特兰数是竞赛里的常客。我们设 (C_n) 表示 (n) 对括号的合法括号序列数，(C_0=1)。括号序列有个著名结构：任何一个合法括号序列都可以看成"左括号、内部合法序列、右括号、后面的合法序列"，于是有递推：
[ C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i} ]
令 (C(x)=\sum C_nx^n)，上述递推的卷积结构可以直接写成一元二次方程：
[ C(x)=1+xC(x)^2 ]
解出来：
[ C(x)=\frac{1\pm\sqrt{1-4x}}{2x} ]
这里必须取负号，因为把 (x=0) 代进去要保持 (C(0)=1)。用广义二项式展开 ( \sqrt{1-4x})，再整理就能得到：
[ C_n=\frac{1}{n+1}\binom{2n}{n} ]
做题时我还想提醒一个细节：在程序里直接用 (\frac{1-\sqrt{1-4x}}{2x}) 求系数，需要处理分母的 (2x)，会让常数项变成"0除以0"。多次跑挂后我的习惯是：单独讨论 (C_0=1)，对 (n\ge1) 再展开，这样能避开整条歧义。
3.3 错排与有标号结构：EGF的高光时刻
错排问题非常适合说明EGF的威力。求 (n) 个元素的排列中，没有任何元素留在原位的情况数 (D_n)。经典的递推是：
[ D_n=(n-1)(D_{n-1}+D_{n-2}) ]
用普通生成函数推这个递推会非常痛苦，因为系数里有 ((n-1)) 乘在括号外，OGF的"乘以下标"操作只能产生单个 (n)，两个下标项混在一起很难看。
改用EGF。令：
[ D(x)=\sum_{n\ge0}D_n\frac{x^n}{n!} ]
代入递推，经过整理后得到：
[ D(x)=\frac{e^{-x}}{1-x} ]
这个结果一眼就能看穿结构：(\frac{1}{1-x}) 是所有排列的EGF（每项的系数都是 (1)），而 (e^{-x}=\sum(-1)^n\frac{x^n}{n!}) 是"奇偶个固定点"的容斥因子。两者相乘，展开系数恰好是：
[ \frac{D_n}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!} ]
所以 (D_n=n!\sum_{k=0}^n\frac{(-1)^k}{k!})。这个式子不只是好看，它揭示了所有"有标号结构+容斥"问题的共性：EGF乘积里的组合数自然完成标号分配，不需要你手动枚举。
4. 上机实操：多项式全家桶与代码细节
4.1 为什么是NTT
生成函数题最终都要算多项式乘法。理论上FFT也能做，但竞赛题答案要求取模，NTT直接在整数模意义下运算，没有浮点误差，速度也快。最常用的质数是 (998244353)，它的原根是 (3)，并且 (2^{23}) 整除 (998244352)，所以能支持比较大的长度。
要理解为什么生成函数和NTT如此搭配，可以这样想：生成函数的操作大多是乘除、求逆、取对数、取指数，这些在多项式截断意义下都归结为若干次乘法。把一个DP变成乘法，再把乘法用NTT加速，这就是整个优化链条。
4.2 NTT与多项式求逆的核心代码
先给一个能跑的NTT模板，省得每次从头写边界。
const int MOD = 998244353; const int G = 3; int qpow(int a, int b) { int res = 1; while (b) { if (b & 1) res = 1LL * res * a % MOD; a = 1LL * a * a % MOD; b >>= 1; } return res; } void ntt(int a[], int n, int op) { // op = 1 正变换，op = -1 逆变换，n 必须为 2 的幂 for (int i = 1, j = 0; i < n; i++) { int bit = n >> 1; for (; j & bit; bit >>= 1) j ^= bit; j ^= bit; if (i < j) swap(a[i], a[j]); } for (int len = 2; len <= n; len <<= 1) { int wlen = qpow(G, (MOD - 1) / len); if (op == -1) wlen = qpow(wlen, MOD - 2); for (int i = 0; i < n; i += len) { int w = 1; for (int j = 0; j < len / 2; j++) { int u = a[i + j]; int v = 1LL * a[i + j + len / 2] * w % MOD; a[i + j] = (u + v) % MOD; a[i + j + len / 2] = (u - v + MOD) % MOD; w = 1LL * w * wlen % MOD; } } } if (op == -1) { int invn = qpow(n, MOD - 2); for (int i = 0; i < n; i++) a[i] = 1LL * a[i] * invn % MOD; } }然后用它实现多项式求逆。求逆的作用很大，像 (\frac{1}{1-x-x^2}) 本质上就是求 (1-x-x^2) 的逆元。牛顿迭代的公式是：已知 (g) 满足 (g \equiv f^{-1} \pmod{x^m})，则：
[ g' = g(2 - fg) \pmod{x^{2m}} ]
实现如下：
void polyInv(int f[], int g[], int n) { static int t[MAXN]; g[0] = qpow(f[0], MOD - 2); for (int m = 1; m < n; m <<= 1) { int len = m << 2; fill(t, t + len, 0); copy(f, f + min(m << 1, n), t); ntt(t, len, 1); ntt(g, len, 1); for (int i = 0; i < len; i++) { g[i] = 1LL * g[i] * (2LL - 1LL * t[i] * g[i] % MOD + MOD) % MOD; } ntt(g, len, -1); fill(g + min(m << 1, n), g + len, 0); } }这里每次迭代把 (g) 的长度翻倍，所以从 (m=1) 开始循环到覆盖 (n)。关键点是：每次NTT前必须把超出当前长度的部分清零，否则上一轮的高位残留会污染结果。我在初学时漏了fill(g + cur, g + len, 0)这一行，导致过了一整晚才debug清楚。
4.3 长度与边界：三个最容易翻车的细节
第一个是卷积数组长度。两个长度为n的多项式相乘，结果长度最多到 (2n-1)，所以NTT的len必须取大于等于 (2n) 的2的幂。我见过一个常见问题是只用 (len=n)，结果高次项被循环卷积混回低位，答案全错。
第二个是求逆时的零次项要求。多项式求逆要求 (f[0]\ne0)。如果生成函数的常数项是0，比如要展开卡特兰数的 (\frac{1-\sqrt{1-4x}}{2x})，就不能直接对 (2x) 求逆。处理方法是先对分子求逆并把整体平移一位，或者单独讨论 (n=0) 项。
第三个是截断。我们计算的永远是模 (x^N) 的截断多项式，超出N的项直接丢弃。乘法后要把系数数组从N到len-1部分清0，否则下次NTT时这些"看不见的高位"照样参与运算，造成错误。这一点最隐蔽，因为大部分时候结果数量级不大，看不出异常，直到某个大数取模后才发现。
5. 常见问题排查与自检技巧
5.1 高频问题速查表
| 症状 | 可能原因 | 处理方式 |
|---|---|---|
| 通项和暴力求解结果对不上 | 生成函数类型选错，OGF与EGF混用 | 看对象是否带标号，带标号换EGF |
| 结果整体差一项 | x的幂次起始点错了 | 核对 (F_0) 是否单独处理 |
| 小数据正常，大数据出错 | NTT数组长度不足，或卷积后高位未清零 | len开2倍，循环后fill高位 |
| 求逆时程序崩溃或结果全0 | (f[0]=0) 直接求逆 | 先平移或单独处理常数项 |
用exp/ln时结果不对 | 模数不是NTT友好质数 | 换 (998244353) 或双模数CRT |
| 递推递出来的数和生成函数算出的差一个常数 | 边界项 (a_{-1}) 之类没定义 | 手动补 (n=0) 项再对拍 |
这张表我每次提交前都会过一遍，尤其是对拍不过时，最先怀疑的就是"哪一步忘了截断"。
5.2 一秒钟判断OGF还是EGF
这个判断会直接影响整道题的建模方向，说它决定成败都不夸张。我的口诀是：没有标号就OGF，有标号就EGF。
说得更具体一点：研究对象如果只是"数量"，比如选几个苹果、拆成几个数，它的组合结构是无标号的，用OGF，系数直接是答案。研究对象如果自带编号，"从n个有编号的客人中选几个坐一桌、剩下坐另一桌"，这种结构会涉及分配标号，就必须用EGF。
一个反直觉但很重要的点是：同一个问题可以同时用OGF和EGF描写，只是系数含义不同。OGF里 (x^n) 系数是 (a_n) 本身，EGF里 (x^n/n!) 系数才是 (a_n)。写题的时候心里要非常明确当前操作的对象是哪一种。
5.3 三个让我debug到深夜的教训
第一个教训是斐波那契的起始下标。同样一组递推，如果定义 (F_0=1,F_1=1)，生成函数就变成 (\frac{1}{1-x-x^2})，而不是 (\frac{x}{1-x-x^2})。就这一个 (x) 的差别，会让第n项对应下标整体偏移一位。现在我拿到递推题，第一件事是写下 (F_0, F_1, F_2) 三个值，再套生成函数验证三次，确认匹配后才继续。
第二个教训是EGF的阶乘处理。有一段时间我偷懒，用OGF处理有标号集合，结果求错排数时所有项都变成原来的 (n!) 倍。问题的根源是我没有在卷积后恢复系数——EGF乘法得到的是 (\frac{a_n}{n!})，要得到最终 (a_n) 还得乘回 (n!)。从那以后，我每次写EGF都会在注释里标"最后乘阶乘"。
第三个教训是多项式开方时的符号选择。前面提到的卡特兰数封闭形式里那个正负号，不是代数上随便选一个，而是要保证零次项系数和实际值一致。按 (x=0) 代入 (1\pm\sqrt{1})，取负号才得到 (0)，再除以 (2x) 得1。这种细节如果只在心里默算，很容易把整套公式带偏。
最后再分享一个小技巧
我自己写生成函数题时有个习惯：先用暴力枚举把 (n=0,1,2,3) 这几个小规模答案全部算出来，列成一张表。然后无论用哪种方法推导，最后拿系数前先把小规模代进去对比。比如算到某个展开式，就看 (n=0) 项是不是1，(n=1) 项是不是预期值。如果小规模全对，再跑大数据，基本一次过。
另一个很值钱的习惯是写一个打印多项式系数的调试函数，输出"指数:系数"格式，项多了只看前十几项。NTT这种算法出错时，光看结果很难定位，但把中间每步乘法前后的多项式打出来，很快就能发现是哪一次卷积把高位弄脏了。这两个习惯帮我省下的时间，远比写它们花掉的时间多得多。
