指数型生成函数入门

Part 2 指数型生成函数 EGF（$\mathtt{E}$xponential $\mathtt{G}$enerating $\mathtt{F}$unction）

指数型生成函数的特征函数是 $f_i(x)=\frac{x^i}{i!}$。

2.0 形式幂级数形式

EGF 的特征函数是 $f_i(x)=\frac{x^i}{i!}$，那么 EGF 的形式幂级数形式即为：

$F(x)=\sum\limits_{i=0}^\infin a_i\frac{x^i}{i!}$

2.1 EGF 的一些运算的意义

为了方便计算，规定原序列的负数项为 $0$，负数的阶乘是正无穷（抛弃带有 $\frac{1}{(-1)!}$ 之类的系数的项）。

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

• 相加减

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

  相当于是 $a$ 和 $b$ 对应项相加减的序列 $c_i=a_i\pm b_i$ 的 EGF；

• 求导

  $\begin{aligned} F'(x)&=\sum\limits_{i=0}^\infin a_i\frac{ix^{i-1}}{i!}\\ &=\sum\limits_{i=0}^\infin a_i\frac{x^{i-1}}{(i-1)!}\\ &=\sum\limits_{i=0}^\infin a_{i+1}\frac{x^i}{i!}\\ \end{aligned}$

  相当于是把原序列整体左移了一位；

• 积分

  $\begin{aligned} \int F(x)dx&=\int \sum\limits_{i=0}^\infin a_i\frac{x^i}{i!}dx\\ &=C+\sum\limits_{i=0}^\infin a_i\frac{x^{i+1}}{(i+1)i!}\\ &=C+\sum\limits_{i=0}^\infin a_i\frac{x^{i+1}}{(i+1)!}\\ &=C+\sum\limits_{i=0}^\infin a_{i-1}\frac{x^i}{i!}\\ \end{aligned}$

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

• 相乘

  $\begin{aligned} F(x)G(x)&=\left(\sum\limits_{i=0}^\infin a_i\frac{x^i}{i!}\right)\left(\sum\limits_{i=0}^\infin b_i\frac{x^i}{i!}\right)\\ &=\sum\limits_{i=0}^\infin x^i\sum\limits_{j=0}^i a_jb_{i-j}\frac{1}{j!(i-j)!}\\ &=\sum\limits_{i=0}^\infin \frac{x^i}{i!}\sum\limits_{j=0}^i a_jb_{i-j}\frac{i!}{j!(i-j)!}\\ &=\sum\limits_{i=0}^\infin \frac{x^i}{i!}\sum\limits_{j=0}^i \binom{i}{j}a_jb_{i-j}\\ \end{aligned}$

  相当于是 $c_i=\sum\limits_{j=0}^i\binom{i}{j}a_jb_{i-j}$ 的 EGF，组合意义如下：

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

2.2 封闭形式

$\{1,1,1,\dots\}$ 的 EGF 是 $F(x)=\sum\limits_{i=0}^\infin\frac{x^i}{i}$，注意到这就是 $e^x$ 在 $x=0$ 处的泰勒展开，那么它的封闭形式即为 $e^x$。

同理，$\{1,p,p^2,p^3,\dots\}$ 的 EGF 的封闭形式即为 $e^{px}$。

由于 $\frac{x^i}{i!}$ 只能利用泰勒展开化为有限的封闭形式，所以往往要先将原序列转化为多个等比数列的和。

2.3 一些常见数列的 EGF 的封闭形式

$a=\{c,cp,cp^2,cp^3,\dots\}\\ a=\{1,-1,1,-1,\dots\}\\ a=\{1,0,1,0,1,\dots\}\\ a=\{0,1,0,1,0,\dots\}\\ a_i=n^{\underline{i}}\text{ 即 }a_i=n(n-1)(n-2)\dots(n-i+1)\text{，}n\text{ 是给定的常数}\\ a_0=0,a_i=(-1)^{i-1}(i-1)!\\ a_0=0,a_i=(i-1)!\\ a=\{1,0,-1,0,1,0,-1,0,\dots\}\\ a=\{0,1,0,-1,0,1,0,-1,\dots\}\\$

---

第一个：

$F(x)=c\sum\limits_{i=0}^\infin p^i\frac{x^i}{i!}=c\sum\limits_{i=0}^\infin \frac{(px)^i}{i!}=c\cdot e^{px}$

第二个：

