省选-数学-生成函数

OI-WIKI。

普通生成函数

$$F(x)=\sum_{n}a_n x^n$$

$a$ 可以是有穷序列，也可以是无穷的。

基本运算

加法运算：

$$F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n$$

乘法运算（卷积）：

$$F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i}$$

封闭形式

例如 $\langle 1,1,1,\cdots\rangle$ 的普通生成函数 $F(x)=\sum_{n\ge 0}x^n$：

$$F(x)x+1=F(x)\\ F(x)=\frac{1}{1-x}$$

---

HDU - 2152 Fruit

HDU - 2152 Fruit。

每个水果选 $a_i$ 到 $b_i$ 个之间，一共选 $m$ 个，问方案数。

直接生成函数就做完了：

$$(x^{a_1}+x^{a_1+1}+\cdots+x^{b_1})(x^{a_2}+x^{a_2+1}+\cdots+x^{b_2})\cdots(x^{a_n}+x^{a_n+1}+\cdots+x^{b_n})$$

P6300 悔改

P6300 悔改。

这道题标签没有生成函数，但是这个就是生成函数的题，算模板吧。

这种题先设 $c_i$ 表示 $i$ 的出现次数。

$$\begin{aligned} ans_k &= \frac{1}{2} \sum_{i+j=k}\min(c_i,c_j)\\ &=\frac{1}{2} \sum_{d=1}^n\sum_{i+j=k}[c_i\ge d][c_j\ge d]\\ \end{aligned}$$

我们发现这个很像生成函数的卷积形式，于是我们设生成函数 $f_d(x)$：

$$f_d(x)=\sum_i [c_i\ge d]x^i$$

然后将 $f_d(x)$ 代入：

$$ans_k=\frac{1}{2}\sum_{d=1}^nf_d(x)^2(k)$$

---

到现在我们已经推完了生成函数，但是这个还是会 TLE。我们还需要一点注意力，可以发现，$d$ 离散化之后就是 $O(\sqrt n)$ 级别的了。

然后上面的卷积就用 FFT/NTT 求出来即可，时间复杂度 $O(m\sqrt n \log m)$。

指数生成函数

$$\hat{F}(x)=\sum_{n}a_n \frac{x^n}{n!}$$

但 $\hat{F}(x)$ 实际上也是序列 $\left\langle \dfrac{a_n}{n!} \right\rangle$ 的普通生成函数。

基本运算

加减法和普通生成函数相同：

$$F(x)\pm G(x)=\sum_n (a_n\pm b_n)\frac{x^n}{n!}$$

乘法运算：

$$\begin{aligned} \hat{F}(x)\hat{G}(x) &=\sum_{i\ge 0}a_i\frac{x^i}{i!}\sum_{j\ge 0}b_j\frac{x^j}{j!}\\ &=\sum_{n\ge 0}x^{n}\sum_{i=0}^na_ib_{n-i}\frac{1}{i!(n-i)!}\\ &=\sum_{n\ge 0}\frac{x^{n}}{n!}\sum_{i=0}^n\binom{n}{i}a_ib_{n-i} \end{aligned}$$

上面的过程是因为组合数 $\binom{n}{i} = \frac{n!}{i! (n-i)!}$，因此

$$\frac{1}{i! (n-i)!} = \frac{1}{n!} \binom{n}{i}$$

所以：$\hat{F}(x)\hat{G}(x)$ 是序列

$\left\langle \sum_{i=0}^n \binom{n}{i}a_ib_{n-i} \right\rangle$

的指数生成函数。

封闭形式

序列 $\langle 1,1,1,\cdots\rangle$ 的指数生成函数是：

$\hat{F}(x) = \sum_{n \ge 0}\frac{x^n}{n!} = \mathrm{e}^x$

泰勒展开就行了。

exp 函数

很多时候，指数生成函数会和 exp 函数结合：

$$\exp(x) = e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!}, \quad x \in \mathbb{C}$$ $$e^{A(x)} = \sum_{k=0}^{\infty} \frac{A(x)^k}{k!}$$

