普通型生成函数入门

Part 1 普通型生成函数 OGF（$\mathtt{O}$rdinary $\mathtt{G}$enerating $\mathtt{F}$unction）

普通型生成函数的特征函数是 $f_i(x)=x^i$。

1.0 形式幂级数形式

回到生成函数的定义：

$F(x)=\sum\limits_{i=0}^\infin a_if_i(x)$

OGF 的特征函数是 $f_i(x)=x^i$，也就是说，OGF 总是可以写成这样的形式：

$F(x)=\sum\limits_{i=0}^\infin a_ix^i$

由于 $x$ 是无关紧要的，只是一个形式，并且这种写法带次幂，所以它被叫做形式幂级数形式。

注意到这种形式可以很方便地将生成函数还原回序列，所以从生成函数还原到序列之前往往要先化为形式幂级数形式。

1.1 OGF 的一些运算的意义

为了方便运算，所以生成函数往往规定原序列的负数项为 $0$。

假设有两个序列 $a$，$b$ 和它们的 OGF $F(x)$，$G(x)$，那么：

• 相加

  $\begin{aligned} H(x)&=F(x)+G(x)\\ &=\sum\limits_{i=0}^\infin (a_i+b_i)x^i \end{aligned}$

  相当于是 $a$ 和 $b$ 对应项相加的序列 $c_i=a_i+b_i$ 的 OGF；

• 相减

  $\begin{aligned} H(x)&=F(x)-G(x)\\ &=\sum\limits_{i=0}^\infin (a_i-b_i)x^i \end{aligned}$

  相当于是 $a$ 和 $b$ 对应项相减的序列 $c_i=a_i-b_i$ 的 OGF；

• 乘 $x$

  $\begin{aligned} xF(x)&=\sum\limits_{i=0}^\infin a_ix^{i+1}\\ &=\sum\limits_{i=0}^\infin a_{i-1}x^{i} \end{aligned}$

  相当于把原序列整体右移一位；

• 相乘

  $\begin{aligned} H(x)&=F(x)G(x)\\ &=\left(\sum\limits_{i=0}^\infin a_ix^i\right)\left(\sum\limits_{i=0}^\infin b_ix^i\right)\\ &=\sum\limits_{i=0}^\infin x^i\sum\limits_{j=0}^ia_jb_{i-j} \end{aligned}$

  相当于是 $c_i=\sum\limits_{j=0}^ia_jb_{i-j}$ 的 OGF。组合意义如下：

  $c_i$ 表示把 $i$ 个无标号小球放入 $A$ 和 $B$ 两个有标号无序集合中，其中 $A$ 集合中放 $i$ 个球的方案数是 $a_i$，$B$ 集合中放 $i$ 个球的方案数是 $b_i$。

1.2 封闭形式

$a=\{1,1,\dots\}$ 这个数列的 OGF 的形式幂级数形式是 $F(x)=\sum\limits_{i=0}^\infin x^i$，考虑用更简洁的方法表示 $F(x)$：

$\text{令 } G_n(x)=\sum\limits_{i=0}^nx^i\\ \begin{aligned} &G_{n+1}(x)-G_n(x)\\ &=x^{n+1}\\ &=1+xG_n(x)-G_n(x)\\ &=1+(x-1)G_n(x) \end{aligned}\\ \text{所以}\\ 1+(x-1)G_n(x)=x^{n+1}\\ G_n(x)=\frac{x^{n+1}-1}{x-1}\\ \text{代入 }n=\infin,-1<x<1\\ F(x)=G_{\infin}(x)=\frac{-1}{x-1}=\frac{1}{1-x}\\$

也就是说，当 $-1<x<1$ 时，$F(x)=\frac{1}{1-x}$，这种**“最简形式”被定义为生成函数的封闭形式**。由于我们并不关心 $x$ 的取值，所以可以认为 $F(x)=\frac{1}{x-1}$。注意到封闭形式有利于对生成函数进行各种运算，所以往往要把生成函数化为封闭形式再进行各种推导。

总结一下，利用生成函数来对数列进行各种推导主要分成以下几步：

