生成函数小小结

· · 个人记录

生成函数小小结

这篇是我学了这几天的 GF 得到的成果，并不是生成函数用法大全一类的。

OGF/普通生成函数

一般地，对于数列 \left<a_0,a_1,a_2,\cdots\right>，定义它的 OGF 为：

F(x)=\sum_{n\ge 0}a_nx^n

其中如果原数列是有限的，就把大于数列上限的 a_n 设为 0 即可。

推导递推式的封闭形式

OGF 可以用来推导形如以下形式递推式的封闭形式：

a_n=\sum_{i=n-k}^{n-1}w_ia_i

其中 k,w_i 均为已知常数，这种递推式也被叫做常系数齐次线性递推。（这种也是能被矩阵快速幂优化的类型，不过如果题目要求 \mathcal{O}(1) 回答询问时矩阵快速幂就不行了）

举个例子吧，比如这道题：

P5110 块速递推

给出一个数列 a 满足以下递推式：

a_n=233a_{n-1}+666a_{n-2},a_0=0,a_1=1

考虑设原数列的 OGF F(x)=\sum_{n\ge 0}a_nx^n。求解的套路是根据题目中给出的递推式，把 F(x) 乘以对应的 w_ix^i，从而使 a_n 系数后退 i 项，并满足题目中的递推形式。例如本题中，我们尝试把 F(x) 分别乘上 233x,666x^2：

233xF(x)=\sum_{n\ge 1}233a_{n-1}x^n\qquad 666x^2F(x)=\sum_{n\ge 2}666a_{n-2}x^n

能看到递推式的影子，考虑把这俩加起来：

\begin{aligned}233xF(x)+666x^2F(x)&=\sum_{n\ge 2}(233a_{n-1}+666a_{n-2})x^n+233a_0x\\&=F(x)-a_0-a_1x+233a_0x\\&=F(x)-x\end{aligned}

用这个方程解出来 F(x)：

F(x)=\dfrac{x}{1-233x-666x^2}

这就是我们要求的数列对应的 OGF 的封闭形式了，但这没有用，我们想求的是这玩意的封闭形式：

[x^n]\dfrac{x}{1-233x-666x^2}

考虑待定系数法：

\dfrac{A}{1-ax}+\dfrac{B}{1-bx}=\dfrac{x}{1-233x-666x^2}

这样解出来 A,B,a,b 后就可以根据左边的 OGF 已知整出来右边的了。根据相同次数的 x 系数相等可以解得：

\begin{cases}A=\dfrac{1}{13\sqrt{337}}\\B=-\dfrac{1}{13\sqrt{337}}\\a=\dfrac{233+13\sqrt{337}}{2}\\b=\dfrac{233-13\sqrt{337}}{2}\end{cases}

这样，根据形如 \dfrac{A}{1-ax} 的封闭形式对应的 OGF 是已知的我们可以得到：

F(x)=\sum_{n\ge 0}\dfrac{1}{13\sqrt{337}}\left(\left(\dfrac{233+13\sqrt{337}}{2}\right)^n-\left(\dfrac{233-13\sqrt{337}}{2}\right)^n\right)x^n

所以有：

[x^n]F(x)=\dfrac{\left(\dfrac{233+13\sqrt{337}}{2}\right)^n-\left(\dfrac{233+13\sqrt{337}}{2}\right)^n}{13\sqrt{337}}

封闭形式是找到了，但回归题目我们却发现还是没法过，因为题目要求的是 \mathcal{O}(1) 求解。接下来要做的就是针对题目来优化这个式子。

首先是找出模 10^9+7 意义下的 \sqrt{337}，通过暴力枚举可以知道它等于 216,284,168 或 783,715,839，再求一下逆元，代入就可以将原式化简为：

[x^n]F(x)\equiv766,769,301(905,847,205^n-94,153,035^n)\pmod{10^9+7}

用欧拉定理模一下指数，再预处理好一些幂（分块打表，也叫作光速幂）就可以做到 \mathcal{O}(1) 求解了。总时间复杂度 \mathcal{O}(T)。

代码实现：\tt code

基本上所有常系数齐次线性递推都可以通过以上的标准流程找到封闭形式，至于找到封闭形式之后是继续化简求解，还是直接套到另一个式子里推，或者其他的就要看具体题目了。

除此之外，还有一类的递推式可以通过 OGF 化简，那就是具有卷积形式的式子。