$F(x)=\sum\limits_{i=0}^\infin (-1)^i\frac{x^i}{i!}=\sum\limits_{i=0}^\infin\frac{(-x)^i}{i!}=e^{-x}$

第三个：

$a_i=\frac{1+(-1)^i}{2}\\ F(x)=\frac{\sum\limits_{i=0}^\infin \frac{x^i}{i!}+\sum\limits_{i=0}^\infin\frac{(-x)^i}{i!}}{2}=\frac{e^x+e^{-x}}{2}$

第四个：

$a_i=\frac{1-(-1)^i}{2}\\ F(x)=\frac{\sum\limits_{i=0}^\infin \frac{x^i}{i!}-\sum\limits_{i=0}^\infin\frac{(-x)^i}{i!}}{2}=\frac{e^x-e^{-x}}{2}$

第五个：

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

第六个：

$\text{考虑 }\ln(x+1)\text{ 在 } x=0 \text{ 附近的泰勒展开：}\\ \begin{aligned} \ln(x+1)&=\sum\limits_{i=0}^{\infin}\ln^{(i)}(1)\frac{x^{i}}{i!}\\ &=\sum\limits_{i=1}^{\infin}(-1)^{i-1}(i-1)!\frac{x^{i}}{i!}\\ \end{aligned}\\ \text{所以}\\ F(x)=\sum\limits_{i=1}^{\infin}(-1)^{i-1}(i-1)!\frac{x^{i}}{i!}=\ln(x+1)$

第七个：

$\text{考虑 }-\ln(1-x)\text{ 在 } x=0 \text{ 附近的泰勒展开，换元可得：}\\ -\ln(1-x)=\sum\limits_{i=1}^{\infin}\frac{x^{i}}{i}\\ \text{所以}\\ F(x)=\sum\limits_{i=1}^{\infin}(i-1)!\frac{x^{i}}{i!}=-\ln(1-x)$

第八个：

$\text{考虑 } \cos(x) \text{ 在 } x=0 \text{ 处的泰勒展开：}\\ \begin{aligned} \cos(x)&=\sum\limits_{i=0}^{\infin} \cos^{i}(0)\frac{x^i}{i!}\\ &=\sum\limits_{i=0}^{\infin}(-1)^i\frac{x^{2i}}{(2i)!}\\ \end{aligned}\\ \text{所以}\\ F(x)=\sum\limits_{i=0}^{\infin}a_i\frac{x^{i}}{i!}=\cos(x)$

第九个：

$\text{考虑 } \sin(x) \text{ 在 } x=0 \text{ 处的泰勒展开：}\\ \begin{aligned} \sin(x)&=\sum\limits_{i=0}^{\infin} \sin^{i}(0)\frac{x^i}{i!}\\ &=\sum\limits_{i=0}^{\infin}(-1)^i\frac{x^{2i+1}}{(2i+1)!}\\ \end{aligned}\\ \text{所以}\\ F(x)=\sum\limits_{i=0}^{\infin}a_i\frac{x^{i}}{i!}=\sin(x)$

2.3.1 简单例题 POJ 3734 Blocks

有红、黄、蓝、绿四种砖块，每种都有无限块，同色的砖块是一样的。

你要选出 $n$（$1\le n\le 10^7$）块砖砌出一堵高度为 $1$ 的墙（一条墙），问满足以下条件的不同的墙的个数：

• 红色砖块只能用偶数个；
• 黄色砖块只能用偶数个；

对 $10007$ 取模。

由于要求排列个数且砖块内部互不区分但是不同色的砖块互相区分，所以应选用 EGF。

观察到求出各种砖块的 EGF 再卷起来即可。

蓝色和绿色砖块的 EGF 显然是 $\sum\limits_{i=0}^\infin \frac{x^i}{i!}=e^x$。

红色和黄色砖块的 EGF 则是 $\frac{\sum\limits_{i=0}^\infin ((-1)^i+1)\frac{x^i}{i!}}{2}=\frac{\sum\limits_{i=0}^\infin \frac{(-x)^i}{i!}+\sum\limits_{i=0}^\infin \frac{x^i}{i!}}{2}=\frac{e^{-x}+e^x}{2}$。

全部卷起来：

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

根据 $\sum\limits_{i=0}^\infin cp^i\frac{x^i}{i!}=ce^{px}$ 展开：