1. 确定特征函数，写出数列对应的生成函数的形式幂级数形式；
2. 根据生成函数的形式幂级数形式求出它的封闭形式；
3. 对所有要参加推导的数列都重复前两步以确定它们的生成函数的封闭形式；
4. 根据题目的需要，对这些封闭形式进行各种运算；
5. 将运算的结果还原回形式幂级数形式，获得答案序列；

1.3 一些常见数列的 OGF 的封闭形式

$a=\{y,yp,yp^2,yp^3,yp^4,\dots\}\\ a=\{0,1,1,1,1,\dots\}\\ a=\{0,1,0,1,0,\dots\}\\ a=\{1,2,3,4,5,\dots\}\\ a_i=\binom{n}{i}\qquad n\text{ 是给定的常数}\\ a_i=\binom{n+i}{n}\qquad n\text{ 是给定的常数}\\ a_i=a_{i-1}+a_{i-2},a_0=1,a_1=1\qquad\text{并推导出通项公式}\\ a_i=\sum\limits_{j=0}^{i-1}a_{j}a_{i-j-1},a_0=1$

第一个：

$\begin{aligned} F(x)&=y\sum\limits_{i=0}^\infin p^ix^i\\ &=y(1+xpF(x))\\ &=\frac{y}{1-xp} \end{aligned}$

第二个：

$\begin{aligned} F(x)&=\sum\limits_{i=1}^{\infin}x^i\\ &=x\sum\limits_{i=0}^{\infin}x^i\\ &=\frac{x}{1-x}\\ \end{aligned}$

第三个：

$\begin{aligned} F(x)&=\sum\limits_{i=0}^{\infin}[i=2j+1]x^i\\ &=\sum\limits_{i=0}^{\infin}x^{2i+1}\\ &=x\sum\limits_{i=0}^{\infin}(x^2)^i\\ &=\frac{x}{1-x^2}\\ \end{aligned}$

第四个：

$\, \begin{aligned} F(x)&=\sum\limits_{i=0}^{\infin}(i+1)x^i\\ &=\sum\limits_{i=0}^{\infin}ix^i+\sum\limits_{i=0}^{\infin}x^i\\ &=xF(x)+\frac{1}{1-x} \end{aligned}\\ (1-x)F(x)=\frac{1}{1-x}\\ F(x)=\frac{1}{(1-x)^2}$

第五个：

$\begin{aligned} F(x)&=\sum\limits_{i=0}^{n}\binom{n}{i}x^i\\ &=(1+x)^i\\ \end{aligned}$

第六个：

考虑组合意义，$\binom{n+i}{n}$ 相当于把 $n+i+1$ 个相同的小球放进 $n+1$ 个不同的盒子里的方案数，相当于 $x_1+x_2+\dots+x_{n+1}=i$ 的不同非负整数解的个数，相当于 $n+1$ 个 $F(x)=\sum\limits_{i=0}^{\infin}x^i$ 乘起来即 $\left(\sum\limits_{i=0}^{\infin}x^i\right)^{n+1}$，写成封闭形式即为 $(\frac{1}{1-x})^{n+1}=\frac{1}{(1-x)^{n+1}}$。

所以 $F(x)=\frac{1}{(1-x)^{n+1}}$。

第七个：

$a_i$ 就是斐波那契数列的第 $i$ 项。

显然有 $F(x)=xF(x)+x^2F(x)-xa_0+a_0+xa_1=1+xF(x)+x^2F(x)$，解得 $F(x)=\frac{1}{1-x-x^2}$。

进一步的，我们可以推导出 $a_i$ 的通项公式：

$\begin{aligned} F(x)&=\frac{1}{1-x-x^2}\\ &=\sum\limits_{i=0}^\infin (x+x^2)^i\\ &=\sum\limits_{i=0}^\infin \sum\limits_{j=0}^i \binom{i}{j}x^{i+j}\\ &=\sum\limits_{i=0}^\infin x^i\sum\limits_{j=0}^i \binom{i-j}{j}\\ \end{aligned}$

即 $a_i=\sum\limits_{j=0}^i \binom{i-j}{j}$。

但是这个式子是 $O(n)$ 的，并不是我们熟悉的带 $\sqrt 5$ 的神秘 $O(1)$ 通项。

