快速 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