简明生成函数指南

· · 算法·理论

本博客主要综合了 @lrc0511更加严谨的形式幂级数与生成函数引论 ，oi-wiki。侧重点放在了实战做题，相对来说在理论严谨上略不完善。

你需要的 前置知识：群、环、映射等基本概念。

一、群

群是一种由一个 集合 和一个 二元运算 组成的代数结构。

我们将一个群记作 (G,\cdot )。G 是一个集合，\cdot 并不意味着只能与点乘形成群，只是一个例子。

群要满足 ⌈群公理⌋。

提到过了很多次，群不一定满足交换律。

对于只满足部分群公理的结构，我们有新的名称。

对于不只满足群公理的结构，同样有新的名称。

- $(\mathbb{N_+},+)$ 是一个半群，因为幺元 $0\notin \mathbb{N_+}$。$(\mathbb{N},+)$ 是一个幺半群，因为不满足存在逆元。$(\mathbb{Z},+)$ 是一个交换群。 - $(\mathbb{Z},\times )$ 不是群而是幺半群，因为部分整数在乘法下的逆元不属于整数集。 - 实数乘集 $(\mathbb{R},\times)$ 是一个交换群。 - $n$ 阶方阵的集合 $\mathbb{M}_n (\mathbb{R})$ 对于矩阵加法构成一个交换群。但对于矩阵乘法构成幺半群。因为矩阵不一定有逆。 初学时这些概念以及简单的例子需要充分熟悉。 ## 二、环 环由一个集合 $R$ 以及**两个**二元运算 $+,\times $ 构成。记作 $(R,+,\times)$。 环需要满足如下性质： - $(R,+)$ 构成**交换群**。 - $(R,\times)$ 构成**半群**。 - 分配律：对于任意 $R$ 的元素 $a,b,c$，满足 $a\times(b+c)=a\times b+a\times c,(b+c)\times a=b\times a+c\times a$。 注意到环的乘法（即符号中的 $\times$ ）只要求是半群，所以满足更多性质的同样有定义： - 环上的乘法**还**满足交换律，称为交换环。 - 环上的乘法存在**幺元**，称为幺环。注意幺环不一定是交换环。交换环也不一定是幺环。 - 若幺环的所有非 $0$ 元素都有乘法逆元。则称其为除环。 **域**是交换除环。 ## 三、多项式与形式幂级数 ### 1.1形式幂级数的定义 定义多项式 $f(x)=\sum\limits_{i=0}^n a_ix^i$，则定义一个多项式环 $R[x]=\{\sum\limits_{i=0}^n a_ix^i|a_i\in \mathbb{R}\}$。 类似的，定义形式幂级数 $A(x)=\sum\limits_{i=0}^\infty a_ix^i$，一般将 $\infty$ 略去。同样形式幂级数环 $R[[x]]=\{\sum\limits_{i=0} a_ix^i|a_i\in \mathbb{R}\}$。 定义形式幂级数第 $n$ 项系数 $[x^n](A)=a_i$。 注意到形式幂级数的 $x$ 只是一个符号，不具有代入计算的功能。我们更多地讨论形式幂级数的系数。 ### 1.2.形式幂级数的运算 定义形式幂级数 $F=\sum\limits_{i=0}a_ix^i,G=\sum\limits_{i=0}b_ix^i$。 $F+G=\sum\limits_{i=0}(a_i+b_i)x^i$，系数对应相加。 $FG=\sum\limits_{i=0}\sum\limits_{j=0}a_ib_jx^{i+j}$。另一种表达形式是 $[x^n](FG)=\sum\limits_{i=0}a_ib_{n-i}=\sum\limits_{i=0}[x^i]F[x^{n-i}]G$。 形式幂级数的非负次幂的定义依靠乘法运算。特别的，定义 $F^0=1$。 形式幂级数**不一定有逆**。 考虑对形式幂级数 $F$ 计算他的逆 $G$。 则因为 $FG=1$，有 $[x^0]=1,[x^i]=0(i>0)$。 可得 $a_0b_0=1$，这意味着 $F$ 的常数项有逆。此时计算出了 $b_0$ 的值。对于 $[x^i]=0(i>0)$，先从 $i=1$ 看，有 $a_0b_1+a_1b_0=0$，由于 $a,b_0$ 是确定的，所以可得 $b_1=-a_1b_0a_0^{-1}$。同样要求常数项有逆。类似的可以推出 $b$ 的其他项。这是求逆的过程。 ### 1.3一些重要的推导 - 形式幂级数 $\sum\limits_{i=0}x_i$ 的逆是 $1-x$。即 $\sum\limits_{i=0}x^i=\dfrac{1}{1-x}$。我们将后者称为前者的封闭形式。注意不要将 $x$ 用某个值代入来判断对错，因为前面提到过形式幂级数的 $x$ 仅仅只是一个符号，不具有代入计算的功能。更严谨的表述可以看 lrc 此处的论述。 由此可以得出一些**重要**推论。 - 推论一：$\sum\limits_{i=0}x^{ik}=\sum\limits_{i=0}(x^k)^i=\dfrac{1}{1-x^k}$。 - 推论二：$\sum\limits_{i=0}^n=\sum\limits_{i=0}x^i-\sum\limits_{i=0}x^ix^{n+1}=\dfrac{1}{1-x}-\dfrac{x^{n+1}}{1-x}=\dfrac{1-x^{n+1}}{1-x}$。 - 推论三：$\sum\limits_{i=0}a^ix^i=\sum\limits_{i=0}(ax)^i=\dfrac{1}{1-ax}$。 - 推论四：$\sum\limits_{i=n}=\sum\limits_{i=0}-\sum\limits_{i=0}^{n-1}=\dfrac{1}{1-x}-\dfrac{1-x^n}{1-x}=\dfrac{x^n}{1-x}$。 - 推论五： $\sum\limits_{i=n}^mx_i=\sum\limits_{i=0}^mx_i-\sum\limits_{i=0}^{n-1}x_i=\frac{1-x^{m+1}}{1-x}-\frac{1-x^n}{1-x}=\frac{x^n-x^{m+1}}{1-x}

