不严谨 GF 笔记

Xie Zheyuan / 2024-04-23 / 原文

不严谨 GF 笔记

前置知识

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