从零开始的生成函数学习笔记 1 幂级数 X 前置组合数学知识 2 ( ext{OGF}) 3 ( ext{EGF})
膜拜生成函数之神 ( t Kcolor{red}{arry5307})，( t Ccolor{red}{ommand\_block})，( t{x}color{red} ext{义}x)。
这个博客基本是贺 ( t Ccolor{red}{ommand\_block}) 的。
幂级数长这样：
你可以认为这是一个无穷项的多项式，其中 (i) 次项的多项式就是 (F[i])。
然后同时 (F[i]) 又可以表示成一个数列。
比如 ({1,1,4,5,1,4,0,0,0,cdots}) 就可以表示成 (4x^5+x^4+5x^3+4x^2+x+1)，但是这个东西太臭了，我们换一个。
比如 ({1,1,1,1,1,cdots}) 就可以表示成 (F(x)=sumlimits_{i=0}^infty x^i)。
然后我们假装这是收敛的（事实上这个幂级数是我们自己搞出来的东西，我们完全可以默认这是收敛的），因此 (F(x)-xF(x)=1)，因此 (F(x)) 也可以写成 (F(x)=frac{1}{1-x}) 的形式。由于后面这个简洁的式子显然比前面的更好用，所以我们称后面的那个东西为生成函数的封闭形式。
我们约定 (xrightarrow{ extbf{G}}) 为数列到幂级数的一种简单映射：直接取每个数当作系数。
然后可以得到一些结论。
X 前置组合数学知识
X.1 组合对象
我们称一些满足某些性质的元素的集合为组合对象，用 (A) 表示。
比如 (A) 可以表示有标号荒漠，或者 dead_X 的妹子（没错，空集也是合法的），或者一个字符集为 ( t{0,1}) 的字符串。
然后 (A) 中的每个元素 (a) 都会有一个大小函数 (size(a))。
比如 (size(a)) 在有标号荒漠的集合中可以表示点的数量，在 dead_X 的妹子的集合中表示年龄，字符串中可以表示串长。
然后题目一般会问我们“(n) 个点的有标号荒漠数量是多少”，也就是问 (size(a)) 为 (n) 的 (ain A) 的数量。我们同样设定一个符号 (A[n]) 来表示这个东西。
于是我们就把一个集合用数列的方式表达了。
X.2 笛卡尔积
(A) 可以做乘法，没想到吧（注意这里的 (A) 是组合对象而不是集合）
(A_1 imes A_2 imes A_3 imescdots A_n) 还是一个组合对象，它的定义为 (n) 元组 ((a_1,a_2,a_3,cdots,a_n) (a_iin A_i,i=1,2,cdots,n)) 的集合。
易知 (|A imes B|=|A| imes |B|)。
不难发现，在这个过程中，我们定义了一个新的组合对象。
( ext{OGF})
2.1 介绍
( ext{OGF}) 的全名是 ( ext{ordinary generating function})，也就是普通生成函数。
事实上 (xrightarrow{ extbf{G}}) 就是 (xrightarrow{ extbf{OGF}})。我们只需要暴力给每个数乘上 (x^i) 加以区分即可。
再回顾一下，( ext{OGF}) 就是表示一个数列的幂级数，即 ({f_0,f_1,f_2,cdots}xrightarrow{ extbf{OGF}}F(x)=sumlimits_{i=0}^{infty}f_ix^i)。然后又由于一个组合对象也可以用数列的方式组合，因此我们可以用 ( ext{OGF}) 来表示组合对象。
我们已经用之前的 (xrightarrow{ extbf{G}}) 表示了一些 ( ext{OGF})，接着我们再给几个：
这些都可以自行手推，莫得难度。
2.2 组合意义
显然 ( ext{OGF}) 的性质对人类友好一些……
我们来分析一下 ( ext{OGF}) 在处理一些组合意义时怎么办。
2.2.1 不交并
两个不相交集合的并。
(C(x)=A(x)+B(x))
加法原理，没啥好说的。
2.2.2 笛卡尔积
注意，这里的笛卡尔积一般用于处理无标号对象的组合对象。
假设我们要求组合对象 (C=A imes B)。
我们再定义 (size(a,b)=size(a)+size(b))。
然后我们就能发现这其实就是一个简单的卷积形式，也就是 (C[i]=sumlimits_{j=0}^iA[j]B[i-j])
2.3 简单应用（迫真）
2.3.1 Super Poker II
好吧这个是真的很简单的应用。
有四个集合 (A,B,C,D)，一开始每个集合里有所有合数 (a_i,b_i,c_i,d_i)，然后我们从这些集合去掉 (n) 个数，最后问你在每个集合选出一个数，和为 (l,l+1,cdots,r) 各有几种方案。
(nleq 10^4,mleq 5 imes 10^4)
不难发现 (size(a)=sum a)，即一个多元组的大小为所有元素之和，于是就满足了上面笛卡尔积的前提。
不难发现每个 (A[n]) 都在 (n) 是合数且没有被去掉的情况下是 (1)，其余情况都是 (0)。
那么就可以 ( ext{FFT}) 卷起来了。
2.3.2 数学题
求长度为 (n) 且前 (i) 个字符是数字，后 (n-i) 个字符是小写字母的字符串数量。
然后你发现这玩意还是可以笛卡尔积。
不难发现前面这玩意的生成函数是 (frac{1}{1-10x})，后面这玩意的生成函数是 (frac{1}{1-26x})，直接乘起来得到 (frac{1}{(1-10x)(1-26x)})，然后暴力求逆即可。
2.3.3 数学题II
长度为 (i) 的骨牌有 (A[i]) 种，每种 (inf) 个，求有多少种方法凑出不重叠，长度为 (1,2,3,cdots,n) 的长条。
这个题看起来十分不可做。
我们考虑大力枚举使用 (k) 块骨牌组成 (n) 的方法数，发现就是将 (A) 变成 (A) 的 (k) 次方。
那么设 (B=A(x)^i)，(B) 的每一项就对应着答案。
而总方案就可以写成用 (1,2,3,cdots,infty) 块骨牌的方法数和。
于是答案的幂级数就是 (sumlimits_{i=0}^infty A(x)^i)。
根据前面的式子，有 (sumlimits_{i=0}^infty A(x)^i=frac{1}{1-A(x)})，然后就可以欢乐多项式求逆了。
2.3.3+ 整数的lqp拆分
不难发现斐波那契数列的生成函数可以写成 (F(x)=frac{1}{1-x-x^2})，那么答案就是 (large frac{1}{1-frac{1}{1-x-x^2}})，直接计算即可。
你看，就用这个小技巧，我们氵了个黑题
2.3.4 The Child and Binary Tree
我们发现当数据出现一些难以处理的限制时，往往能够把限制也搞成一个生成函数。
我们设 (F[i]) 为权值为 (i) 的神犇二叉树个数。
我们设 (G[i]) 为是否可以选择点权 (i)，可以为 (1)，不可以为 (0)。
然后我们考虑怎么 dp 求出 (F[i])。
我们开始思索 (F[i]) 如何拆成 (F[j])。
稍微思考了一下，发现由于题目要求的是有根，无标号，区分左右儿子的二叉树，我们可以拆成左子树和右子树。
然后就十分简单了：(F[i]=sumlimits_{j=0}^i(G[i-j]sumlimits_{k=0}^jF[k]F[j-k]))
即先选自身权值，再将剩下的权值分给孩子。
不难发现这个很能卷积，于是变成生成函数。
诶，这个好像不对？
哦，(F[0]=1)，但是 (G[0]=0) 把它去掉了，所以我们给右边加 (1)。
解一元二次方程。
判断 (pm) 应该取负，然后就可以多项式开根，求逆然后乘起来了。
( t Ccolor{red}{ommand\_block}) 给出了一种减小常数的方法：
常数减小了！
2.3.5 [集训队作业2013]城市规划
我们发现连通图依旧是一个限制条件，我们尝试去掉限制，发现 (n) 个点的简单图很好算。
我们设 (F[i]) 为 (n) 个点的连通图数量。
我们设 (G[i]) 为 (n) 个点的图数量。
不难发现如果我们考虑将 (1) 号点所在的连通块和原图分开，则有
然后你发现 (G[i]=2^inom{i}{2})。
于是把这三个神奇的式子分别记为 (A[i],B[j],C[i-j])，就有 (C(x)=A(x) imes B(x)) 了。
由于我们知道 (B) 和 (C)，于是开始一通多项式高级操作，这题就做完了。
( ext{EGF})
3.1 介绍
( ext{EGF}) 的全名是 ( ext{ordinary generating function})，也就是 exp 生成函数。
注意，这里 (f_0 eq F[0]) 了！
列举一些常见 ( ext{EGF}) 的封闭形式：
3.2 组合意义
3.2.1 不交并
(C(x)=A(x)+B(x))
加法原理，没啥好说的。
3.2.2 笛卡尔积
注意，这里的笛卡尔积一般用于处理有标号对象的组合对象。
假设我们要求组合对象 (C=A imes B)。
我们再定义 (size(a,b)=size(a)+size(b))。
然后此时我们定义两个组合对象相加后可以改变相对顺序，但内部顺序保持原样。
然后我们先观察序列：(C_i=sumlimits_{j=0}^nA_jB_{i-j}inom{i}{j})。
那么就有
你可以理解为，( ext{OGF}) 是把两样东西原封不动拼接起来，而 ( ext{EGF}) 则是混合起来了。
具体可以看第一个例子。
2.3 简单应用（迫真）
2.3.1 数学题III
你有 (n) 个格子，你打算把每个格子涂成 (color{#1f1e33} t{1f1e33})，(color{#114514} t{114514})，(color{#191981} t{191981}) 中的一种颜色。
由于野兽先辈和原野二人幸终，所以你要求 (color{#114514} t{114514})，(color{#191981} t{191981}) 必须涂偶数次。
你想知道有多少种涂色的方法。
我们套路地设 (F(x),G(x),H(x)) 为用三种颜色涂 (i) 个格子的方法数的 ( ext{EGF})，那么
然后你惊奇地发现，用两种颜色涂格子的方法的方法数的 ( ext{EGF}) 就是将两种用一种颜色涂格子的方法数的 ( ext{EGF}) 乘起来。
- 证明：(i) 个数选 (j) 个用第一种，剩下的用第二种。
于是这道题就做完了。
2.3.2 无聊的水题I
首先，你要知道有 prufer 序列这个东西。
但是你并不需要了解它，你只需要知道两个结论：
- (n) 个节点的有标号无根树和长度为 (n-2)，元素为节点编号的序列一一对应，也就是双射。
- 一个长度为 (n-2)，元素为节点编号的序列所代表的树中，每个节点的度数为它在序列中出现次数 (+1)。
不难想道把阴间的恰好转化成不超过然后相减，所以要求的东西如下：
一个长度为 (n-2)，值域为 ([1,n]) 的整数，每个数出现次数小于 (k) 的序列的个数。
那么我们就可以整出 ( ext{EGF}) 了，( ext{EGF}) 即为 ({frac{1}{0!},frac{1}{1!},frac{1}{2!},cdots,frac{1}{(k-1)!},0,0,0,cdots})。
于是设上面那玩意是 (F(x))，我们只需要求 (F(x)^{n})，直接上多项式快速幂即可。
复杂度 (O(nlog n))。