$\begin{aligned} ANS(x)&=\frac{1+2\sum\limits_{i=0}^\infin 2^i\frac{x^i}{i!}+\sum\limits_{i=0}^\infin 4^i\frac{x^i}{i!}}{4}\\ &=\frac{1+2\sum\limits_{i=0}^\infin 2^i\frac{x^i}{i!}+\sum\limits_{i=0}^\infin 4^i\frac{x^i}{i!}}{4}\\ &=\frac{1}{4}+\sum\limits_{i=0}^\infin 2^{i-1}4^{i-1}\frac{x^i}{i!}\\ \end{aligned}$

由于 $\frac{1}{4}$ 是常数项，属于 $x^0$，而 $n\ge 1$，所以不用管它，那么答案即为 $2^{n-1}4^{n-1}$，直接快速幂即可。

2.4 EGF 的 EXP 的组合意义

考虑一个序列 $g$ 和它的 EGF $G(x)=\sum\limits_{i=0}^\infin g_i\frac{x^i}{i!}$，这里我们默认 $g_0=0$，因为这是可以计算 $\exp$ 的前提条件。那么$[x^n]G(x)=g_n$ 的组合意义如下：

把 $n$ 个有标号小球放入一个无序集合内的方案数。

考虑 EGF 乘法的组合意义，那么 $[x^n]G^k(x)=[x^n](G(x))^k$ 的组合意义如下：

把 $n$ 个有标号小球放入 $k$ 个有标号的非空无序集合内的方案数，每个集合中放 $i$ 个小球的方案数都是 $g_i$。

那么 $[x^n]\sum\limits_{k=1}^\infin G^k(x)$ 的组合意义自然是：

把 $n$ 个有标号小球放入若干个有标号的非空无序集合内的方案数，每个集合中放 $i$ 个小球的方案数都是 $g_i$。

考虑 $[x^n]\frac{G^k(x)}{k!}$ 的组合意义，除掉的 $k!$ 相当于去掉了集合之间的顺序：

把 $n$ 个有标号小球放入 $k$ 个无标号的非空无序集合内的方案数，每个集合中放 $i$ 个小球的方案数都是 $g_i$。

那么 $[x^n]\sum\limits_{k=1}^\infin \frac{G^k(x)}{k!}$ 的组合意义自然是：

把 $n$ 个有标号小球放入若干个无标号的非空无序集合内的方案数，每个集合中放 $i$ 个小球的方案数都是 $g_i$。

注意到这就是 $\exp(G(x))$ 的定义，所以 $[x^n]\exp(G(x))$ 的组合意义就是：

把 $n$ 个有标号小球放入若干个无标号的非空无序集合内的方案数，每个集合中放 $i$ 个小球的方案数都是 $g_i$。

2.5 EGF 的应用

2.5.1 圆排列计数

圆排列：排在圆上的排列，旋转之后本质相同。

设 $f_n$ 表示 $n$ 的排列的个数，容易发现 $f_n=n!$。设 $F(x)$ 为 $f$ 的 EGF，那么有 $F(x)=\sum\limits_{i=0}^\infin i!\frac{x^i}{i!}=\sum\limits_{i=0}^\infin x^i$。

设 $g_n$ 表示 $n$ 的圆排列的个数，那么由于环旋转之后是本质相同的，所以有 $g_n=\frac{n!}{n}=(n-1)!$，特别的，$g_0=0$。设 $G(x)$ 为 $g$ 的 EGF，那么有 $G(x)=\sum\limits_{i=1}^\infin (i-1)!\frac{x^i}{i!}=\sum\limits_{i=1}^\infin\frac{x^i}{i}$。

观察到有 $F(x)=\frac{1}{1-x}$，$G(x)=-\ln(1-x)=\ln(\frac{1}{1-x})$，所以有 $G(x)=\ln(F(x))$。

组合意义上的解释是，考虑一个长度为 $n$ 排列 $p$，从 $i$ 向 $p_i$ 连一条有向边，那么由于每个点的入度和出度都是 $1$，所以最后一定会形成若干个环，并且环的方案和排列组成双射。由于大小为 $x$ 的环的方案数都是 $g_x$，所以有 $F(x)=\exp(G(x))$。

2.5.2 错排列计数

错排列：满足 $p_i\not= i$ 的排列。

设 $f_n$ 表示 $n$ 的错排列的个数，$g_n$ 表示 $n$ 的圆排列的个数，$F(x)$、$G(x)$ 分别为 $f$、$g$ 的 EGF，根据之前的推导有 $G(x)=-\ln(1-x)$。

