我怎么可能学会生成函数？

Wonder_Fish · 2025-03-11 10:08:14 · 算法·理论

cnblogs

[2025-03-17] 基本完工，之后可能随机更新。

[2025-03-27] 增加了 P4931。

普通生成函数（OGF）

定义：序列 a 的普通生成函数为 \sum a_i x^i。

• 其中序列 a 可以是任意序列，可以有穷也可以无穷。

加法运算：多项式直接加，合并同类项。对应到序列上意义是对应位置相加。

乘法运算：设 a,b 两个序列的生成函数是 F(x) 和 G(x)，发现 F(x)\cdot G(x) 得到的是 \sum_{i=0}^{n+m} \sum_{j=0}^i a_j b_{i-j} x^i，也就是序列 c_i = \sum_{j=0}^i a_j b_{i-j} 的生成函数。序列 c 即 a,b 的加法卷积。多个序列加法卷积起来可以看成是无序背包。

在运算中，常常使用生成函数的封闭形式，比如：

序列 1,1,1,1,\dots 的 OGF \sum_i x^i = \frac{1}{1-x};

序列 1,c,c^2,c^3,\dots 的 OGF \sum_i c^ix^i = \frac{1}{1-cx}；

序列 1,0,1,0,\dots （下标从 0 开始）的 OGF \sum_i x^{2i} =\frac{1}{1-x^2};

序列 a_i=c^i x^{ki} 的 OGF \sum_i a_i=c^i x^{ki} = \frac{1}{1-cx^k}；

斐波那契数列 OGF 封闭形式为 \frac{x}{1-x-x^2}。

以上几个通过错位相减容易得到。

序列 \binom{n}{0},\binom{n}{1},\dots,\binom{n}{n} 的 OGF \sum_{i=0}^n \binom{n}{i} x^i = (x+1)^n;

序列 \binom{n}{0},-\binom{n}{1},\binom{n}{2},\dots,(-1)^n \binom{n}{n} 的 OGF \sum_{i=0}^n \binom{n}{i} (-x)^i = (1-x)^n。

以上通过二项式定理得到。

序列 \binom{n}{n},\binom{n+1}{n},\dots,\binom{n+k}{n},\dots 的生成函数 \sum_i \binom{n+i}{n} x^i = \frac{1}{(1-x)^{n+1}}。

以上我不会推，先记着吧。 考虑组合意义，\binom{n+k}{n} 可以看成有 n+k+1 个物品，将其分成 n+1 份，每份都有 \geq 1 个物品的方案数，给每份拿走一个，就是 k 个物品分成至多 n+1 份的方案数。考虑背包，f_k 表示 k 个物品的方案（即上述序列），每次加入任意个物品，加入 n+1 次。设 f 的生成函数是 F(x)，用多项式表示加入的过程，F(x)=(\sum_i x^i)^{n+1} = \frac{1}{(1-x)^{n+1}}。

CF1096G

不难发现其实是要求 f_i 表示长度为 \frac{n}{2} 和为 i 的方案数，答案即为 \sum f_i^2。

也就是一个背包，每次放一个 0\sim 9 的数，一共放 \frac{n}{2} 个。

放一个数的答案 OGF 是 F(x)=\sum_{i=0}^9 x^i，最终答案的 OGF 为 F^{\frac{n}{2}}(x)，用 NTT 算一下系数。

本题没有要求对 x^n 取模，并且答案多项式最高次数是 9\times 10^5 在计算范围内，不需要大常数多项式快速幂，可以一遍 FFT，算下点值表示的 \frac{n}{2} 次幂，再 IFFT 回去，常数大大减小。

P2000

计算题。写出每个部分的 OGF 再乘起来观察。

发现这是 \binom{4+i}{i} 的 OGF，答案为 [x^n] \frac{1}{(1-x)^5}，即 \binom{4+n}{n} =\binom{n+4}{4} = \frac{n(n-1)(n-2)(n-3)}{24} ，高精度算一下。

P4451

斐波那契数列的 OGF 为 F(x) =\frac{x}{1-x-x^2}，该题的答案的生成函数是 G(x) =\sum_{i>0} F^i(x) = \frac{F(x)}{1-F(x)} = \frac{x}{1-2x-x^2}。

注意到 n 很大，不能暴力多项式求系数。感觉这个答案比较像斐波那契数列的形式，考虑用类似的方法解通项公式。

考虑形如 \frac{1}{1-cx} 的幂级数，希望将其写成若干上述东西的和。