以上概念相当简略，但足够完成对生成函数的基本学习。如果有时间务必系统学习上述内容，本文目的在于学习生成函数，此处先略去。

2.1普通生成函数的定义

首先需要知道生成函数是有多种类型的，最常使用的是普通生成函数(OGF) 以及 指数生成函数(EGF)。

我们先讨论普通生成函数。

对序列 a 定义的普通生成函数为形式幂级数 \sum\limits_{i=0}a_i x^i。

如果序列 a 有通项公式，那么其生成函数的系数就是通项公式，注意形式幂级数下标从 0 开始，而一般的数列从 1 开始，方便起见后续的数列下标均从 0 开始。

- $a=\{1,2,3,\cdots\}$，其通项公式是 $a_n=n+1$。则生成函数是 $\sum\limits_{i=0}(i+1)x^i$。 - $a=\{1,3,5,7,\cdots\}$，其通项公式是 $a_n=2n+1$，则生成函数是 $\sum\limits_{i=0}(2i+1)x^{2i+1}$。 - $a=\{1,2,4,8,\cdots\}$，其通项公式是$a_n=2^n$，则生成函数是 $\sum\limits_{i=0}2^i x^i$。 - $a=\{1,0,1,0,1,\cdots\}$，其通项公式是 $a_{2n}=1$ (比较奇怪的表示)。则生成函数是 $\sum\limits_{i=0}x^{2i}$。 $eg2$：（训练封闭形式） 发现上一个训练中的第四个写成封闭形式是较为简单的，但是其他几个好像很困难。具体可见 oi-wiki 的做法。 - 某数列的生成函数的封闭形式是 $\dfrac{1}{2x^2-3x+1}$，求数列通项公式。 对其因式分解得 $\dfrac{2}{1-2x}+\dfrac{1}{1-x}$。由前面的推论可知生成函数是 $2\sum\limits_{i=0}2^ix^i+\sum\limits_{i=0}x^i=\sum\limits_{i=0}2^{i+1}x^i+\sum\limits_{i=0}x^i=\sum\limits_{i=0}(2^{i+1}+1 )x^i$。则通项公式是 $a_n=2^{n+1}+1$。 ### 2.2普通生成函数的组合意义 以下部分较为重要。 举个例子来说，有一堆红球，如果我们设 $a_i$ 为取出 $i$ 个无标号红球的方案数。如果要求取出的是 $2$ 的倍数，$a=\{1,0,1,0,\cdots\}$。如果取出的小于等于 $3$ 个，$a=\{1,1,1,1,0,\cdots\}$。我们求出其生成函数 $F$，得到 $a_i=[x^i](F)$。 如果还有一堆蓝球，也有若干限制。设 $b_i$ 为取出 $i$ 个无标号蓝球的方案数。得到生成函数 $G$。 我们要求取出的蓝、红球的 **总数** 为 $i$，还要满足各自的需求。设 $c_i$ 为方案数，则 $c_i$ 应该是多少呢？枚举红球 $j$ 个，蓝球就是 $i-j$ 个，$c_i=\sum\limits_{j=0}^i a_ib_{i-j}$。不觉得这很熟悉吗，我们把 $F,G$ 乘起来，$[x^i](FG)$ 也是上述结果。 例：[P2000 拯救世界](https://www.luogu.com.cn/problem/P2000) 题意不清。十种东西互不相关且无标号，要求总数为 $n$ 且要满足各自的要求。 如果做过前面的练习，写出这些生成函数想必不难。 直接把生成函数乘起来。不好乘，写成封闭形式乘起来，得到 $(\dfrac{1}{1-x})^5$。由前面退推论可知其等于 $\sum\limits_{i=0}\binom{5+i-1}{5-1}x^i$，第 $i$ 项系数是 $\binom{n+4}{4}$。 ### 3.1指数生成函数的定义 定义数列 $a$ 的指数生成函数为形式幂级数 $F(x)=\sum\limits_{i=0}\dfrac{a_i}{i!}x^i$。或者写作 $\sum\limits_{i=0}a_i\dfrac{x^i}{i!}$。文中一般写后者。主要是为了满足 $[x^n]F=a_i$。 考虑指数生成函数的加减。系数对应相加减即可。 考虑乘法。设数列 $a,b$ 的指数生成函数为 $F,G$。则 $FG=\sum\limits_{i=0} \dfrac{a_i}{i!}x^i\sum\limits_{j=0}\dfrac{b_j}{j!}x^j$。通过形式幂级数乘法得到 $\sum\limits_{i=0}\sum\limits_{j=0}x^{i+j}\dfrac{a_ib_j}{i!j!}$。转化为 $\sum\limits_{n=0}x^n\sum\limits_{i=0}a_ib_{n-i}\times \dfrac{1}{i!(n-i)!}$。如果给如果只看第二个求和号的话发现其对应着 EGF 定义的 $\dfrac{a_n}{n!}$。如果将 $n!$ 乘上去的话就是 $\sum\limits_{i=0}\binom{n}{i}a_ib_{n-i}$。所以 $FG$ 是此式的指数生成函数。 考虑 EGF 的封闭形式。回顾一下，OGF 的封闭形式我们从 $\sum\limits_{i=0}x^i=\dfrac{1}{1-x}$ 开始。EGF 也有类似的操作。 $\sum\limits_{i=0}\dfrac{x^i}{i!}=e^x=\exp x$。 如果对形式幂级数做 $\exp$ 呢？我们把 $\exp$ 视作一个形式幂级数环向自身的映射。 形式化的，定义 $\exp:R[[x]]_+\to R[[x]],F\mapsto \sum\limits_{i=0}\dfrac{F^i}{i!}$。这里相当于默认 $i!$ 可逆。这里的 $R[[x]]_+$ 为 $R[[x]]$ 的子环，他是全体常数项为 $0$ 的形式幂级数。 下面的部分将会涉及到多项式基础操作。如 多项式卷积、多项式求逆、多项式开根、多项式 $\exp$、多项式 $\ln$，也算是前置知识。其不仅能够加速运算，还可以加深对 $\exp,\ln$ 的理解。 ### 3.2 一些有关 $\exp$ 的重要推论 首先有 $\sum\limits_{i=0}\dfrac{x^i}{i!}=\exp(x)$。 则有 $\exp(F+G)=\exp(F)\exp(G)$。 证明： $\exp(F+G)=\sum\limits_{i=0}\dfrac{(F+G)^i}{i!}=\sum\limits_{i=0}\dfrac{1}{i!}\sum\limits_{j=0}^i \binom{i}{j}F^jG^{i-j}=\sum\limits_{i=0}\sum\limits_{j=0}^i \dfrac{F^j}{j!}\dfrac{G^{i-j}}{(i-j)!}=\sum\limits_{j=0}\dfrac{F^j}{j!}\sum\limits_{i=j}\dfrac{G^{i-j}}{(i-j)!}=\sum\limits_{j=0}\dfrac{F^j}{j!}\sum\limits_{i=0}\dfrac{G^i}{i!}=\exp(F)\exp(G)