那么观察到错排列就相当于是变成若干个环后不存在大小为 $1$ 的环，那么设 $G_*(x)=G(x)-x$ 即让大小为 $1$ 的环的方案数为 $0$，显然有 $G_*(x)=-\ln(1-x)-x$，$F(x)=\exp(G_*(x))=\exp(-\ln(1-x)-x)$。

2.5.3 简单例题：不动点

求满足以下条件的 $n$ 个点有向图的个数：

• 每个点出度为 $1$；
• 从每个点出发，走 $k$ 步后到达的点和走 $k-1$ 步后到达的点一样；

$1\le n\le 2\times 10^6,1\le k\le 3$。

不难发现满足条件的图是一个基环树森林，并且森林中的基环树的根都是一个自环，所以实际上图是一个森林。且森林中的树的深度小于等于 $k$。

那么设 $f_{n,m}$ 表示 $n$ 个点的深度不超过 $m$ 的有根树的个数，显然有 $f_{1,1}=1$，设 $F_m(x)=\sum\limits_{i=0}^\infin f_{i,m}\frac{x^i}{i!}$ 也就是 $f$ 关于 $n$ 的 EGF。那么由于根的不同子树不用考虑顺序，所以有 $F_m(x)=x\times \exp(F_{m-1}(x))$ 其中乘 $x$ 是因为要算上根的 EGF $\frac{x^1}{1!}$。

接下来就要把这些有根树组合起来，答案即为 $[x^n]\exp(F_k(x))$。

经典例题

CF891E Lust

有个结论，$ans$ 每次增加的量等于 $\prod a_i$ 减少的量，那么设 $a_i$ 减少了 $b_i$，那么 $ans$ 即为 $\prod a_i-\prod (a_i-b_i)$。

那么设 $a_i$ 的 EGF 为 $F_i(x)=\sum\limits_{j=0}^\infin (a_i-j)\frac{x^j}{j!}$，则答案即为 $\prod a_i-\frac{[x^k]\prod F_i(x)}{n^k}$。

分母可以 $O(n)$ 算，所以问题的难点在于 $[x^k]\prod F_i(x)$，注意到有：

$\begin{aligned} F_i(x)&=\sum\limits_{j=0}^\infin (a_i-j)\frac{x^j}{j!}\\ &=\sum\limits_{j=0}^\infin a_i\frac{x^j}{j!}-\sum\limits_{j=0}^\infin j\frac{x^j}{j!}\\ &=a_i\sum\limits_{j=0}^\infin\frac{x^j}{j!}-x\sum\limits_{j=1}^\infin \frac{x^{j-1}}{(j-1)!}\\ &=(a_i-x)e^x \end{aligned}$

那么有：

$[x^k]\prod F_i(x)=[x^k]\left(e^{nx}\prod (a_i-x)\right)$

由于 $n\le 5000$，所以 $\prod (a_i-x)$ 的每一项系数 $c_0+c_1x^1+\dots$ 可以 $O(n^2)$ 算出来，然后根据 $[x^k]e^{nx}=n^k$，可以直接 $O(n^2)$ 暴力卷积算出 $[x^k]\prod F_i(x)$。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=5005,p=1000000007;

int n,k,a[S];
int c[S],tmp[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline int C(int n,int m)
{
	if(n<m||n<0||m<0) return 0;
	int re=1,div=1;
	for(int i=n;i>=n-m+1;i--) re=1ll*re*i%p;
	for(int i=1;i<=m;i++) div=1ll*div*i%p;
	return 1ll*re*qpow(div,p-2)%p;
}

int main()
{
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	c[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=n;j++) tmp[j]=c[j];
		for(int j=0;j<=n;j++) c[j]=1ll*c[j]*a[i]%p;
		for(int j=0;j<=n-1;j++) c[j+1]=(c[j+1]-tmp[j]+p)%p;
	}
	for(int i=0,fra=1;i<=n;i++) fra=1ll*fra*max(i,1)%p,c[i]=1ll*fra*c[i]%p;
	int prod=0;
	for(int i=k;i>=k-n&&i>=0;i--) prod=(prod+1ll*qpow(n,i)*c[k-i]%p*C(k,k-i)%p)%p;
	int mul=1;
	for(int i=1;i<=n;i++) mul=1ll*mul*a[i]%p;
	int ans=(mul-1ll*prod*qpow(qpow(n,k),p-2)%p+p)%p;
	printf("%d\n",ans);
	return 0;
}