下面将用另一种方式推出 $O(1)$ 的通项，考虑一类我们熟悉的 OGF —— $yF(x)=\sum\limits_{i=0}^\infin p^iyx^i=\frac{y}{1-xp}$，由于斐波那契数列的生成函数的封闭形式是 $\frac{1}{1-x-x^2}$，所以需要至少两个这样的 OGF 加起来通分之后才能出现最高次项，那么设：

$\begin{aligned} \frac{1}{1-x-x^2}&=\frac{A}{1-ax}+\frac{B}{1-bx}\\ &=\frac{A(1-bx)+B(1-ax)}{(1-ax)(1-bx)}\\ &=\frac{A+B-(aB+Ab)x}{1-(a+b)x+abx^2}\\ \end{aligned}$

所以有：

$\begin{cases} aB+Ab=0\\ A+B=1\\ a+b=1\\ ab=-1 \end{cases}$

解得：

$\begin{cases} a=\frac{1-\sqrt 5}{2}\\ b=\frac{1+\sqrt 5}{2}\\ A=\frac{1}{2}-\frac{\sqrt 5}{10}\\ B=\frac{1}{2}+\frac{\sqrt 5}{10} \end{cases}$

所以有

$\begin{aligned} F(x)&=\sum\limits_{i=0}^\infin \left((\frac{1}{2}-\frac{\sqrt 5}{10})(\frac{1-\sqrt 5}{2})^i+(\frac{1}{2}+\frac{\sqrt 5}{10})(\frac{1+\sqrt 5}{2})^i\right)x^i\\ &=\sum\limits_{i=0}^\infin \left(\frac{(1-\frac{\sqrt 5}{5})(\frac{1-\sqrt 5}{2})^i+(1+\frac{\sqrt 5}{5})(\frac{1+\sqrt 5}{2})^i}{2}\right)x^i\\ \end{aligned}$

第八个：

$a_i$ 就是卡特兰数的第 $i$ 项。

发现这个递推式很像卷积，所以考虑用卷积构造它的生成函数。

设 $F(x)=\sum\limits_{i=0}^\infin a_ix^i$，则有：

$\begin{aligned} F(x)&=1+\sum\limits_{i=1}^\infin x^i\sum\limits_{j=0}^{i-1}a^ja^{i-j-1}\\ &=1+x\sum\limits_{i=0}^\infin x^i\sum\limits_{j=0}^ia^ja^{i-j}\\ &=1+xF^2(x)\\ &=\frac{1\pm\sqrt{1+4x}}{2x} \end{aligned}$

现在的问题是取哪个根，我们将其分子有理化：

$F(x)=\frac{2}{1\pm\sqrt{1+4x}}$

代入 $x=0$，这样 $F(x)=a_0=1$，显然若分母应取 $1+\sqrt{1+4x}=2$，所以 $F$ 的封闭形式为 $F(x)=\frac{1-\sqrt{1+4x}}{2x}$。

1.4 应用

1.4.0 BZOJ3028 食物

在许多不同种类的食物中选出 $n$ 个，每种食物的限制如下：

1. 承德汉堡：偶数个
2. 可乐：$0$ 个或 $1$ 个
3. 鸡腿：$0$ 个，$1$ 个或 $2$ 个
4. 蜜桃多：奇数个
5. 鸡块：$4$ 的倍数个
6. 包子：$0$ 个，$1$ 个，$2$ 个或 $3$ 个
7. 土豆片炒肉：不超过一个。
8. 面包：$3$ 的倍数个

每种食物都是以“个”为单位，只要总数加起来是 $n$ 就算一种方案。对于给出的 $n$ 你需要计算出方案数，对 $10007$（质数）取模。

考虑对每种食物构造多项式，由于两种食物选出 $n$ 个的方案数的生成函数就是它们的生成函数的卷积，所以多种食物总共选出 $n$ 个的方案数的生成函数就是他们的生成函数全部卷到一起的结果。

接下来问题就变为求出每种食物的生成函数的封闭形式然后乘起来，最后还原回形式幂级数形式，得到答案。

这里给出每种食物的生成函数的封闭形式：

