简介

在数学中，某个序列 $(a_n)_{n \in {\mathbb{N}}}$ 的母函数（又称生成函数，英语：Generating Function）是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。使用母函数解决问题的方法称为母函数方法。

摘自维基百科。生成函数分为多种，本文将主要介绍普通生成函数（Ordinary Generating Function）和指数生成函数（Exponential Generating Function）。另外，本文还会提到大部分的多项式算法，用来解决生成函数的题目。

入门文章推荐：

前置技能

广义二项式定理

广义二项式定理是卡特兰数通项的前置技能。我们对广义的组合数有如下定义：

$\binom{\alpha}{n} = \frac{\alpha^{\underline{n}}}{n!} (\alpha \in \mathbb{C},n \in \mathbb{N})$

那么下式始终成立：

$(x + 1)^\alpha = \sum_{i = 0}^{\infty} \binom{\alpha}{i} x^i$

当 $\alpha$ 为整数的时候上式就是传统的二项式定理。

复合函数求导

对一个复合函数 $f\circ g(x)$ 求导：

$(f \circ g(x))' = \frac{\text{d} f\circ g(x)}{\text{d} g(x)} \cdot \frac{\text{d} g(x)}{\text{d} x} = f'(g(x)) \cdot g'(x)$

这样的求导法则被称为 “链式法则”。

普通生成函数

普通生成函数，英文 Ordinary Generating Function，简称 OGF。对于序列 $(a_n)_{n \in \mathbb{N}}$，它的普通生成函数 $F(x) = \sum_{i = 0}^{\infty} a_i x_i$。另外如果 $a_i$ 是某个离散随机变量的概率质量函数，它的生成函数被称为概率生成函数。

BZOJ 3028 食物

「BZOJ 3028」食物

题目大意：

由若干种食物，每种食物有一个限制（比如只能选不超过 $x$ 个，只能选奇数个等，具体看题），问选出 $n$ 份食物的方案数。

数据范围：$n \le 10^{500}$。

思路分析：

考虑把所有食物的生成函数乘起来：

$\begin {split} & (x^0 + x^2 + \cdots)(x^0 + x^1)(x^0 + x^1 + x^2)(x^1 + x^3 + \cdots) (x^0 + x^4 + \cdots) \\ \times & (x^0 + x^1 + x^2 + x^3)(x^0 + x^1)(x^0 + x^3 + \cdots) \\ = & \frac{(1 + x)^2(1 + x + x^2)(1 + x + x^2 + x^3) x}{(1 - x^2)^2 (1 - x^3) (1 - x^4)} \\ = & \frac{(1 + x)^2(1 - x^3)(1 - x^4) x}{(1 - x)^4(1 + x)^2(1 - x^3)(1 - x^4)} \\ = & \frac{x}{(1 - x)^4} \\ \end {split}$

于是我们考虑用二项式定理展开：

$\begin {split} F(x) & = \frac{x}{(1 - x)^4} \\ & = x (1 - x)^{-4} \\ & = x \sum_{i = 0}^{\infty} \binom{-4}{i} (-x)^i \\ & = x \sum_{i = 0}^{\infty} (-4) \times (-5) \times \cdots \times \left(-(i + 3)\right) \times \frac{1}{i} \times (-x)^i \\ & = \sum_{i = 1}^{\infty} \binom{i + 2}{3} \times x^i \end {split}$

于是就有 $f(n) = \binom{n + 2}{3}$，直接计算即可。

BZOJ 3027 Sweet

「BZOJ 3027」Sweet

题目大意：

有 $n$ 罐糖，第 $i$ 罐有 $m_i$ 个，问选出 $[a, b]$ 个糖的方案数。

数据范围：$n \le 10, m_i \le 10^6, a \le b \le 10^7$。

思路分析：

我们要求的是生成函数：

$\begin {split} & \prod_{i = 1}^{n} \frac{1 - x^{m_i + 1}}{1 - x} \\ = & (1 - x)^{-n} \prod_{i = 1}^{n} 1 - x^{m_i + 1} \\ = & \sum_{i = 0}^{\infty} \binom{-n}{i} (-x)^i \prod_{i = 1}^{n} 1 - x^{m_i + 1} \\ = & \sum_{i = 0}^{\infty} \binom{n + i - 1}{n - 1} x^i \prod_{i = 1}^{n} 1 - x^{m_i + 1} \\ \end {split}$

中 $x^a, x^{a + 1}, \cdots, x^b$ 的系数的和。

发现 $n$ 很小，所以可以 $2^n$ 枚举 $\prod_{i = 1}^{n} 1 - x^{m_i + 1}$ 的每一项，之后就只需要计算一个组合数的前缀和：