一个简单的推论：\exp(nF)=\exp(F)^n。为什么简单？仔细看看上面的式子。

还有：e^x=\sum\limits_{i=0}\dfrac{x^i}{i!},e^{ax}=\sum\limits_{i=0}\dfrac{a^ix^i}{i!},ae^x=\sum\limits_{i=0}\dfrac{ax^i}{i!}

一道简单的例题。P2012 拯救世界2

注意到题目要求有标号计数，所以使用 EGF。

先写出普通人的答案序列 a_i=\{1,1,1,\dots\}，则 EGF 为 \sum\limits_{i=0}\dfrac{x^i}{i!}=e^x=\exp(x)。

考虑出现偶数次的答案序列 a_i=\{0,1,0,1,\dots\}，则 EGF 为 \dfrac{e^x+e^{-x}}{2}。这是为什么呢？

考虑定义一个生成函数 G(x)=\sum\limits_{i=0}a_ix^i

则 G(-x)=\sum\limits_{i=0}(-1)^ia_ix^i，系数写出来就是 a_0,-a_1,a_2,-a_3,\dots，两个生成函数相加，系数为 2a_0,0,2a_2,0,2a_4,\cdots。除以二正好是 \sum\limits_{i=0} a_{2i} x^{2i}。

奇数次是 \dfrac{e^x-e^{-x}}{2}。

