快速 GF 入门
xiezheyuan
·
·
算法·理论
前置知识
Maclaurin 展开式
Maclaurin 展开式利用多阶导数逼近，可以将一个函数展开成一个无穷级数的形式，公式如下：
f(x)=\sum_{k=0}^{+\infty}\frac{f^{(k)}(0)}{k!}x^k
常用公式：
\begin{aligned}
&e^x=\sum_{k=0}^{+\infty}\frac{x^k}{k!}\\
&\frac{1}{1-x}=\sum_{k=0}^{+\infty}x^k
\end{aligned}
前一个用于 EGF，后一个用于 OGF。
广义二项式定理
广义二项式系数：
\binom{m}{n}=\frac{1}{n!}\prod_{k=0}^{n-1}m-k
要求 n\in\mathbb{N},m\in\mathbb{R}。
同理还有广义二项式定理：
(x+y)^n=\sum_{k=0}^{+\infty}\binom{n}{k}x^{n-k}y^k
上指标反转，用于将上面的数转成正数：
\binom{n}{m}=(-1)^m\binom{m-n-1}{m}
普通生成函数
概述
数列 A_0,A_1,\cdots,A_\infty 的普通生成函数（OGF）为：
\sum_{k=0}^{+\infty}A_kx^k
例题 1
炸串店有 5 种素菜，3 种荤菜，奶茶店有 2 种奶茶。ytxy 要请我吃饭，求凑出 6 个菜的方案数（素菜与素菜、荤菜与荤菜、奶茶与奶茶之间互不区分）。
通过简单的手摸或者背包问题，可以知道答案是 11。我们考虑用普通生成函数的思想去理解这个问题。
对于素菜，我们构造数列 A=\{1,1,1,1,1,1,0,\cdots\}，其生成函数为 F=x^5+x^4+x^3+x^2+x+1。
对于荤菜，我们构造数列 B=\{1,1,1,1,0,\cdots\}，其生成函数为 G=x^3+x^2+x+1。
对于奶茶，我们构造数列 C=\{1,1,1,0,\cdots\}，其生成函数为 H=x^2+x+1。
然后我们考虑计算出 I=F\times G\times H：
I=x^{10} + 3 x^{9} + 6 x^{8} + 9 x^{7} + 11 x^{6} + 12 x^{5} + 11 x^{4} + 9 x^{3} + 6 x^{2} + 3 x + 1
然后我们发现 x^6 的系数（下面记作 [x^6]I）就是答案。
为什么呢？考虑多项式乘法的过程，凑出 x^6 其实就是在 F 中选一个指数 i，G 中选出一个指数 g，H 中选出一个指数 h，使得 i+g+h=6，这和我们暴力凑数的思想是一样的。
例题 2
Link
考虑计算每种食物的普通生成函数，然后将其乘起来找第 n 项系数：
承德汉堡：偶数个：\{1,0,1,0,\cdots\}，生成函数为：
\sum_{k=0}^{+\infty}x^{2k}
发现这是一个无穷级数的形式处理不方便，但是我们发现它的封闭形式为：
\frac{1}{1-x^2}
所以我们就用这个形式来表达它的普通生成函数。
可乐：0 个或 1 个：\{1,1,0,0,\cdots\}，生成函数为：
x+1
鸡腿：0\sim2 个：\{1,1,1,0,0,\cdots\}，生成函数为：
x^2+x+1
蜜桃多：奇数个：\{0,1,0,1,\cdots\}，生成函数为：
\sum_{k=0}^{+\infty}x^{2k+1}=x\sum_{k=0}^{+\infty}x^{2k}=\frac{x}{1-x^2}
鸡块：4 的倍数个：\{1,0,0,0,1,0,\cdots\}，生成函数为：
\sum_{k=0}^{+\infty}x^{4k}=\frac{1}{1-x^4}
包子：0\sim3 个：\{1,1,1,1,0,0,\cdots\}，生成函数为：
x^3+x^2+x+1
土豆片炒肉：不超过一个：\{1,1,0,0,\cdots\}，生成函数为：
x+1
面包：3 的倍数个：\{1,0,0,1,0,\cdots\}，生成函数为：
\sum_{k=0}^{+\infty}x^{3k}=\frac{1}{1-x^3}
我们将这些乱七八糟的东西乘起来，得到：
\begin{aligned}
&(\frac{1}{1-x^2})(x+1)(x^2+x+1)(\frac{x}{1-x^2})(\frac{1}{1-x^4})(x^3+x^2+x+1)(x+1)(\frac{1}{1-x^3})\\
&=\frac{x}{x^{4} - 4 x^{3} + 6 x^{2} - 4 x + 1}\\
&=\frac{x}{(x-1)^4}
\end{aligned}
然后我们将这个东西展开，你可以广义二项式定理，当然也可以直接展开。但是直接展开太麻烦了，我们还是广义二项式定理吧：
\begin{aligned}
&\frac{x}{(x-1)^4}\\
&=x(x-1)^{-4}\\
&=x\sum_{k=0}^{+\infty}\binom{-4}{k}x^{k}(-1)^{-4-k}\\
&=x\sum_{k=0}^{+\infty}(-1)^k\binom{k+3}{k}x^k(-1)^{-4-k}\\
&=x\sum_{k=0}^{+\infty}\binom{k+3}{k}x^k\\
&=\sum_{k=1}^{+\infty}\binom{k+2}{k-1}x^k\\
&=\sum_{k=1}^{+\infty}\frac{1}{6}k(k+1)(k+2)x^k
\end{aligned}
所以答案就是 \frac{1}{6}k(k+1)(k+2)。
指数生成函数
概述
数列 A_0,A_1,\cdots,A_\infty 的指数生成函数（EGF）为：
\sum_{k=0}^{+\infty}\frac{x^k}{k!}A_k
例题 1
有红绿蓝三种彩灯，红色彩灯共三个，绿色彩灯共四个，蓝色彩灯共两个，求选出 6 个彩灯摆成一排的方案数。（同种颜色的彩灯之间互不区分）
可以写一个程序，枚举所有情况，计算答案应该是 410 个。
我们发现这和前面的问题区别在于不同物品之间存在顺序。无法使用普通生成函数。
我们考虑构造指数生成函数。
红色彩灯的数列是 \{1,1,1,1,0,\cdots\}，其指数生成函数为：
A=\frac{1}{6}x^3+\frac{1}{2}x^2+x+1
同理，绿色彩灯的数列是 \{1,1,1,1,1,0,\cdots\}，其指数生成函数为：
B=\frac{1}{24}x^4+\frac{1}{6}x^3+\frac{1}{2}x^2+x+1
同理，蓝色的数列是 \{1,1,1,0,\cdots\}，其指数生成函数为：
C=\frac{1}{2}x^2+x+1
考虑计算 I=A\times B\times C。答案为：
\frac{x^{9}}{288} + \frac{x^{8}}{32} + \frac{23 x^{7}}{144} + \frac{41 x^{6}}{72} + \frac{3 x^{5}}{2} + \frac{71 x^{4}}{24} + \frac{13 x^{3}}{3} + \frac{9 x^{2}}{2} + 3 x + 1
改成指数生成函数的形式：
1+3x+\frac{9}{2!}x^2+\frac{13}{3!}x^3+\frac{71}{24}x^4+\frac{180}{5!}x^5+\frac{410}{6!}x^6+\frac{805}{7!}x^7+\frac{1260}{8!}x^8+\frac{1260}{9!}x^{9}
可以发现 x^6 的系数就是 \frac{410}{6!} 和答案吻合。
为什么呢？
考虑一个最简单的问题，有 n 个格子，我们将其 m 个位置涂黑，这方案数应该是 \binom{n}{m}，而我们统一除上阶乘就不用这个二项式系数了。
大概就是这样的一个意思。
例题 2
用红蓝绿 3 种颜色去涂 1\times n 的棋盘，每格涂一种颜色，求使得被涂成红色和蓝色的方格数均为偶数的的涂色方法数。
考虑红色和蓝色，数列为 \{1,0,1,0,\cdots\}，生成函数为：
\begin{aligned}
&\sum_{k=0}^{+\infty}\frac{x^{2k}}{(2k)!}\\
&=\frac{1}{2}\left(\sum_{k=0}^{+\infty}\frac{x^k}{k!}+\sum_{k=0}^{+\infty}\frac{(-x)^k}{k!}\right)\\
&=\frac{e^x+e^{-x}}{2}
\end{aligned}
而绿色，数列为 \{1,1,1,\cdots\}，生成函数为：
\begin{aligned}
&\sum_{k=0}^{+\infty}\frac{x^k}{k!}\\
&=e^x
\end{aligned}
所以答案的生成函数为：
\begin{aligned}
&e^x\left(\frac{e^x+e^{-x}}{2}\right)^2\\
&=\frac{1}{4}e^x\left(e^{2x}+e^{-2x}+2\right)\\
&=\frac{1}{4}(e^{3x}+2e^{x}+e^{-x})\\
&=\sum_{k=0}^{+\infty}\frac{(-1)^n+3^n+2}{4}\cdot\frac{x^k}{k!}
\end{aligned}
所以答案便是 \frac{(-1)^n+3^n+2}{4}。
课后作业：试证明 m=\frac{(-1)^n+3^n+2}{4}，对于 n\in\mathbb{N} 而言，m\in\mathbb{Z}^{+}。
单位根反演
前置知识
复数、单位根、等比数列求和公式。
概述
虽然说单位根反演本身和生成函数关系没有那么紧密，但是在一些毒瘤题目（比如白兔之舞）是有应用的。
基本公式：
[n\mid m]=\frac{1}{n}\sum_{k=0}^{n-1}\omega_n^{mk}
Proof：
- 若 m\equiv0\pmod{n}，那么 \omega_n^{mk}=1，所以原式为 \frac{1}{n}\times n = 1。
- 若 m\not\equiv0\pmod{n}，那么我们利用等比数列求和公式得到后面的求和式为 1\times\frac{1-\omega_n^{mn}}{1-\omega_n^{m}}，由于 \omega_n^{mn}=1，所以后面的求和式等于 0，所以原式等于 0。
常见形式
\sum_{k=0}^{m}[n\mid k]f_k=\frac{1}{n}\sum_{k=0}^{m}f(\omega_n^k)
其中 f 为多项式。
证明是平凡的，读者不难自证。
习题
BZOJ 3028. 食物
就是 OGF 的例题 2。只需要注意读入 n 的时候需要顺便取模。
Code
P2000 拯救世界
OGF 练习题。
先考虑 kkk。
金神石的块数必须是 6 的倍数；
\frac{1}{1-x^6}
木神石最多用 9 块；
x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1
水神石最多用 5 块；
x^5+x^4+x^3+x^2+x+1
火神石的块数必须是 4 的倍数；
\frac{1}{1-x^4}
土神石最多用 7 块。
x^7+x^6+x^5+x^4+x^3+x^2+x+1
然后是 lzn：
金神石的块数必须是 2 的倍数；
\frac{1}{1-x^2}
木神石最多用 1 块；
x+1
水神石的块数必须是 8 的倍数；
\frac{1}{1-x^8}
火神石的块数必须是 10 的倍数；
\frac{1}{1-x^{10}}
土神石最多用 3 块。
x^3+x^2+x+1
然后丧心病狂地将这些东西全部乘起来就好了，得到：
\begin{aligned}
&- \frac{1}{x^{5} - 5 x^{4} + 10 x^{3} - 10 x^{2} + 5 x - 1}\\
&=\frac{1}{(1-x)^5}\\
&=(1-x)^{-5}\\
&=\sum_{k=0}^{+\infty} \binom{-5}{k}(-x)^k\\
&=\sum_{k=0}^{+\infty}(-1)^k\binom{k+4}{k}(-1)^kx^k\\
&=\sum_{k=0}^{+\infty}\binom{k+4}{k}x^k
\end{aligned}
所以答案是 \binom{n+4}{n}。至于高精度，用 python 即可。注意如果用默认的 int 会炸，要用 decimal.Decimal。
Submission
HDU-2065 "红色病毒"问题
EGF 练习题。
A,C 都要求出现偶数次，生成函数为：
\sum_{k=0}^{+\infty}\frac{x^{2k}}{k!}=\frac{e^x+e^{-x}}{2}
B,D 无特殊限制，生成函数为：
\sum_{k=0}^{+\infty}\frac{x^k}{k!}=e^x
所以答案的生成函数为：
\begin{aligned}
&e^{2x}\left(\frac{e^x+e^{-x}}{2}\right)^2\\
&=\frac{1}{4}e^{2x}(e^{2x}+e^{-2x}+2)\\
&=\frac{1}{4}(e^{4x}+2e^{2x}+1)\\
&=\frac{1}{4}+\frac{1}{4}\left(\sum_{k=0}^{+\infty}(4^k+2^{k+1})\frac{x^k}{k!}\right)
\end{aligned}
所以答案便是 \frac{1}{4}(4^k+2^{k+1})=4^{k-1}+2^{k-1}。
Submission
P2012 拯救世界2
题号好评！
对于乾、坎、艮、震，只能出现奇数次，即：
\sum_{k=0}^{+\infty}\frac{x^{2k+1}}{(2k+1)!}=\frac{e^x-e^{-x}}{2}
对于坤、兑、离、巽，只能出现偶数次，即：
\sum_{k=0}^{+\infty}\frac{x^{2k}}{(2k)!}=\frac{e^x+e^{-x}}{2}
对于 A、C、T、G，无特殊限制，即：
\sum_{k=0}^{+\infty}\frac{x^k}{k!}=e^x
所以答案的生成函数就是：
\begin{aligned}
&e^{4x}\left(\frac{e^x-e^{-x}}{2}\right)^4\left(\frac{e^x+e^{-x}}{2}\right)^4\\
&=\frac{1}{256}e^{4 x} (e^x - e^{-x})^4 (e^{-x} + e^x)^4\\
&=\frac{1}{256}\left(-4 + e^{-4 x} + 6 e^{4 x} - 4 e^{8 x} + e^{12 x}\right)\\
&=-\frac{1}{64}+\frac{1}{256}(e^{-4x}+6e^{4x}-4e^{8x}+e^{12x})\\
&=-\frac{1}{64}+\frac{1}{256}\sum_{k=0}^{+\infty}((-4)^k+6\cdot4^k-4\cdot8^k+12^k)\frac{x^k}{k!}
\end{aligned}
所以答案就是：
\begin{aligned}
&\frac{(-4)^k+6\cdot4^k-4\cdot8^k+12^k}{256}\\
&=3\times2^{2 k - 7}- 2^{3 k - 6}+ (-1)^k 4^{k - 4} + 3^k 4^{k - 4}
\end{aligned}
这道题数据范围特别大，朴素快速幂好像不是很能过的样子，而模数又不是质数，可以使用扩展欧拉定理优化，并且使用光速幂。
最后一堆细节处理，但是本题并不卡常。
Submission
P4451 [国家集训队] 整数的lqp拆分
首先考虑如果对于每一个 a_i=i 构造一个生成函数是极其不现实的。
我们考虑设斐波那契数列 f 的生成函数为 F(x)，则容易发现恰好取 k 个的生成函数是 F^k(x)。则本题我们可以枚举这个 k，答案的生成函数为：
\sum_{k=0}^{+\infty}F^k(x)=\frac{1}{1-F(x)}
然后考虑我们怎么计算 F(x)。感兴趣自己在网上找推导：
F(x)=\frac{x}{1-x-x^2}
好，记住这个结论，我们继续。
则答案的生成函数为：
\frac{x^2 + x - 1}{x^2 + 2 x - 1}
好，这玩意怎么展开呢？
我不太会，所以我们直接找一个网站来帮我们算，最后结论为：
\frac{x^2 + x - 1}{x^2 + 2 x - 1}=\sum_{k=0}^{+\infty}\frac{-(1-\sqrt{2})^n+(1+\sqrt{2})^n}{2\sqrt{2}}x^n
好，然后我们发现 2 存在模 10^9+7 意义下的二次剩余（59713600），所以这道题就做完了。
答案为：
\frac{-(1-\sqrt{2})^n+(1+\sqrt{2})^n}{2\sqrt{2}}
Submission