# 生成函数学习笔记

# 普通生成函数 (Ordinary Generating Function，OGF)

# 定义

定义序列 $a$ 的生成函数为 :

$$F(x) = \sum_{i = 0} ^{+\infty} a _{i} x ^{i}$$

# 运算

1. 加法运算

$$F(x) \pm G(x) = \sum _{i = 0} ^{+\infty} (a _{i} \pm b _{i}) x ^{i}$$

其意义为 $(a _{i} \pm b _{i})$ 序列的 生成函数

2. 乘法运算 (卷积)

普通型生成函数的乘法运算与 “多重集的组合问题有关”。

$$F(x) \ast G(x) = \sum _{i = 0} ^{+\infty} \left( \sum _{j = 0} ^{i} a _{j} b_{i-j} \right) x ^{i}$$

其意义为 $\sum _{i = 0} ^{n} a _{i} b_{n-i}$ 序列的 生成函数

# 封闭形式

根据等比数列求和公式，可得 :

$$F(x) = \sum_{i = 0} ^{+\infty} a _{i} x ^{i} = a _{0} \ast \frac{1 - x ^ {\infty}}{1 - x}$$

取 $x \in (-1, 1)$, 则有$1 - x ^{\infty} \to 1$, 即

$$F(x) = a _{0} \ast \frac{1 - x ^ {\infty}}{1 - x} = \frac{a _{0}}{1 - x}$$

# 牛顿二项式定理

定义组合数

$$\binom{n}{m} = \frac{n ^{\underline{m}}}{m !} \,, n \in \mathbf{C}, m \in \mathbf{N}$$

当 $n \in \mathbf{C}$ 时，

$$(x + 1) ^{n} = \sum _{i = 0} ^{+\infty} \binom{n}{i} x ^{i} = \sum _{i = 0} ^{+\infty} C _{n} ^{i} x ^{i}$$

# 指数型生成函数 (Exponential Generating Function, EGF)

# 定义

定义序列 $a$ 的指数型生成函数为

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

# 封闭形式

特别的， $0! = 1$。

首先我们来看都为 $1$ 数列 $\{1, 1, 1, 1, 1,...\}$ ，他所对应的指数型生成函数为 $F(x) = \sum\limits_{i = 0} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + ..$.
然后我们对他求个导数：
$F'(x) = \sum\limits_{i = 0} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} +...$
我们惊奇的发现，$F'(x) = F(x)$.
同时，$F(x) = 1$，且 $(e^x)' = e^x$ ，所以我们得出 $F(x) = e^x$，这也是这类函数被称作指数型母函数的原因。

类似于普通型生成函数和其封闭形式的转化 1，指数型生成函数也有类似的等式：

$$\begin{aligned} In~addition~&to~the~above~equations：\\ e^{kx} &= 1 + kx + k^2 \frac{x^2}{2} + k^3 \frac{x^3}{3!} + ... + k^n \frac{x^n}{n!} + ...\\ \frac{e^x + e^{-x}}{2} &= 1 + \frac{x^2}{2!} + \frac{x^4}{4!} + \frac{x^6}{6!} + ... + \frac{n^{2n}}{(2n)!}+...\\ \frac{e^x - e^{-x}}{2} &= x + \frac{x^3}{3!} + \frac{x^5}{5} + \frac{x^7}{7!} + ... + \frac{x^{2n+1}}{(2n+1)!} + ... \end{aligned}$$

# 乘法运算

指数型生成函数的乘法运算与 “多重集的排列问题有关”

我们举一个例子：
$F(x) = \sum\limits_{i = 0} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + ..$
$G(x) = \sum\limits_{i = 0} \frac{x^i}{i!} = 1 + x + \frac{x^2}{2} + \frac{x^3}{3!} + ..$
我们在两个多项式中任取一项相乘，$\frac{x^k x^{n-k}}{k! (n-k)!}$，取系数在乘上 $n!$ 得到 $\frac{n!}{k!(n-k)!} = C_n^k$。
当然生成函数的应用也不只有这些。

# OGF 和 EGF 的应用

# P2000 拯救世界

# 题目描述

老师要给我们留五科作业（当然是印卷子啦），卷子数不同对学生成绩的提升效果不同。
若想提高逻辑能力，则这套作业的组成如下：

1. 数学卷子必须是 $6$ 的倍数；
2. 物理卷子最多留 $9$ 张；
3. 化学卷子最多留 $5$ 张；
4. 生物卷子必须是 $4$ 的倍数；
5. 语文卷子最多留 $7$ 张。

若想提高计算能力，则这套作业的组成如下：

1. 数学卷子必须是 $2$ 的倍数；
2. 物理卷子最多留 $1$ 张；
3. 化学卷子必须是 $8$ 的倍数；
4. 生物卷子必须是 $10$ 的倍数；
5. 语文卷子最多留 $3$ 张。