$\sum_{i = 0}^{k} \binom{n + i - 1}{n - 1} = \binom{n + k}{n}$

直接计算即可，时间复杂度 $O(2^n n)$。

推导卡特兰数通项

卡特兰数的第 $n$ 项表示 $n$ 个结点的二叉树数量（不带标号，区分左右子树）。记卡特兰数的第 $n$ 项为 $f_n$，那么 $f(0) = 1$，且对于 $n \ge 1$ 有递推式：

$f(n) = \sum_{i = 0}^{n - 1} f(i) f(n - 1 - i)$

记 $F(x)$ 表示卡特兰数的生成函数，那么我们有：

$F(x) = xF^2(x) + 1 \\$

最后 $+1$ 是因为要考虑 $f(0) = 1$ 的边界。那么我们考虑解方程：

$\begin {split} F(x) & = \frac{1 \pm \sqrt{1 - 4x}}{2x} \\ & = \frac{(1 \pm \sqrt{1 - 4x})(1 \mp \sqrt{1 - 4x})}{2x(1 \mp \sqrt{1 - 4x})} \\ & = \frac{4x}{2x(1 \mp \sqrt{1 - 4x})} \\ & = \frac{2}{1 + \sqrt{1 - 4x}} \\ & = \frac{1 - \sqrt{1 - 4x}}{2x} \\ \end {split}$

在第四行舍掉减号是因为如果取减号那么 $x = 0$ 时没有意义。

那么我们首先要计算 $(1 - 4x)^{\frac{1}{2}}$，用二项式定理展开：

$(1 - 4x)^{\frac{1}{2}} = \sum_{i = 0}^{\infty} \binom{\frac{1}{2}}{i} (-4x)^i = g(i) \\$

考虑计算 $g(i)$：

$\begin {split} g(i) & = \left(\frac{1}{2}\right) \times \left(-\frac{1}{2}\right) \times \left(-\frac{3}{2}\right) \times \cdots \times \left(-\frac{2i - 3}{2}\right) \times \left(\frac{1}{i!}\right) \times (-4x)^i \\ & = \left(\frac{1}{2}\right)^i \cdot (-1)^{i - 1} \cdot (2i - 3)!! \cdot \left(\frac{1}{i!}\right) \cdot (-1)^i \cdot 4^i x^i \\ & = -\frac{(2i - 3)!!}{i!} \cdot 2^i x^i \\ & = -\frac{(2i - 2)!}{2^{i - 1}(i - 1)! i!} \cdot 2^i x^i \\ & = -\frac{2(2i - 2)!}{(i - 1)! i!} x^i \\ \end {split} \\$

注意上式只在 $i \ge 1$ 时是正确的，$i = 0$ 时 $g(0) = 1$。经过上述的推导，我们有：

$\begin {split} (1 - 4x)^{\frac{1}{2}} = 1 - \sum_{i = 1}^{\infty} \frac{2(2i - 2)!}{(i - 1)! i!} x^i \\ \end {split}$

代回原式得到：

$\begin {split} F(x) & = \frac{1 - \sqrt{1 - 4x}}{2x} \\ & = \frac{\sum_{i = 1}^{\infty} \frac{2(2i - 2)!}{(i - 1)! i!} x^i}{2x} \\ & = \sum_{i = 0}^{\infty} \frac{(2i)!}{i! (i + 1)!} x^i \\ \end {split}$

所以我们就得到了卡特兰数的通项公式：

$f(n) = \frac{(2n)!}{i!(i + 1)!} = \frac{\binom{2n}{n}}{n + 1}$

BZOJ 4001 概率论

「BZOJ 4001」概率论

题目大意：

问 $n$ 个点的二叉树期望有几个叶子。

数据范围：$n \le 10^9$。

思路分析：

设 $f(n)$ 表示 $n$ 个结点的二叉树的叶子总数，那么我们有 $f(1) = 1$，对于 $n \ge 2$ 有递推式：

$f(n) = 2\sum_{i = 1}^{n - 1} f(i) C_{n - 1 - i}$

其中 $C_i$ 表示卡特兰数的第 $i$ 项，也就是 $\frac{\binom{2n}{n}}{n + 1}$。那么我们记卡特兰数的 OGF 为 $H(x)$，$f(n)$ 的 OGF 为 $F(x)$，那么我们有：

$F(x) = 2xF(x)H(x) + x$