P4726 【模板】多项式指数函数（多项式 exp）。

组合意义

$\left\langle \sum_{i=0}^n \binom{n}{i}a_ib_{n-i} \right\rangle$

我们发现这个正是把 $n$ 个元素划分成 $i$ 个集合。

广义二项式定理

$$(a+b)^{\alpha} = \sum_{k=0}^{\infty} \binom{\alpha}{k} a^{\alpha-k} b^k,$$ $$\binom{\alpha}{k} = \frac{\alpha (\alpha-1) (\alpha-2) \cdots (\alpha-k+1)}{k!}$$

广义组合数

经典组合数：

$$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$$

广义组合数：

$$\binom{\alpha}{k} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k!}$$

当 $\alpha$ 是负整数时，可化为带符号的经典组合数：

$$\binom{-n}{k} = (-1)^k \binom{n+k-1}{k}, \quad n \in \mathbb{N}^+$$

HDU - 1521 排列组合

HDU - 1521 排列组合。

第 $i$ 种物品的生成函数是 $1+\frac{x^1}{1!}+\frac{x^2}{2!} \cdots +\frac{x^{a_i}}{a_i!}$。

$$(1+\frac{x^1}{1!}+\frac{x^2}{2!} \cdots +\frac{x^{a_1}}{a_1!})(1+\frac{x^1}{1!}+\frac{x^2}{2!} \cdots +\frac{x^{a_2}}{a_2!}) \cdots (1+\frac{x^1}{1!}+\frac{x^2}{2!} \cdots +\frac{x^{a_n}}{a_n!})$$

最后我们要求 $\frac{x^m}{m!}$ 的系数。

生成函数的封闭形式

$$e^x = \sum_{n=0}^{\infty} \frac{x^n}{n!} = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!} + \cdots$$ $$e^{-x} = \sum_{n=0}^{\infty} \frac{(-x)^n}{n!} = 1 - x + \frac{x^2}{2!} - \frac{x^3}{3!} + \frac{x^4}{4!} - \cdots$$

POJ - 3734 Blocks

POJ - 3734 Blocks。

红色和绿色的生成函数：

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

蓝色和黄色的生成函数：

$$1+\frac{x^1}{1!} + \frac{x^2}{2!} + \cdots = e^x$$ $$\begin{aligned} F(x) &= ( \frac{e^x+e^{-x}}{2})^2 \cdot (e^x)^2 \\ &= \frac{e^{4x} + 2e^{2x} + 1}{4}\\ &= \frac{1}{4} + \sum\limits_{n=0}^{\infty}\frac{4^n}{4} \cdot \frac{x^n}{n!} +\sum\limits_{n=0}^{\infty}\frac{2^{n+1}}{4} \cdot \frac{x^n}{n!}\\ &=\frac{1}{4} + \sum\limits_{n=0}^{\infty}\frac{4^n + 2^{n+1}}{4} \cdot \frac{x^n}{n!} \end{aligned}$$

所以最后的答案就是：

$$4^{n-1} + 2^{n-1} \pmod{10007}$$

卡特兰数

有一些生成函数的题目需要卡特兰数。而且卡特兰数的递推公式可以用生成函数求。

$$C_n = \begin{cases} 1, & n = 0, \\ \sum_{i=0}^{n-1} C_{i}C_{n-1-i}, & n > 0 \end{cases}$$

数列前几项（可以背一下吧，做题可以瞪）：

$$1,1,2,5,14,42,132,429,1430\cdots$$

卡特兰数还有别的形式：

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \dfrac{(2n)!}{n!(n+1)!}$$

P3978 [TJOI2015] 概率论

P3978 [TJOI2015] 概率论。

首先，先定义 $g$ 表示二叉树的形态有多少种：

$$c_n=\sum_{i=0}^{n-1} g_{i}g_{n-1-i}$$

我们发现这正是卡特兰数的形式，通项公式就是用生成函数推的。

