Part 2 指数型生成函数 EGF(Exponential Generating Function)
指数型生成函数的特征函数是 fi(x)=i!xi。
2.0 形式幂级数形式
EGF 的特征函数是 fi(x)=i!xi,那么 EGF 的形式幂级数形式即为:
F(x)=i=0∑∞aii!xi
2.1 EGF 的一些运算的意义
为了方便计算,规定原序列的负数项为 0,负数的阶乘是正无穷(抛弃带有 (−1)!1 之类的系数的项)。
假设有两个序列 a,b 和它们的 EGF F(x),G(x),那么:
-
相加减
H(x)=F(x)±G(x)=i=0∑∞(ai±bi)i!xi
相当于是 a 和 b 对应项相加减的序列 ci=ai±bi 的 EGF;
-
求导
F′(x)=i=0∑∞aii!ixi−1=i=0∑∞ai(i−1)!xi−1=i=0∑∞ai+1i!xi
相当于是把原序列整体左移了一位;
-
积分
∫F(x)dx=∫i=0∑∞aii!xidx=C+i=0∑∞ai(i+1)i!xi+1=C+i=0∑∞ai(i+1)!xi+1=C+i=0∑∞ai−1i!xi
相当于是把原序列整体右移了一位;
-
相乘
F(x)G(x)=(i=0∑∞aii!xi)(i=0∑∞bii!xi)=i=0∑∞xij=0∑iajbi−jj!(i−j)!1=i=0∑∞i!xij=0∑iajbi−jj!(i−j)!i!=i=0∑∞i!xij=0∑i(ji)ajbi−j
相当于是 ci=j=0∑i(ji)ajbi−j 的 EGF,组合意义如下:
ci 表示把 i 个有标号小球放入 A 和 B 两个有标号无序集合中,其中 A 集合中放 i 个球的方案数是 ai,B 集合中放 i 个球的方案数是 bi。
2.2 封闭形式
{1,1,1,…} 的 EGF 是 F(x)=i=0∑∞ixi,注意到这就是 ex 在 x=0 处的泰勒展开,那么它的封闭形式即为 ex。
同理,{1,p,p2,p3,…} 的 EGF 的封闭形式即为 epx。
由于 i!xi 只能利用泰勒展开化为有限的封闭形式,所以往往要先将原序列转化为多个等比数列的和。
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(n−1)(n−2)…(n−i+1),n 是给定的常数a0=0,ai=(−1)i−1(i−1)!a0=0,ai=(i−1)!a={1,0,−1,0,1,0,−1,0,…}a={0,1,0,−1,0,1,0,−1,…}
第一个:
F(x)=ci=0∑∞pii!xi=ci=0∑∞i!(px)i=c⋅epx
第二个:
F(x)=i=0∑∞(−1)ii!xi=i=0∑∞i!(−x)i=e−x
第三个:
ai=21+(−1)iF(x)=2i=0∑∞i!xi+i=0∑∞i!(−x)i=2ex+e−x
第四个:
ai=21−(−1)iF(x)=2i=0∑∞i!xi−i=0∑∞i!(−x)i=2ex−e−x
第五个:
F(x)=i=0∑nnii!xi=i=0∑n(in)xi=(x+1)n
第六个:
考虑 ln(x+1) 在 x=0 附近的泰勒展开:ln(x+1)=i=0∑∞ln(i)(1)i!xi=i=1∑∞(−1)i−1(i−1)!i!xi所以F(x)=i=1∑∞(−1)i−1(i−1)!i!xi=ln(x+1)
第七个:
考虑 −ln(1−x) 在 x=0 附近的泰勒展开,换元可得:−ln(1−x)=i=1∑∞ixi所以F(x)=i=1∑∞(i−1)!i!xi=−ln(1−x)
第八个:
考虑 cos(x) 在 x=0 处的泰勒展开:cos(x)=i=0∑∞cosi(0)i!xi=i=0∑∞(−1)i(2i)!x2i所以F(x)=i=0∑∞aii!xi=cos(x)
第九个:
考虑 sin(x) 在 x=0 处的泰勒展开:sin(x)=i=0∑∞sini(0)i!xi=i=0∑∞(−1)i(2i+1)!x2i+1所以F(x)=i=0∑∞aii!xi=sin(x)
有红、黄、蓝、绿四种砖块,每种都有无限块,同色的砖块是一样的。
你要选出 n(1≤n≤107)块砖砌出一堵高度为 1 的墙(一条墙),问满足以下条件的不同的墙的个数:
对 10007 取模。
由于要求排列个数且砖块内部互不区分但是不同色的砖块互相区分,所以应选用 EGF。
观察到求出各种砖块的 EGF 再卷起来即可。
蓝色和绿色砖块的 EGF 显然是 i=0∑∞i!xi=ex。
红色和黄色砖块的 EGF 则是 2i=0∑∞((−1)i+1)i!xi=2i=0∑∞i!(−x)i+i=0∑∞i!xi=2e−x+ex。
全部卷起来:
ANS(x)=ex×ex×2e−x+ex×2e−x+ex=e2x×4e−2x+2+e2x=41+2e2x+e4x
根据 i=0∑∞cpii!xi=cepx 展开:
ANS(x)=41+2i=0∑∞2ii!xi+i=0∑∞4ii!xi=41+2i=0∑∞2ii!xi+i=0∑∞4ii!xi=41+i=0∑∞2i−14i−1i!xi
由于 41 是常数项,属于 x0,而 n≥1,所以不用管它,那么答案即为 2n−14n−1,直接快速幂即可。
2.4 EGF 的 EXP 的组合意义
考虑一个序列 g 和它的 EGF G(x)=i=0∑∞gii!xi,这里我们默认 g0=0,因为这是可以计算 exp 的前提条件。那么[xn]G(x)=gn 的组合意义如下:
把 n 个有标号小球放入一个无序集合内的方案数。
考虑 EGF 乘法的组合意义,那么 [xn]Gk(x)=[xn](G(x))k 的组合意义如下:
把 n 个有标号小球放入 k 个有标号的非空无序集合内的方案数,每个集合中放 i 个小球的方案数都是 gi。
那么 [xn]k=1∑∞Gk(x) 的组合意义自然是:
把 n 个有标号小球放入若干个有标号的非空无序集合内的方案数,每个集合中放 i 个小球的方案数都是 gi。
考虑 [xn]k!Gk(x) 的组合意义,除掉的 k! 相当于去掉了集合之间的顺序:
把 n 个有标号小球放入 k 个无标号的非空无序集合内的方案数,每个集合中放 i 个小球的方案数都是 gi。
那么 [xn]k=1∑∞k!Gk(x) 的组合意义自然是:
把 n 个有标号小球放入若干个无标号的非空无序集合内的方案数,每个集合中放 i 个小球的方案数都是 gi。
注意到这就是 exp(G(x)) 的定义,所以 [xn]exp(G(x)) 的组合意义就是:
把 n 个有标号小球放入若干个无标号的非空无序集合内的方案数,每个集合中放 i 个小球的方案数都是 gi。
2.5 EGF 的应用
2.5.1 圆排列计数
圆排列:排在圆上的排列,旋转之后本质相同。
设 fn 表示 n 的排列的个数,容易发现 fn=n!。设 F(x) 为 f 的 EGF,那么有 F(x)=i=0∑∞i!i!xi=i=0∑∞xi。
设 gn 表示 n 的圆排列的个数,那么由于环旋转之后是本质相同的,所以有 gn=nn!=(n−1)!,特别的,g0=0。设 G(x) 为 g 的 EGF,那么有 G(x)=i=1∑∞(i−1)!i!xi=i=1∑∞ixi。
观察到有 F(x)=1−x1,G(x)=−ln(1−x)=ln(1−x1),所以有 G(x)=ln(F(x))。
组合意义上的解释是,考虑一个长度为 n 排列 p,从 i 向 pi 连一条有向边,那么由于每个点的入度和出度都是 1,所以最后一定会形成若干个环,并且环的方案和排列组成双射。由于大小为 x 的环的方案数都是 gx,所以有 F(x)=exp(G(x))。
2.5.2 错排列计数
错排列:满足 pi=i 的排列。
设 fn 表示 n 的错排列的个数,gn 表示 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≤n≤2×106,1≤k≤3。
不难发现满足条件的图是一个基环树森林,并且森林中的基环树的根都是一个自环,所以实际上图是一个森林。且森林中的树的深度小于等于 k。
那么设 fn,m 表示 n 个点的深度不超过 m 的有根树的个数,显然有 f1,1=1,设 Fm(x)=i=0∑∞fi,mi!xi 也就是 f 关于 n 的 EGF。那么由于根的不同子树不用考虑顺序,所以有 Fm(x)=x×exp(Fm−1(x)) 其中乘 x 是因为要算上根的 EGF 1!x1。
接下来就要把这些有根树组合起来,答案即为 [xn]exp(Fk(x))。
经典例题
有个结论,ans 每次增加的量等于 ∏ai 减少的量,那么设 ai 减少了 bi,那么 ans 即为 ∏ai−∏(ai−bi)。
那么设 ai 的 EGF 为 Fi(x)=j=0∑∞(ai−j)j!xj,则答案即为 ∏ai−nk[xk]∏Fi(x)。
分母可以 O(n) 算,所以问题的难点在于 [xk]∏Fi(x),注意到有:
Fi(x)=j=0∑∞(ai−j)j!xj=j=0∑∞aij!xj−j=0∑∞jj!xj=aij=0∑∞j!xj−xj=1∑∞(j−1)!xj−1=(ai−x)ex
那么有:
[xk]∏Fi(x)=[xk](enx∏(ai−x))
由于 n≤5000,所以 ∏(ai−x) 的每一项系数 c0+c1x1+… 可以 O(n2) 算出来,然后根据 [xk]enx=nk,可以直接 O(n2) 暴力卷积算出 [xk]∏Fi(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;
}