在上一题中我们知道 $H(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$，那么我们就有：

$\begin {split} F(x) & = (1 - \sqrt{1 - 4x}) F(x) + x \\ & = \frac{x}{\sqrt{1 - 4x}} \\ & = x (1 - 4x)^{-\frac{1}{2}} \\ & = x \sum_{i = 0}^{\infty} \binom{-\frac{1}{2}}{i} (-4x)^i \\ & = x \sum_{i = 0}^{\infty} \binom{2i}{i} x^i \\ & = \sum_{i = 1}^{\infty} \binom{2i - 2}{i - 1} x^i \end {split}$

于是我们就得到了 $f(n) = \binom{2n - 2}{n - 1}$，那么答案就是：

$\frac{f(n)}{C_n} = \frac{\binom{2n - 2}{n - 1} (n + 1)}{\binom{2n}{n}} = \frac{n^2 + n}{4n - 2}$

直接计算即可。当然也有更巧妙的方法，观察到：

$\int \frac{F(x)}{x} \text{d}x = -\frac{1}{2} \sqrt{1 - 4x} = xH(x)$

那么我们就得到了：$f(n) = n C_{n - 1} = \binom{2n - 2}{n - 1}$。

Codeforces 438E 小朋友与二叉树

「Codeforces 438E」The Child and Binary Tree

题目大意：

给定 $n$ 个数 $c_1, c_2, \cdots, c_n$，问有多少棵点上有数的二叉树，满足点上的数是某个 $c_i$，并且点权和为 $k$。对于所有 $1 \le k \le m$ 求出答案。

数据范围：$n, m \le 10^5$。

思路分析：

设 $c_1, c_2, \cdots, c_n$ 的 OGF 为 $G(x)$，答案的 OGF 为 $F(x)$，那么根据题意，有：

$F(x) = G(x)F^2(x) + 1 \\ G(x)F^2(x) - F(x) + 1 = 0 \\$

考虑解方程：

$\begin {split} F(x) & = \frac{1 \pm \sqrt{1 - 4G(x)}}{2G(x)} \\ & = \frac{\left(1 \pm \sqrt{1 - 4G(x)}\right)\left(1 \mp \sqrt{1 - 4G(x)}\right)}{2G(x)\left(1 \mp \sqrt{1 - 4G(x)}\right)} \\ & = \frac{\left(1 \pm \sqrt{1 - 4G(x)}\right)\left(1 \mp \sqrt{1 - 4G(x)}\right)}{2G(x)\left(1 \mp \sqrt{1 - 4G(x)}\right)} \\ & = \frac{4G(x)}{2G(x)\left(1 \mp \sqrt{1 - 4G(x)}\right)} \\ & = \frac{2}{1 + \sqrt{1 - 4G(x)}} \\ \end {split}$

这里要舍掉减号。于是使用多项式求逆、开根即可计算，时间复杂度 $O(n \log n)$。

指数生成函数

指数生成函数，英文是 Exponential Generating Function，简称 EGF。对于序列 $(a_n)_{n \in \mathbb{N}}$，它的指数生成函数为：

$\hat F(x) = \sum_{i = 0}^{\infty} \frac{a_i}{i!} x_i$

指数生成函数一般被用来求解有标号的计数问题，它可以简化运算，因为有以下泰勒级数成立：

$e^x = 1 + \frac{x}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots$

POJ 3734 Blocks

「POJ 3734」Blocks

题目大意：

有 $n$ 个带标号的格子，每个格子染 $4$ 种颜色之一，要求最后第 $1, 2$ 种颜色是偶数，问方案数。

数据范围：$T \le 100, n \le 10^9$。

思路分析：

格子是有标号的，考虑答案的指数生成函数：

$\begin {split} \hat F(x) & = \left(1 + \frac{x^1}{1!} + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots\right)^2 \left(1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \cdots\right)^2 \\ & = \left(e^x\right)^2 \left(\frac{e^x + e^{-x}}{2}\right)^2 \\ & = \frac{e^{2x} \cdot (e^{2x} + e^{-2x} + 2)}{4} \\ & = \frac{e^{4x} + 2e^{2x} + 1}{4} \end {split}$

因为 $e^{ax} = \sum_{i = 0}^{\infty} \frac{(ax)^i}{i!} = \sum_{i = 0}^{\infty} a^i \frac{x^i}{i!}$，所以有：

$\begin {split} \hat F(x) & = \frac{e^{4x} + 2e^{2x} + 1}{4} \\ & = \frac{1}{4} + \frac{\sum_{i = 0}^{\infty} (2^{i + 1} + 4^{i}) \frac{x^i}{i!}}{4} \end {split}$

所以答案 $f(n)$ 就等于 $\frac{2^{n + 1} + 4^n}{4}$，直接计算即可。

BZOJ 3456 城市规划

「BZOJ 3456」城市规划

题目大意：

问有多少个带标号的 $n$ 个点的联通图。

数据范围：$n \le 1.3 \times 10^5$。

思路分析：

记 $n$ 个点的带标号无向图的个数为 $g(n) = 2^{\frac{n(n - 1)}{2}}$，那么 $g(n)$ 的指数生成函数为：

$\hat G(x) = \sum_{i = 0}^{\infty} 2^{\frac{i(i - 1)}{2}} \frac{x^i}{i!}$

记 $n$ 个点的带标号联通图的个数为 $f(n)$，那么 $f(n)$ 的指数生成函数为：

$\hat F(x) = \sum_{i = 0}^{\infty} f(i) \frac{x^i}{i!}$

发现 $\hat G(x) = 1 + \frac{\hat F(x)}{1!} + \frac{\hat F^2(x)}{2!} + \frac{\hat F^3(x)}{3!} + \cdots = e^{\hat F(x)}$，所以我们把 $\hat G(x)$ 做多项式对数函数就行了。时间复杂度 $O(n \log n)$。

51nod 1728 不动点

「51nod 1728」不动点

题目大意：

求有多少个映射 $f:{1,2,\cdots,n}\to {1,2,\cdots,n}$，使得 $\forall i, \underbrace{f\circ f \circ \cdots \circ f}_{k}(i) = \underbrace{f\circ f \circ \cdots \circ f}_{k - 1}(i)$。

数据范围：$T \le 5 \times 10^4, n \le 2 \times 10^6, k \le 3$。时限 $20s$。

思路分析：

其实就是求 $n$ 个点的每个树的深度都不超过 $k$ 的有根森林的个数。记 $k = i$ 时的指数生成函数为 $\hat F_i(x)$，那么显然有 $\hat F_1(x) = e^x$。考虑如何从 $F_i(x)$ 推到 $F_{i + 1}(x)$。对于一个 $n$ 个点的有根树我们枚举一个根，去掉这个根后其他的点就会形成大小为 $n - 1$ 的有根森林。如果令 $n$ 个点的深度不超过 $i$ 的有根树个数的指数生成函数为 $\hat G_i(x)$，那么就有 $[x^n]\hat G_{i + 1}(x) = n[x^{n - 1}]\hat F_{i}(x)$，推一下发现 $\hat G_{i + 1}(x) = x \hat F_{i}(x)$。而我们又有 $\hat F_i(x) = \exp(\hat G_i(x))$，所以就有 $\hat F_{i + 1}(x) = \exp(x\hat F_i(x))$。时间复杂度 $O(k n \log n)$，注意常数优化。

Codeforces 891E Lust

「Codeforces 891E」Lust

题目大意：

给定 $n$ 个数 $a_1, a_2, \cdots, a_n$，作 $k$ 次操作，每次随机选一个数 $a_i \gets a_i - 1$，把 $\text{res} \gets \text{res} + \prod_{j \neq i} a_j$，问最后 $\text{res}$ 的期望。

数据范围：$n \le 5000, k \le 10^9$。

思路分析：

发现答案等于一开始所有数的乘积减去操作完后所有数的乘积，所以只要算操作完后所有数的乘积的期望。考虑算出每个数的 EGF 最后乘起来。$a_i$ 的 EGF 是：

$\begin {split} \hat F_i(x) & = \sum_{j = 0}^{\infty} (a_i - j)\frac{x^j}{j!} \\ & = (a_i - x)e^x \end {split}$

所以答案的 EGF 是：

$\begin {split} \hat F(x) & = \prod_{i = 1}^{n} \hat F_i(x) \\ & = \prod_{i = 1}^{n} (a_i - x)e^x \\ & = e^{nx} \prod_{i = 1}^{n} (a_i - x) \\ \end {split}$

我们要求的期望 $E$ 满足 $\frac{n^k E}{k!} = [x^k] \hat F(x)$。我们 $O(n^2)$ 算出 $\prod_{i = 1}^{n} (a_i - x) = \sum_{i = 0}^{n} b_i x^i$ 后考虑计算答案：

$\begin {split} \frac{n^k E}{k!} & = [x^k] e^{nx} \prod_{i = 1}^{n} (a_i - x) \\ & = [x^k] \prod_{i = 1}^{n} (a_i - x) \prod_{j = 0}^{\infty} \frac{n^j}{j!} \\ & = \sum_{i = 0}^{n} b_i \frac{n^{k - i}}{(k - i)!} \\ E & = \sum_{i = 0}^{n} b_i \frac{n^{- i} k!}{(k - i)!} \\ & = \sum_{i = 0}^{n} b_i \frac{k^{\underline{i}}}{n^i} \end {split}$

直接计算，总复杂度 $O(n^2)$。