对分母因式分解，解 1-2x-x^2=0，得 x_1=-1+\sqrt 2,x_2=-1-\sqrt 2，于是 1-2x-x^2=-(x-x_1)(x-x_2)。（注意有个负号，第一遍没看到结果推错了）

希望将其写成 \frac{a}{x-x_1}+\frac{b}{x-x_2}，解方程 \frac{a}{x-x_1}+\frac{b}{x-x_2} =\frac{x}{1-2x-x^2}，即 a(x-x_2)+b(x-x_1)=-x；

移项得 (a+b+1)x=ax_2+bx_1 恒成立，即 a+b=-1,ax_2+bx_1=0；

带入 x_1,x_2 可得 a=\frac{\sqrt 2 -2}{4},b=\frac{-\sqrt 2 -2}{4}。

把 x_1,x_2,a,b 带回去，得到

这是答案的通项公式，直接快速幂计算即可。指数很大，根据费马小定理对 \bmod-1 取模。

本题 \bmod 1000000007 意义下 \sqrt 2 存在，为 59713600 或 940286407，可以直接算。若不存在，可以考虑手写一个结构体 a\sqrt 2 +b 来运算。

P4389

答案 OGF F(x) = \prod_{i=1}^n \frac{1}{(1-x^{v_i})} = \frac{1}{\prod_{i=1}^m{(1-x^{v_i})}}。

看到这种乘积，容易想到取 \ln。

注意到 \ln(1-x^{v_i}) = - \sum_{i\geq 1} \frac{x^{vi}}{i}（建议背诵），推导过程如下：

令 f(x) = 1-x^v,g(x) = \ln(f(x)) ，

于是 G(x)=\sum_{i=1}^m \sum_{j\geq 1} \frac{x^{v_ij}}{j}

有了这个式子后，对于每个 v 就可以 O(\frac{m}{v}) 处理系数，对于相同的 v 一起处理，复杂度是调和级数的 O(n\log n)。

求出 G(x) 之后再 \exp 回去就行。

P3784

发现这题就是上面那题反过来。

设 f 的 OGF 为 F(x)，G(x)= \ln(F(x))= \sum_{i\in S} \sum_{j\geq 0} \frac{x^{ij}}{j}。

对给出的 f 求 \ln 得到 g，然后由于字典序最小，从小到大看 g 的每一位是否是 0，若不是，说明这个数存在，就加入答案并把后面都减去这个数的贡献。

黑的原因大概是任意模数罢。

梦熊省选第 25 场 T2

题目要求最大环长为 1 或 2，逆序对数为 i 的排列数量的奇偶性。注意到最大环长 >2 的排列将某个 >2 环所有边方向取反可以得到另一个不同的排列，因此会两两抵消，不会对答案产生影响。

所以只需要求 f_i 表示逆序对数为 i 的方案数，考虑 dp，f_{i,j} 表示加入前 i 个数，当前逆序对数为 j 的方案数，f_{i,j}=\sum_{k=0}^{i-1} f_{i-1,j-k}。

这个 dp 是背包形式，可以写成多项式相乘，设 f_n 的生成函数为 F(x)，

考虑对分子和分母分开计算，分母 \prod_{i=1}^n (1-x^i)，每个因式项数都很少，可以直接背包，忽略 \leq k 的项，使用 bitset 优化，复杂度 O(\frac{k^2}{\omega})。

分子部分，\frac{1}{(1-x)^n} = \sum_{i} \binom{n-1+i}{i}x^i，对于每项使用 lucas 定理计算那个组合数的奇偶性（关于组合数奇偶性的结论来自 P3773）。

然后再把分子部分与分母部分卷起来，同样用 bitset 优化背包做到 O(\frac{k^2}{\omega})。

P7435

几乎从头到尾的任何一部分都可以在其他题里面找到，但是我怎么推了这么长时间。哦原来是一开始题读错了。

根据题意考虑 dp，设 f_{i,j} 表示已经加入了前 i 个数，有 j 个逆序对的权值和，发现每加入一个数 i 可能新增 0\sim i-1 个逆序对，所以转移是 f_{i,j} =\sum_{k=0}^{i-1} i^k f_{i-1,j-k}。

这样的转移可以写成卷积形式。f_n 的生成函数为 F(x)=\prod_{i=1}^n \sum_{j=0}^{i-1} i^j。

熟悉的乘积形式，考虑取 \ln。

是一堆 \ln(1-(cx)^k) 状物，用类似 P4389 的方式求导以求出系数（现在发现 P4389 真有用吧）。

得到以上东西后，再代回 \ln(F(x))，即可得到 \ln(F(x)) 的各项系数。