然后考虑函数 $f$ 表示 $n$ 个节点的二叉树的节点个数和。

我们考虑从 $n-1$ 转移。可以发现一个有 $n-1$ 个点的二叉树一共有 $(n-1)*2-(n-2)=n$ 个空余的节点。我们考虑转移后的组合 $(T,d)$ 表示一个树的每一个叶子节点，然后我们可以发现，每一个目标树上的节点都可以从对应的 $n-1$ 的树上转移来，所以：

$$f_{i}=n*g_i$$

所以 $n$ 个点二叉树叶子个数等于 $n-1$ 个点的个数 $\times n$。

例题

CF993E Nikita and Order Statistics

CF993E Nikita and Order Statistics。

反转序列构造卷积形式。

思路

首先这道题很容易想到前缀和。

$$ans_k=\sum_{l=1}^n\sum_{r=1}^n [s_r-s_{l-1}=k]$$

移项，然后还是用出现次数 $c$ 来表示。

$$ans_k=\sum_{l=1}^n c_{s_{l-1}+k}$$

然后我们需要消去 $s$：

$$ans_k=\sum_{l=1}^{n-k}c_i*c_{i+k}$$

然后这一点也不像卷积的形式，于是...我们设 $d$ 为把 $c$ 反过来的数组，$c_i=d_{n-i+1}$。

$$ans_k=\sum_{l=1}^{n-k}c_i\times d_{n-i-k}$$

于是我们用卷积来表示答案：

$$ans_k=c*d (n-k)$$

---

写完代码发现 $ans_0$ 一直是错的，然后需要特判。原因：可能会计算 $l>r$ 的情况。

P4451 [国家集训队] 整数的lqp拆分

P4451 [国家集训队] 整数的lqp拆分。

融合生成函数和数论各种知识的好题。

思路

我们可以用 $F$ 表示出选 $k$ 个数的生成函数：

$$\sum_{i=0}^{+\infty}f(x)^i$$

然后我们考虑写成封闭形式，我们先推导 $F$ 的封闭形式：

$$\begin{aligned} f(x)&=xf(x)+x^2f(x)+a_0+a_1x-a_0x\\ f(x)&=xf(x)+x^2f(x)+x\\ f(x)&=\frac{x}{1-x-x^2} \end{aligned}$$

然后我们再推原来的式子（代入无穷级数公式）：

$$\begin{aligned} \sum_{i=0}^{+\infty}f(x)^i&=\sum_{i=0}^{+\infty}\frac{1}{1-f(x)}\\ &=\frac{1-x-x^2}{1-2x-x^2}\\ &=1+\frac{x}{1-x-x^2} \end{aligned}$$

现在我们需要求这个生成函数的点值：

$$\frac{x}{1-x-x^2}$$

设这个为 $A$：

$$(1-2x-x^2)A(x)=x\\ \sum a_nx^n-2\sum a_nx^{n+1}-\sum a_nx^{n+2} = x\\ a_n=2a_{n-1}+a_{n-2}$$

然后我们需要求通项公式，需要一个叫特征方程的东西：

$$r^n=2r^{n-1}-r^{n-2}\\ r^2-2r-1=0\\ r=1\pm \sqrt 2$$

上面的方程是能表示出递推关系的，我们只需要解出可以满足 $a_0$ 和 $a_1$ 的解就行了。

然后通项公式一定是这个形式的（这个是二阶的函数）：

$$a_n=A(1+ \sqrt 2)^n+B(1-\sqrt 2)^n$$

代入 $0$ 和 $1$，$A=-B$，然后解得：

$$A=\frac{1}{2\sqrt2},B=-\frac{1}{2\sqrt2}$$

通项公式：

$$a_n=\frac{1}{2\sqrt2}(-\sqrt 2+1)^n-\frac{1}{2\sqrt2}(\sqrt 2+1)^n$$

然后注意到 $\sqrt2$ 在 $10^9$ 下存在。