指数型生成函数入门

Part 2 指数型生成函数 EGF(E\mathtt{E}xponential G\mathtt{G}enerating F\mathtt{F}unction)

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

2.0 形式幂级数形式

EGF 的特征函数是 fi(x)=xii!f_i(x)=\frac{x^i}{i!},那么 EGF 的形式幂级数形式即为:

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

2.1 EGF 的一些运算的意义

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

假设有两个序列 aabb 和它们的 EGF F(x)F(x)G(x)G(x),那么:

  • 相加减

    H(x)=F(x)±G(x)=i=0(ai±bi)xii!\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}

    相当于是 aabb 对应项相加减的序列 ci=ai±bic_i=a_i\pm b_i 的 EGF;

  • 求导

    F(x)=i=0aiixi1i!=i=0aixi1(i1)!=i=0ai+1xii!\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}

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

  • 积分

    F(x)dx=i=0aixii!dx=C+i=0aixi+1(i+1)i!=C+i=0aixi+1(i+1)!=C+i=0ai1xii!\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}

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

  • 相乘

    F(x)G(x)=(i=0aixii!)(i=0bixii!)=i=0xij=0iajbij1j!(ij)!=i=0xii!j=0iajbiji!j!(ij)!=i=0xii!j=0i(ij)ajbij\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}

    相当于是 ci=j=0i(ij)ajbijc_i=\sum\limits_{j=0}^i\binom{i}{j}a_jb_{i-j} 的 EGF,组合意义如下:

    cic_i 表示把 ii有标号小球放入 AABB 两个有标号无序集合中,其中 AA 集合中放 ii 个球的方案数是 aia_iBB 集合中放 ii 个球的方案数是 bib_i

2.2 封闭形式

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

同理,{1,p,p2,p3,}\{1,p,p^2,p^3,\dots\} 的 EGF 的封闭形式即为 epxe^{px}

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

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

a={c,cp,cp2,cp3,}a={1,1,1,1,}a={1,0,1,0,1,}a={0,1,0,1,0,}ai=ni 即 ai=n(n1)(n2)(ni+1)n 是给定的常数a0=0,ai=(1)i1(i1)!a0=0,ai=(i1)!a={1,0,1,0,1,0,1,0,}a={0,1,0,1,0,1,0,1,}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)=ci=0pixii!=ci=0(px)ii!=cepxF(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)=i=0(1)ixii!=i=0(x)ii!=exF(x)=\sum\limits_{i=0}^\infin (-1)^i\frac{x^i}{i!}=\sum\limits_{i=0}^\infin\frac{(-x)^i}{i!}=e^{-x}

第三个:

ai=1+(1)i2F(x)=i=0xii!+i=0(x)ii!2=ex+ex2a_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}

第四个:

ai=1(1)i2F(x)=i=0xii!i=0(x)ii!2=exex2a_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}

第五个:

F(x)=i=0nnixii!=i=0n(ni)xi=(x+1)n\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}

第六个:

考虑 ln(x+1) 在 x=0 附近的泰勒展开:ln(x+1)=i=0ln(i)(1)xii!=i=1(1)i1(i1)!xii!所以F(x)=i=1(1)i1(i1)!xii!=ln(x+1)\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)

第七个:

考虑 ln(1x) 在 x=0 附近的泰勒展开,换元可得:ln(1x)=i=1xii所以F(x)=i=1(i1)!xii!=ln(1x)\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)

第八个:

考虑 cos(x) 在 x=0 处的泰勒展开:cos(x)=i=0cosi(0)xii!=i=0(1)ix2i(2i)!所以F(x)=i=0aixii!=cos(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)

第九个:

考虑 sin(x) 在 x=0 处的泰勒展开:sin(x)=i=0sini(0)xii!=i=0(1)ix2i+1(2i+1)!所以F(x)=i=0aixii!=sin(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

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

你要选出 nn1n1071\le n\le 10^7)块砖砌出一堵高度为 11 的墙(一条墙),问满足以下条件的不同的墙的个数:

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

1000710007 取模。

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

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

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

红色和黄色砖块的 EGF 则是 i=0((1)i+1)xii!2=i=0(x)ii!+i=0xii!2=ex+ex2\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}

全部卷起来:

ANS(x)=ex×ex×ex+ex2×ex+ex2=e2x×e2x+2+e2x4=1+2e2x+e4x4\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}

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