我们需要求出这个东西的前 k 项系数。对于后半部分，虽然 i 的取值是 1\sim n，但是能对答案造成影响的一定是 \leq k 的数的约数，直接枚举 i(i\leq \min(n,k)) 然后计算它对其 \leq k 的倍数的影响即可做到 O(k\log k)。

对于前半部分，类似 [忘了是哪题了]，写出它的 EGF，

然后这个 G(x) 的系数是可以求的（注意上下常数项都是 0，但分母要求逆要求常数项不是 0，所以上下同除以 x 即可）。

然后就做完了，求出 \ln(F(x)) 再求 \exp。

P4931

考虑非加强版的做法，设 g_i 为 i 对情侣都不和睦的方案数。答案是 g_{n-k} 乘上剩下的 k 对情侣和睦的方案数，后面是好算的，若能快速求出 g_i 就可以 O(1) 回答询问。

计算 g_k 考虑容斥，钦定 i 对和睦，g_k = \sum_{i=0}^k (-1)^i \binom{k}{i} 2^i \frac{k!}{(k-i)!} (2k-2i)!。

考虑写出 g 的生成函数 F(x)，

于是 [x^k]F(x) = k!k! \sum_{i+j=k} \frac{(-2)^i}{i!}\binom{2j}{j}，设 G(x) 是 \frac{g_k}{k!k!} 的生成函数，

根据递推式求出 g'_k 即可得到 g_k。

指数生成函数（EGF）

定义序列 a 的指数生成函数为 \sum_i a_i \frac{x^i}{i!}。

加法运算：同样是对应位置直接加。

乘法运算：设 a,b 的指数生成函数为 F(x),G(x)，项数分别为 n 和 m，F(x)\cdot G(x) = \sum_{i=0}^{n+m} \sum_{j=0}^i a_j b_{i-j} \frac{x^i}{j!(i-j)!} = \sum_{i=0}^{n+m} \sum_{j=0}^i \binom{i}{j} a_j b_{i-j} \frac{x^i}{i!}，也就是序列 c_i = \sum_{j=0}^i \binom{i}{j} a_j b_{i-j} 的生成函数。

OGF 一般是集合计数，而 EGF 一般是序列计数。

对于指数生成函数还有一种理解：序列 \frac{a_i}{i!} 的普通生成函数。我们知道，普通生成函数可以看成无序组合，把这个 \frac{a_i}{i!} 卷起来再第 n 项乘上 n!，也就是全排，但实际上每个部分内部的顺序已经确定，并不需要再排，应当去掉全排时导致增加的内部顺序，这个可以提前去掉，即 \frac{a_i}{i!}。

EGF 运算中同样经常使用封闭形式。

序列 1,1,1,\dots 的 EGF 是 \sum_i \frac{x^i}{i!} = e^x，可用泰勒展开，但我不会，所以就直接背了吧。

序列 1,c,c^2,c^3,\dots 的 EGF 是 \sum_i \frac{c^ix^i}{i!} = e^{cx}，类比上面的东西得到。

序列 1,0,1,0,1,\dots 的 EGF 是 \sum_i \frac{x^i}{i!} [i \bmod 2 = 0] = \frac{e^x+e^{-x}}{2}，即奇数项相抵消，偶数项算了两遍所以要乘 \frac{1}{2}；

序列 0,1,0,1,0,\dots 类比得到 \frac{e^x-e^{-x}}{2}。

P5219

考虑 Prufer 序列，可以用长度 n-2 的序列与 n 个点有标号无根树构成双射，且每个点在序列中出现的次数为 d_x -1（d 为度数）。

可以看成每个数放 0 \sim M-1 个，最终的序列有多少种可能。

使用 EGF，每个数的 EGF 是 F(x)= \sum_{i<M} \frac{x^i}{i!}，答案是 (x-2)! [x^{n-2}] F^n(x)，多项式快速幂算一下即可。

P10588

即计数长度为 m 的操作序列，其中 1\sim l 出现奇数次，l+1\sim n 出现偶数次。

容易写出 EGF F(x)=(\sum_{i\bmod 2=1} \frac{x^i}{i!})^l (\sum_{i\bmod 2=0} \frac{x^i}{i!})^{n-l} = (\frac{e^x-e^{-x}}{2})^l(\frac{e^x+e^{-x}}{2})^{n-l}，然后答案就是 m![x^m]F(x)。

令 G(x)= (x-1)^l(x+1)^{n-l}，考虑通过求导法 G(x) 的系数 g 的递推式：