现在我们有 $n$ 张卷子，教育处主任想知道如果把 $n$ 张卷子都组成这两种套卷发下去，最多能有多少种方案。现在，他找到了年级第一而且又 AK 了 IOI 的 Ptilopsis_w，并让他在 $1000 ms$ 内给出答案，然而 Ptilopsis_w 最烦的就是这种数数题了，他找到了热爱着计数的你，希望你能在 $500 ms$ 内作出回答。

$10^{99999} \le n < 10^{100000}$ (有时候人的崩溃就在一瞬之间)

# Solution of The Problem

显然两套卷子的组成方案对应着十个生成函数，我们只需要把他们乘起来，然后取出 $n$ 次项系数就好。 不就是多项式的化简约分嘛，很简单对吧（

$$\begin{aligned} f_1(x) &= \sum_{i = 0} x^{6i} = \frac{1}{1-x^6} \\ f_2(x) &= 1 + x^1+ x^2+ x^3+ x^4+ x^5+ x^6+ x^7+ x^8+ x^9 \\ f_3(x) &= 1 + x^1+ x^2+ x^3+ x^4+ x^5 \\ f_4(x) &= \sum_{i = 0} x^{4i} = \frac{1}{1-x^4} \\ f_5(x) &= 1 + x^1+ x^2+ x^3+ x^4+ x^5+ x^6+ x^7\\ f_6(x) &= \sum_{i = 0}x ^ {2i} = \frac{1}{1-x^2}\\ f_7(x) &= 1 + x \\ f_8(x) &= \sum_{i = 0} x^{8i} = \frac{1}{1-x^8} \\ f_9(x) &= \sum_{i = 0} x^{10i} = \frac{1}{1-x^{10}} \\ f_{10}(x) &= 1 + x + x^2 + x^3 \end{aligned}$$

接下来就是 振奋人心 （sang xin bing kuang） 的化简时间，显然易得，最后的式子是 $(1-x)^{-5}$，借助于广义二项式定理，第 $n$ 次项的系数就是 $\binom{n+4}{4}$
由于 $n$ 巨大，并且没有取模，所以只可以上高精，良心 （du liu） 的出题人卡了 FFT 的精度，所以要用 NTT。

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

# 题目描述

Ptilopsis_w 为了报答帮助他解决问题的你，他决定送你一份礼物，但是礼物盒上有个密码锁，上面有 $10$ 个数字，密码就是如下问题答案对 $1004535809$ 取模的结果。
灵水市有 $n$ 个城区，现在市政府决定在某些城区间铺上崭新的 摆油马路 ，使任意两个城区都通过新建的马路直接或间接的连接。同时，因为资金有限，两个城区之间最多只能铺一条马路。对于两种铺设马路的方案，
如果存在一个城区对，在两个方案中是否建立路线不一样，那么这两个方案就是不同的，否则就是相同的。问题是方案数（这不是肯定的嘛）。

# Solution of The Problem

我们设 $f_n$ 为 $n$ 个城区联通的方案数，$g_n$ 表示 $n$ 个城区铺路的方案数（不一定能相互到达）。对于$g_n$ 而言，每两个个城区都有连边或不连边两种选择，则 $g_n = 2^{\binom{n}{2}}$ 。

我们选择 $1$ 号城区所在连通块，其大小为 $x$，其他 $x-1$ 点的方案数为 $\binom{n-1}{x-1}$。
$g_n = \binom{n-1}{x-1} f_x \cdot g_{n-x}$.
把 $g$ 带入后，开始推式子：

$$\begin{aligned} 2^{\binom{n}{2}} &= \sum_{x = 1}^{n} \left( \frac{(n-1)!}{(x-1)! (n-x)!}\cdot f_x \cdot 2^{\binom{n-x}{2}} \right) \\ \frac{2^{\binom{n}{2}}}{(n-1)!} &= \sum_{x = 1}^{n} \left( \frac{f_x}{(x-1)!} \cdot \frac{2^{\binom{n-x}{2}}}{(n-x)!} \right) \\ \end{aligned}$$

很明显，上述式子是一个卷积形式。

下面，我们来构造多项式：
我们令
$A(x) = \sum\limits_{i = 1} \frac{f_i}{i!}x^{i}$.
对它求个导数，得到
$A'(x) = \sum\limits_{i = 1} \frac{f_i}{(i-1)!} x^{i-1}$.
再令
$F(x) = xA'(x) = \sum\limits_{i = 1} \frac{f_i}{(i-1)!} x^{i}$.
我们令
$G(x) = \sum\limits_{i = 0} \frac{2^{\binom{i}{2}}}{i!}x^{i}$.
对它求个导数，得到
$G'(x) = \sum\limits_{i = 0} \frac{2^{\binom{i}{2}}}{(i-1)!}x^{i-1}$.
再令
$H(x) = xG'(x) = \sum\limits_{i = 0} \frac{2^{\binom{i}{2}}}{(i-1)!}x^{i}$.