1. $\frac{1}{1-x^2}$
2. $1+x$
3. $1+x+x^2=\frac{1-x^3}{1-x}$
4. $\frac{x}{1-x^2}$
5. $\frac{1}{1-x^4}$
6. $1+x+x^2+x^3=\frac{1-x^4}{1-x}$
7. $1+x$
8. $\frac{1}{1-x^3}$

接下来要把它们乘起来：

$\begin{aligned} &\frac{(1+x)(1-x^3)x(1-x^4)(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x^4)(1-x)(1-x^3)}\\ &=\frac{(1+x)x(1+x)}{(1-x^2)(1-x)(1-x^2)(1-x)}\\ &=\frac{(1+x)x(1+x)}{(1-x)(1+x)(1-x)(1-x)(1+x)(1-x)}\\ &=\frac{x}{(1-x)(1-x)(1-x)(1-x)}\\ &=\frac{x}{(1-x)^4}\\ \end{aligned}$

考虑到 $\frac{x}{(1-x)^4}=x(\frac{1}{1-x})^4$，相当于四个 $\{1,1,1,1,1,\dots\}$ 的生成函数乘起来再让系数整体右移一位，也就是 $x\sum\limits_{i=0}^\infin\binom{i+3}{3}x^i=\sum\limits_{i=0}^\infin\binom{i+2}{3}x^i$，那么答案即为 $\binom{n+2}{3}$。

1.4.1 [P6078 [CEOI2004] Sweets](https://www.luogu.com.cn/problem/P6078)

第 $i$ 种糖果的生成函数显然是 $\frac{1-x^{m_i+1}}{1-x}$，答案的生成函数就是 $\frac{\prod\limits_{i=1}^n 1-x^{m_i+1}}{(1-x)^n}$。

考虑暴力展开，显然由于 $a_i=\binom{n+i}{n}$ 的生成函数的封闭形式就是 $\frac{1}{(1-x)^{n+1}}$，所以答案的生成函数可以化为：

$\left(\prod\limits_{i=1}^n 1-x^{m_i+1}\right)\sum\limits_{i=0}^\infin \binom{n+i-1}{i}x^i$

前面的部分可以 $O(2^n)$ 暴力求出 $x$ 的所有指数对应的系数 $y_ix^{k_i}$，那么对于所有二元组 $(y_i,k_i)$，它对答案的贡献即为：

$\begin{aligned} &y_i\sum\limits_{j=a-i}^{b-k_i} \binom{n+j-1}{j}\\ &=y_i\left(\sum\limits_{j=0}^{b-k_i} \binom{n-1+j}{j}-\sum\limits_{j=0}^{a-k_i-1} \binom{n-1+j}{j}\right)\\ &=y_i\left(\binom{n-1+b-k_i+1}{b-k_i}-\binom{n-1+a-k_i-1+1}{a-k_i-1}\right)\\ &=y_i\left(\binom{n+b-k_i}{b-k_i}-\binom{n+a-k_i-1}{a-k_i-1}\right)\\ &=y_i\left(\binom{n+b-k_i}{n}-\binom{n+a-k_i-1}{n}\right)\\ \end{aligned}$

注意到组合数可以直接暴力 $O(n)$ 计算（$\binom{n}{m}=\frac{n!}{m!(n-m)!}$，由于 $m!$ 很小，所以可以暴力计算 $n\times (n-1)\times(n-2)\times\dots\times(n-m+1)\mod 2004m!$ 然后除以 $m!$ 再模 $2004$），时间复杂度即为 $O(n2^n)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=15,p=2004;

int n,a,b;
int m[S];

inline int C(int n,int m)
{
	if(n<0||m<0||m>n) return 0;
	long long mod=p;
	long long r1=1,r2=1;
	for(int i=1;i<=m;i++) r1*=i,mod*=i;
	for(int i=n;i>=n-m+1;i--) r2=r2*i%mod;
//	printf("C(%d %d)=%d\n",n,m,r2/r1);
	return r2/r1%p;
}

int dfs(int i,int y,int k)
{
	if(i==n+1) return (y*(C(n+b-k,n)-C(n+a-k-1,n))+p)%p;
	return (dfs(i+1,y,k)+dfs(i+1,-y,k+m[i]+1))%p;
}

int main()
{
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++) scanf("%d",&m[i]);
	printf("%d\n",dfs(1,1,0));
	return 0;
}