后面很简单，三个玩意乘起来然后 4 次方。

化简后的生成函数是 \dfrac{e^{12x}-4e^{8x}+6e^{4x}+e^{-4x}-4}{256}

求出其第 n 项系数，即为答案。

\dfrac{1}{256} (12^n-4\times 8^n+6\times4^n+(-4)^n)

注意 256 在 \bmod 10^9 没有逆元，两东西不互质。考虑乘进去。

81\times 12^{n-4}-8^{n-2}+6\times 4^{n-4}+(-4)^{n-4}

想卡常的话，用

欧拉定理

a^{\varphi(p)}\equiv 1\pmod p

该定理的在 p 为素数时退化为 a^{p-1}\equiv1\pmod p。

常用推论是若 a,p 互质，有 a^{b}\equiv a^{b\bmod \varphi(p)}\pmod p，证明可以把 b 替换为取模加上除以下取整，由欧拉定理消去后一部分。

如果不互质，有扩展欧拉定理。

当 b\ge \varphi(p)，a^b\equiv a^{b\bmod \varphi(p)+\varphi(p)}。

当 b<\varphi(p)，直接快速幂计算即可。

这样使得复杂度是 \log \varphi(p)，与 b 无关。

3.3 \exp 的组合意义

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

考虑无向图的计数很简单，直接有 g_n=2^{\binom{n}{2}}，枚举任意两点的连边是否存在即可。