然后再根据我们之前推得的式子得出：$H(x) = F(x) * G(x)$，那么 $F(x) \equiv G(x) * H^{-1}(x)$。
至于答案嘛 . . . 就是 $F(x)$ 的 $n$ 次项系数喽。（多项式求逆就好了）

# P5488 差分与前缀和

# 题目描述

你成功的打开了这个装有神秘礼物的盒子，里面有一副令牌， Ptilopsis_w 解释道，它可以实现一个愿望，但需要正确回答问题，否则就要付出代价。听到这，你拿着它迅速跑回家（宿舍），许下了 AK IOI 的愿望，它将你带入它内部的世界，上面有一道题：
我是掌管人间百愿的神，若你能答对我将实现你的愿望，否则，将剥夺 $3$ 年的气运，这将是一道简单的问题，请在 $1000ms$ 内给出答案：一个长度为 $n$ 的序列，答出它的 $k$ 阶差分和前缀和。（$1 \le k \le 10^{2333}，k \not\equiv 0 \pmod{1004535809}$）

# Solution of The Problem

首先来考虑差分，该位置差分后数值上等于原数列该位置减去上个位置，对应到多项式里就是该项的系数减去上一项的系数，怎么搞能让上一项的系数对齐在该项并且变负呢 . . . 乘个 $(1-x)$ 就好了嘛。那么 $k$ 阶差分就需要乘 $k$ 次，当然不是真的整个多项式快速幂去硬乘，其实也不用这么麻烦。
$(1-x)^k = \sum\limits_{i = 0} \binom{k}{i}(-1)^i x^i$，可以 $O(n)$ 计算的。

那么接着来看前缀和，也是同样的道理。
前缀和 $c_n = \sum\limits_{i = 1}^n a_i = \sum\limits_{i = 1}^n a_i * b_i$，序列 $b$ 是一个都为 $1$ 的序列。
乘一个 $B(x) = \sum\limits_{i = 0} x^i$ 就相当于求一次前缀和，还是乘 $k$ 次就好了。
$B(x)$ 的封闭形式是 $\frac{1}{1-x}$， $B^k(x) = \frac{1}{(1-x)^k} = (1-x)^{-k}$.
运用广义二项式定理进行展开得到 $(1-x)^{-k} = \sum\limits_{i = 0} \binom{-k}{i} (-1)^i x^i$。
$i$ 无论是技术还是偶数，最后的化简结果都是一样的，$(1-x)^{-k} = \sum\limits_{i = 0} \frac{k^{\bar{\imath}}}{i!} x^i$。
一切问题只要卷起来就都解决了，既然模数是 NTT 模数那我就不客气了。

# P2012 拯救世界 2

# 题目描述

在你转身跑走之后， Ptilopsis_w 被 Mr.Yang 叫到了办公室，Mr.Yang 让 Ptilopsis_w 搞一搞统计班里信息的 Excel，布置完任务后转身忙去了。在 Ptilopsis_w 打开电脑后，发现有 $T$ 层密码保护，为了在 Mr.Yang 回来之前完成任务，他找到了你去破解写在桌子上的密码提示。
你看了一眼，发现这是与 Mr.Yupo 的协作下制造的密码：
某位 Dalao 的基因序列有 $12$ 种，A, B, C, D, E, F, G, H, I, J, K, L。经过一顿分析，A B C D 可以出现任意多个，E F G H 只可以出现奇数个，I J K L 只可以出现偶数个。每一层的密码是：若 Dalao 基因序列长度为 $n$ ，可能的组成方案数对 $10^9$ 取模的结果。时间紧迫，你只有 $1000ms$ 的时间破解密码。

# Solution of The Problem

这显然是一个多重集的排列问题，指数型生成函数 “板子题”。
考虑构造多项式

$$\begin{aligned} F(x) &= \sum_{i = 0} \frac{x^i}{i!} = e^x\\ G(x) &= \sum_{i = 0} \frac{x^{2i}}{(2i!)} = \frac{e^x+e^{-x}}{2}\\ H(x) &= \sum_{i = 0} \frac{x^{2i+1}}{(2i+1)!} = \frac{e^x-e^{-x}}{2}\\ \end{aligned}$$

将$F^4(x)$， $G^4(x)$， $H^4(x)$ 乘起来，取 $n$ 次项系数，再乘上 $n!$，取个模就成功了。

$$\Huge{To~be~continued . ~ . ~ .}$$

# P5110 块速递推

没时间写了，听我口胡吧 . . .