隐藏
生成函数在信息学竞赛中的应用 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

生成函数在信息学竞赛中的应用

真是奇怪啊,为什么我是先学生成函数的应用再学生成函数的概念的啊

在数学中,生成函数(generating function,又称母函数)是一种形式幂级数,个人认为生成函数这个名字更为优美。

生成函数是一个无穷级数,我们只关心生成函数的系数。
某些时候,我们只关心生成函数的前$n$项系数,也就是$A(x)\pmod x^n$,在多项式取模处有所叙述。

在OI中,我们常常用到两类生成函数:普通(组合)型生成函数指数型生成函数

普通型生成函数

定义

普通型生成函数的一般表示形式

我们将其系数$a_i$提取出来,得到其系数表示$(a_0,a_1,a_2,\cdots)$的行向量。

普通型生成函数一般用于解决组合问题,也就是不考虑顺序影响的问题。

举个栗子:(来自ruanx)

你有一些水果,只能拿3的倍数个苹果,只能拿质数个草莓。问对于每个$0<i\le n$,有多少种方案使得恰好拿$i$个水果。

我们不妨先造出两个bool数组,来储存“能不能拿”。
苹果:[0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1...]
草莓:[0,0,1,1,0,1,0,1,0,0,0,1,0,1,0,0...]

我们可以构造上面两个bool数组的生成函数:
苹果:$A(x)=x^3+x^6+x^9+\cdots=x^{3i}$
草莓:$B(x)=x^2+x^5+x^7+\cdots$

我们把它们乘起来,就会发现一个奇妙的事情:乘积的结果,$x^k$的系数正好表示了取$k$个物品的方案数。

为什么会这样?考虑$x^5$的系数。$x^5$可以由$x^0\cdot x^5,x^1\cdot x^4,x^2\cdot x^3,x^3\cdot x^2\cdots$来构成,这正好映射了“$0$个苹果$5$个草莓、$1$个苹果$4$个草莓$\ldots$”的选取方式。

更加精确地讲,实际上是因为这是一个类似背包的问题,背包可以写作卷积形式,而生成函数正是处理这种卷积形式的工具。

项的意义

继续用背包问题来理解普通型生成函数。
若有$a_i$个重量为$w_i$的物品,那么在生成函数中重量$w_i$所能作出贡献的项就应该累加上$a_i$。

如,若有一个重量为$w_1$的物品,其生成函数的表示即为$x^0+x^{w_1}=\sum\limits_{i=0}^1x^{iw_1}$,其中的$0$次幂表示不选该物品。
再如,有$3$个重量为$w_2$的物品,其生成函数的表示即为$x^0+x^{w_2}+x^{2w_2}+x^{3w_2}=\sum\limits_{i=0}^3x^{iw_2}$。
再如,有$+\infty$个重量为$w_3$的物品,其生成函数的表示即为$x^0+x^{w_3}+x^{2w_3}+x^{3w_3}+\cdots=\sum\limits_{i=0}^{+\infty}x^{iw_2}$。

闭形式

我们可以利用等比数列求和公式对某些呈等比数列的普通型生成函数进行求和,如:

称$\frac{1}{1-x}$为生成函数$(1,1,1,\ldots)$的闭形式

闭形式也是生成函数的一种表达方式,与系数表示等价。

又如$A(x)\bmod x^5=\sum\limits_{i=0}^4x^i$的闭形式为:

根据等比数列求和可以写出生成函数的闭形式。
根据扩展到负指数的二项式定理可以将闭形式展开成为系数表示或一般表示。

扩展到负指数的二项式定理:

当$n\gt0$时有:

例如,闭形式

又如,闭形式

例题

指数型生成函数

定义

指数型生成函数的一般表示形式

同样的,我们将其系数$\frac{a_i}{i!}$提取出来,得到其系数表示$(a_0,\frac{a_1}{1},\frac{a_2}{2},\cdots)$的行向量。

指数型生成函数一般用于解决排列问题,也就是考虑顺序影响的问题。

举个栗子:

你有$4$个数:$1,2,3,4$,每个数最多选择$2$次,现在用这$4$个数组成一些多位数,问对于每个$0<i\le n$,有多少个$i$位数可以由上述规则组成。

给次数编号,构造每个数的指数型生成函数:$F(x)=(0,1,\frac12,0,0,\ldots)$。
考虑,构成一个$i$位数,相当于对出现次数做一个卷积,也就是将编过号的次数重分配标号给位置
计算$F^4(x)$,其结果的$i$次幂项系数乘上阶乘$[x^i]F^4(x)\cdot i!$就是答案。

闭形式

结合麦克劳林级数:

如:
$\sum\limits_{i=0}^{+\infty}\frac{x^i}{i!}$的闭形式为$e^x$。

普通型与指数型的对比

普通型生成函数比较少见,一般的高端数论题均使用的是指数型生成函数。
普通型生成函数解决组合问题,也就是说顺序不同不算作多种方案。
正因为有了这个限制,对于一个物品不能构造一个生成函数$x^{w_i}$让其自乘,因为同一方案会算重,故需要将生成函数包含其的幂全部填上。
而指数型生成函数与前者不同,指数型生成函数用于解决排列问题,也就是说顺序不同算作多种方案(包含标号重分配的过程)。
故不需要像普通型生成函数那样填上后面的所有幂次,只需要将其对应的幂次填上,自乘即可。

在计数问题中,通常都包含标号重分配的过程,因此通常使用指数型生成函数。

运算

生成函数的运算遵从多项式运算规则

参考资料

姥爷们赏瓶冰阔落吧~