ANS(x)=1+2i=02ixii!+i=04ixii!4=1+2i=02ixii!+i=04ixii!4=14+i=02i14i1xii!\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}

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

2.4 EGF 的 EXP 的组合意义

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

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

考虑 EGF 乘法的组合意义,那么 [xn]Gk(x)=[xn](G(x))k[x^n]G^k(x)=[x^n](G(x))^k 的组合意义如下:

nn有标号小球放入 kk有标号非空无序集合内的方案数,每个集合中放 ii 个小球的方案数都是 gig_i

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

nn有标号小球放入若干有标号非空无序集合内的方案数,每个集合中放 ii 个小球的方案数都是 gig_i

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

nn有标号小球放入 kk无标号非空无序集合内的方案数,每个集合中放 ii 个小球的方案数都是 gig_i

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

nn有标号小球放入若干无标号非空无序集合内的方案数,每个集合中放 ii 个小球的方案数都是 gig_i

注意到这就是 exp(G(x))\exp(G(x)) 的定义,所以 [xn]exp(G(x))[x^n]\exp(G(x)) 的组合意义就是:

nn有标号小球放入若干无标号非空无序集合内的方案数,每个集合中放 ii 个小球的方案数都是 gig_i

2.5 EGF 的应用

2.5.1 圆排列计数

圆排列:排在圆上的排列,旋转之后本质相同。

fnf_n 表示 nn 的排列的个数,容易发现 fn=n!f_n=n!。设 F(x)F(x)ff 的 EGF,那么有 F(x)=i=0i!xii!=i=0xiF(x)=\sum\limits_{i=0}^\infin i!\frac{x^i}{i!}=\sum\limits_{i=0}^\infin x^i

gng_n 表示 nn 的圆排列的个数,那么由于环旋转之后是本质相同的,所以有 gn=n!n=(n1)!g_n=\frac{n!}{n}=(n-1)!,特别的,g0=0g_0=0。设 G(x)G(x)gg 的 EGF,那么有 G(x)=i=1(i1)!xii!=i=1xiiG(x)=\sum\limits_{i=1}^\infin (i-1)!\frac{x^i}{i!}=\sum\limits_{i=1}^\infin\frac{x^i}{i}

观察到有 F(x)=11xF(x)=\frac{1}{1-x}G(x)=ln(1x)=ln(11x)G(x)=-\ln(1-x)=\ln(\frac{1}{1-x}),所以有 G(x)=ln(F(x))G(x)=\ln(F(x))

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

2.5.2 错排列计数

错排列:满足 pi=ip_i\not= i 的排列。

fnf_n 表示 nn 的错排列的个数,gng_n 表示 nn 的圆排列的个数,F(x)F(x)G(x)G(x) 分别为 ffgg 的 EGF,根据之前的推导有 G(x)=ln(1x)G(x)=-\ln(1-x)

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

2.5.3 简单例题:不动点

求满足以下条件的 nn 个点有向图的个数:

  • 每个点出度为 11
  • 从每个点出发,走 kk 步后到达的点和走 k1k-1 步后到达的点一样;

1n2×106,1k31\le n\le 2\times 10^6,1\le k\le 3

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

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

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

经典例题

CF891E Lust

有个结论,ansans 每次增加的量等于 ai\prod a_i 减少的量,那么设 aia_i 减少了 bib_i,那么 ansans 即为 ai(aibi)\prod a_i-\prod (a_i-b_i)

那么设 aia_i 的 EGF 为 Fi(x)=j=0(aij)xjj!F_i(x)=\sum\limits_{j=0}^\infin (a_i-j)\frac{x^j}{j!},则答案即为 ai[xk]Fi(x)nk\prod a_i-\frac{[x^k]\prod F_i(x)}{n^k}

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

Fi(x)=j=0(aij)xjj!=j=0aixjj!j=0jxjj!=aij=0xjj!xj=1xj1(j1)!=(aix)ex\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}

那么有:

[xk]Fi(x)=[xk](enx(aix))[x^k]\prod F_i(x)=[x^k]\left(e^{nx}\prod (a_i-x)\right)

由于 n5000n\le 5000,所以 (aix)\prod (a_i-x) 的每一项系数 c0+c1x1+c_0+c_1x^1+\dots 可以 O(n2)O(n^2) 算出来,然后根据 [xk]enx=nk[x^k]e^{nx}=n^k,可以直接 O(n2)O(n^2) 暴力卷积算出 [xk]Fi(x)[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;
}