连通图稍难。设 f_n 为无向连通图的个数。

则从 g 考虑。一个连通图可以看成若干个连通块，启示我们枚举连通快数量，枚举每个连通快的个数，给每个连通块分配编号，然后把 f_{\texttt{每个连通块的个数}} 乘起来。

但是由于连通块之间是无序的，所以这种算法会把每种情况算出 k! 次，例如 \{1,2\},\{3\} 和 \{3\},\{1,2\} 都会被算上。

列出式子进行一些推导，可以得到：

进行一个推广，可以得到： $[x^n] \exp F$ 为将有标号的 $n$ 个数，划分为若干子集（子集之间无序），每个子集分配一个 $F$ 的方案。 如果要求子集非空，则答案是 $\exp(e^x-1)$，即贝尔数。[P5748 集合划分计数](https://www.luogu.com.cn/problem/P5748) ### 4.1 $\ln,\exp$ 的性质 此处与多项式 $\ln,\exp$，导数，积分密切相关。学完再来。 - $\exp(\ln F)=F

最后一条提一下证明：

首先试证 -\ln(1-x)=\sum\limits_{i=1}\dfrac{x^i}{i}

两边求导。先看左边。

因为 \ln(x) 的导数是 \dfrac{1}{x}。 所以 f'(x)=-\mathcal{D}(\ln(1-x))。

考虑 \mathcal{D}(\ln(1-x))。

设 g(x)=\ln(x),a=1-x，则 \ln(1-x)=g\circ a，由链式法则有 \mathcal D(g\circ a)=(\mathcal D(g)\circ a)\mathcal D(a)=-\dfrac{1}{1-x}。

原式的左边就是 \dfrac{1}{1-x}。

右边求导，形式幂级数求导有 f'(x)=\sum\limits_{i=0} (i+1)a_{i+1}x^i，右边即为 \sum\limits_{i=0}x^i。

2.3 Euler 变换

Euler 变换之于 OGF，就相当于 \exp 之于 EGF。——lrc0511

P4389 付公主的背包

注意到东西是无标号的。考虑写出每种物品的 OGF。

对于一个体积为 v 的物品，其组成体积为 m 的背包的 OGF 为 \sum\limits_{i=0} x^{i v}=\dfrac{1}{1-x^v}。

最后的答案即把这些物品的 OGF 卷起来找 [x^m]。

复杂度 m^2\log m。

进一步腿式子。

卷起来的东西即为：

考虑对其 $\ln$，再 $\exp$。 $\ln(\prod\limits_{i=1}^n \dfrac{1}{1-x^{v_i}})=\sum\limits_{i=1}^n\ln(\dfrac{1}{1-x^{v_i}})=\sum\limits_{i=1}^n \ln(1-x^{v_i})=\sum\limits_{i=1}^n\sum\limits_{j=1}\dfrac{x^{v_ij}}{j}$。 我们只需要前 $m$ 项，将相同的 $v_i$ 记一下数量，枚举 $i$，$ij\le m$，调和级数的复杂度。求个 $\exp$ 是 $\log$。 引出 Euler 变换。 $$\xi(x)=\prod\limits_{i=1}(\dfrac{1}{1-x^i})^{[x^i]F}$$ 类似于 $\exp$，上式的含义是： 将 $n$ 个**无**标号物品分成若干子集（子集之间无序）的方案数，其中分为一个大小为 $i$ 的子集的方案数是 $[x^i]F$。 而 $\exp$ 是： 将 $n$ 个**有**标号物品分为若干子集（子集之间无序）的方案数，其中分为一个大小为 $i$ 的子集的方案数是 $[x^i]F$。 使用类似于那题一样的推导，将 Euler 变换写成另一种形式。 $\xi(x)=\exp(\sum\limits_{j=1}\dfrac{1}{j}F(x^j))

基本的东西已经介绍完了，入门的作用已经起到了。下面就是多刷题了。由于数学公式打起来浪费时间，所以和数学有关的题目的做题笔记都以纸质方式整理。