于是我们得到了递推式，g_0 和 g_1 容易自己算出来，剩下来的通过这个式子递推。

现在答案表示为 \frac{m!}{2^n} [x^m] e^{-nx} G(e^{2x})，令 H(x)=e^{-nx} G(e^{2x})，继续化简 G(x)：

现在答案已经是可以计算的形式了，带入计算即可。

由于 m 较大，算快速幂的时候 m 对 998244352 取模，这时候有个 corner case：0^0=1,0^{998244352}=0，需要特判。

P6555

奈绪可爱 qwq

观察到我们可以认为一个集合中的数，若出现 b 次，集合中的数为 [l,r] 中的正整数，则和的期望是 b\cdot\frac{l+r}{2}。因为从小到大排序后，对称的数列显然，不对称的考虑将其翻转，再将每个数 x 变为 l+r-x，可以得到一个与它不同的序列，两个的平均值刚好为 b\cdot\frac{l+r}{2}。

由于求总和，考虑对每个集合分别计算，其选 i 个数时的和乘上剩余部分方案数，再求和。算方案数时，一个集合放 i 个数的方案有 \binom{i+a-1}{a-1} 中，多个集合背包即可。可以使用可撤销背包算贡献，做到 O(nk^2)，但这显然不能通过本题。

发现背包卷积的形式可以用 EGF 卷积表示，对于方案数，每个集合的 EGF 是 F_k(x)= \sum_{i=1}^{b_k} \frac{\binom{i+a_k-1}{a_k-1}x^i}{i!}，对于需要算贡献的集合的 EGF 是 G_k(x)= \sum_{i=1}^{b_k} \frac{avg_k\binom{i+a_k-1}{a_k-1}x^i}{i!}，其中 avg_k 即所有可能出现在第 k 集合中的数的平均数。

设 H(x) =\sum_{i=1}^n G_i(x) \prod_{j\neq i} F_j(x)，答案就是 \sum_{i=1}^m i![x^i]H(x)，只需求出 H(x) 的系数。

考虑分治，存每个区间的 F(x) 和 H(x)，合并时候 F(x)=F_l(x)F_r(x),H(x)=H_l(x)F_r(x)+F_l(x)H_r(x)，边界 l=r 时 F 就是这个集合的 F，H 是这个集合的 G。分治有 \log 层因此每个式子只会被乘 \log 次，时间复杂度 O(k\log^2 k)。

P5850

原题任意模数似乎还不那么好用多项式做，所以原题才是加强版（雾

每个数最多出现一次，数 k 的 EGF 是 F_k(x)=\frac{x^0}{0!}+\frac{kx^1}{1!} = kx+1，答案是 n! [x^n] \prod_{i=1}^k F_i(x) = n![x^n] G(x)。

看到这个乘积，考虑类似 P4389 地取 \ln，\ln(G(x))= \sum_{i=1}^k \ln(kx+1)。

现在如果能快速求出 \ln(G(x)) 的各项系数，也就是快速求 \sum_{j=1}^k j^i 状物，再求 \exp 就可以得到 G(x)。

考虑写出上述东西的 EGF：

不难得到 H(x) 分子和分母的各项系数，对分母求逆再与分子乘起来即可得到 H(x) 的系数 h。但是注意到分母常数项为 0，不能求逆；注意到分子常数项也为 0，直接分子分母同除以 x 就行。求系数时别漏了 \frac{1}{i!}。

接下来得到 \ln(G(x))，再 \exp 得到 G(x)，即可得到答案。EGF 题别忘了乘 n!。

P5825

这题不难而且做法挺多，我只会最笨的那种。

考虑先计算钦定有 k 个 p_i<p_{i+1} 的位置的方案数 f_i，再通过二项式反演求出答案 g_i。

考虑钦定 k 个如上位置实际上等价于将排列划分为 n-k 段，每一段都上升。设排列 q 满足 q_{p_i}=i，这样的 p 和 q 显然是一一对应的，所以可以直接计数这样的 q。

考虑上面的限制对应到 q 上就是分成几组位置，组内保证有序。这是经典的 EGF 问题。一组的生成函数为 \sum_{i\geq 1} \frac{x^i}{i!}=e^x-1，而 f_{n-i}=n![x^n] (e^x-1)^i。

将其化成卷积形式一次 NTT 即可算出 f。

而二项式反演是众所周知的可以用 NTT 加速：

令 h_i= \frac{(-1)^{n-i}}{(n-i)!}，那么 g_i=\frac{1}{i!} [x^{n+i}] F(x)H(x)。