CF438E The Child and Binary Tree

给出一个含有 n 个元素的集合 C，定义一个二叉树是好的，当且仅当它所有点的权值都在集合 C 中，并定义一个二叉树的权值为所有顶点权值和。给出一个整数 m，对于所有的 1\le s\le m，求出权值为 s 的好二叉树个数，答案对 998,244,353 取模。(1\le n,m,c_i\le10^5)

考虑设 f_i 表示权值为 i 的好二叉树个数，g_i=[i\in C]，则可以得到：

f_n=[n=0]+\sum_{i=1}^ng_i\sum_{j=0}^{n-i}f_jf_{n-i-j}

大概意思就是枚举这个点的权值，并枚举左右子树的权值。可以观察到明显的卷积形式，如果设

F(x)=\sum_{n\ge 0} f_nx^n\qquad G(x)=\sum_{n\ge 0}g_nx^n

则原式即：

F=F^2G+1

把 F 当主元，解这个二元一次方程：

F=\dfrac{1\plusmn\sqrt{1-4G}}{2G}

有俩解，不过问题不大，我们可以用 f_0 排除掉一个。考虑 \lim_{x\rightarrow0}F(x)=f_0=1，而：

\lim_{x\rightarrow0}\dfrac{1+\sqrt{1-4G(x)}}{2G(x)}=\infty\qquad \lim_{x\rightarrow0}\dfrac{1-\sqrt{1-4G(x)}}{2G(x)}=1

所以可以得到 F=\dfrac{1-\sqrt{1-4G}}{2G}，分子有理化得到：

F=\dfrac{2}{1+\sqrt{1-4G}}

多项式开根号+求逆即可解决。

代码实现：\tt code

加速组合求出的式子

对于某些组合的题目，利用容斥等组合科技可以得到某个式子，但可能直接计算复杂度较高无法通过，这时候就要找找看式子里有没有卷积的形式，如果有就能利用 GF 把它优化掉了。

P4491 [HAOI2018]染色

给出一个长为 n 的序列，序列上的每个位置都可能被染成 m 种颜色的其中一种。如果恰好出现 s 次的颜色有 k 种，则这个方案的贡献为 w_k。求出所有方案的贡献和，答案对 1,004,535,809 取模。(1\le n\le10^7,1\le m\le10^5,1\le s\le 150)

令 x=\min(\frac{n}{s},m)，即可能取到的 k 最大值。考虑设 f(k) 表示恰好出现 s 次的颜色至少有 k 种的方案数。至少有 i 种也就是钦定 k 种剩下的随便，则方案数为：

f(i)=\dbinom{m}{k}\dfrac{n!}{(s!)^k(n-sk)!}(m-k)^{n-sk}

即选出 i 个乘可重集排列数乘随便。但显然我们想要的不是至少而是恰好，这个转化容易想到二项式反演，如果设 g(k) 表示恰好 k 种，则：

g(k)=\sum_{i=k}^x(-1)^{i-k}\dbinom{i}{k}f(i)

现在就可以求了，只不过时间复杂度是 \mathcal{O}(m^2) 的无法通过。考虑把那个组合数拆成阶乘的形式：

\begin{aligned}g(k)&=\sum_{i=k}^x(-1)^{i-k}\dfrac{i!}{(i-k)!k!}f(i)\\&=\dfrac{1}{k!}\sum_{i=k}^x\dfrac{(-1)^{i-k}}{(i-k)!}i!f(i)\end{aligned}

好像有点差卷积的形式？考虑记：

F(n)=\dfrac{(-1)^n}{n!}\qquad G(n)=n!f(n)

则原式可以化为：

g(k)k!=\sum_{i=k}^x F(i-k)G(i)

这就是典型的差卷积的形式了，只需要把 G(n) 的系数倒过来（设得到的多项式为 G^R(n)）就有卷积的形式了：

\begin{aligned}g(k)k!&=\sum_{i=k}^x F(i-k)G^R(x-i)\\&=\sum_{i=0}^{x-k}F(i)G^R(x-k-i)\end{aligned}

预处理出 F,G，直接上 NTT 做即可，时间复杂度 \mathcal{O}(m\log m)。

代码实现：\tt code

EGF/指数型生成函数

一般地，对于数列 \left<a_0,a_1,a_2,\cdots\right>，定义它的 EGF 为：

F(x)=\sum_{n\ge 0}a_n\dfrac{x^n}{n!}

其中如果原数列是有限的，就把大于数列上限的 a_n 设为 0 即可。

EGF 卷积的组合意义

众所周知 EGF 卷积的组合意义是选这一堆和那一堆合并，但合并的时候是具有前后顺序的。可以根据这个意义，把很多用 OGF 不好表示的东西用 EGF 简洁地描述。

P5339 [TJOI2019]唱、跳、rap和篮球

有 a+b+c+d 个物品，物品有四种类型，第 1,2,3,4 种分别有 a,b,c,d 个。求出从这些物品中选 n 个摆成一排，且满足不存在四个位置使得这四个位置上依次是第 1,2,3,4 种物品的方案数（我们称这样的四个位置为坏位置），答案对 998,244,353 取模。(n\le 10^3,a,b,c,d\le 500,a+b+c+d\ge n)

考虑设 f(k) 表示至少存在 k 个坏位置，g(k) 表示恰好存在 k 个坏位置，则根据二项式反演：

g(k)=\sum_{i\ge k}\dbinom{i}{k}(-1)^{i-k}f(i)

最终答案即 g(0)=\sum_{i\ge 0}(-1)^if(i)。现在的问题是怎么求 f(k)，考虑先从整体去掉 3k 个格子，随便插入 k 个第 1 种，再在所有的第 1 种后面缀上第 2,3,4 种，这就是放 k 个坏位置的方案。剩下的随便即可：

f(k)=\dbinom{n-3k}{k}S(a-k,b-k,c-k,d-k,n-4k)

其中 S(a,b,c,d,n) 表示 n 个位置，四种物品分别有 a,b,c,d 个，随便放置的方案数。把 f(k) 代入 g(0) 的表达式：

g(0)=\sum_{i\ge 0}(-1)^i\dbinom{n-3i}{i}S(a-i,b-i,c-i,d-i,n-4i)

现在只需要快速求出 S(a,b,c,d,n) 就能得到答案了。因为这个放置是具有前后顺序的，所以构造这四种物品的 EGF：

\hat{A}(x)=\sum_{n\ge 0}[n\le a]\dfrac{x^n}{n!}\quad\hat{B}(x)=\sum_{n\ge 0}[n\le b]\dfrac{x^n}{n!}\quad \hat{C}(x)=\sum_{n\ge 0}[n\le c]\dfrac{x^n}{n!}\quad \hat{D}(x)=\sum_{n\ge 0}[n\le d]\dfrac{x^n}{n!}

卷起来取第 n 项即为答案。每次都做一次 NTT，所以时间复杂度 \mathcal{O}(n^2\log n)。还能通过一些巧妙的方法优化成 \mathcal{O}(n^2)，不过那不是本文的重点就略过了。（其实就是我没看懂）

代码实现：\tt code

EGF exp 的组合意义

如果设

\hat{F}(x)=\sum_{n\ge 0}f_n\dfrac{x^n}{n!},\hat{G}(x)=\exp \hat{F}(x)=\sum_{n\ge 0}g_n\dfrac{x^n}{n!}

则 g_n 的意义为：

g_n=\sum_{\pi=\{S_1,S_2,\cdots,S_n\}}\prod_{i=1}^n f_{|S_i|}

其中 \pi 是 1\sim n 的划分。

P4841 [集训队作业2013]城市规划

求出 n 个点的简单有标号无向连通图个数，答案对 1,004,535,809 取模。(1\le n\le 1.3\times10^5)

这道题的 Key Observation 在于注意到无向图其实就是把点划分为若干个相互不连通的连通块，即如果设 \hat{G}(x) 表示 n 个点无向图个数的 EGF，\hat{F}(x) 表示 n 个点无向连通图的 EGF，则满足：

\hat{G}(x)=\exp \hat{F}(x)

由于 \hat{G}(x) 是已知的：（考虑完全图的每条边连还是不连）

\hat{G}(x)=\sum_{n\ge 0}2^{\binom{n}{2}}\dfrac{x^n}{n!}

所以我们想求的 \hat{F}(x) 即：

\hat{F}(x)=\ln \hat{G}(x)

多项式 \ln，这题就做完了，时间复杂度 \mathcal{O}(n\log n)。

代码实现：\tt code

EGF 满足 \exp 关系的一些例子：