集合幂级数的ln和exp运算及组合意义

集合幂级数的ln和exp运算及组合意义

子集卷积

设(f,g,h)为集合幂级数
定义(h)为(f)和(g)的子集卷积

[h_S=sum_{L}sum_{R} f_L g_R [L cap R=emptyset][L cup R=S] ]

注意到([L cap R=emptyset][L cup R=S]=[|L|+|R|=|S|][L cup R=S])

我们定义集合占位幂级数 (F_{i,S}),(F_{|S|,S}=f_S),其余情况为0

那么上面的式子就可以简化为

[H_{k,S}=sum_isum_jsum_Lsum_R[i+j=k][L cup R=S]F_{i,L} G_{j,R} ]

容易发现,第一维是一个普通卷积,而第二维是集合幂级数的or卷积. 而集合占位幂级数可以看成一个二元生成函数,每一维之间是独立的,只需要分开即可.(可以考虑多项式的乘法如((xy+x^2y)(2x^2y+3y^2)),感性理解即可)

那么我们处理这个卷积时,只需要对每一行(f_i)做FMT,然后对于每一列,暴力做普通卷积,再把每一行IFMT回来即可。因为有(n)行(2^n)列,所以复杂度(O(n^22^n))

集合幂级数exp

我们考虑EGF的组合意义,EGF的exp表示把元素组合成集合的方案数。不妨定义(F_{|S|,S}=frac{f_S}{|S|!}). 那么每一列就是一个EGF. 我们先定义占位集合幂级数的exp为(exp F -1=sum_{igeq 1}frac{F^i}{i!}),其中(F)的乘法定义为子集卷积. 由于占位集合幂级数中中两维的独立性,这等价于对第一维做普通卷积意义下的exp,对第二维做or卷积.

实现时,类似子集卷积,先对行FMT,再列exp,再IFMT回来即可. 对列做exp，当然可以用多项式全家桶做到(O(nlog n)),但常数爆炸。因为(n)很小,考虑如何(O(n^2))做exp.

设(G=exp F -1)

两边求导得(G'=F' exp F=F'G)

写成系数形式(ng_n=sum_{i=0}^{n-1}if_ig_{n-i}),即

[g_n=frac{1}{n} sum_{i=0}^{n-1}if_ig_{n-i}]

集合幂级数的exp好像十分抽象,我们现在探讨它的组合意义. 设(g_n)为真实的方案数(没有除掉EGF中的n!)

[frac{g_n}{n!}=sum_{i=0}^{n-1} frac{i}{n} frac{f_i}{i!} frac{g_{n-i}}{(n-i)!} ]

[g_n=sum_{i=0}^{n-1} frac{i}{n}inom{n}{i}f_i g_{n-i}=sum_{i=0}^{n-1} inom{n-1}{i-1}f_i g_{n-i} ]

组合解释如下: 枚举(n)所在的集合的大小(i),那么该集合内部的方案数为(f_i).从的(n-1)个数中选(i-1)个数与(n)放到同一集合。剩下的(n-i)个数随便放,方案数(g_{n-i}). 那么exp的意义就是选取若干个不相交的集合组合成S的方案数。

void exp(int *f,int *g,int n){
	static int F[maxlogn+5][maxn+5],G[maxlogn+5][maxn+5];
	for(int i=0;i<(1<<n);i++) for(int j=0;j<=n;j++) F[j][i]=G[j][i]=0;
	for(int i=0;i<(1<<n);i++) F[cnt[i]][i]=f[i];
	for(int i=0;i<=n;i++) FMT(F[i],n,1);
	G[0][0]=1;
	FMT(G[0],n,1);
	for(int s=0;s<(1<<n);s++){
		for(int i=1;i<=n;i++){
			for(int j=0;j<=i-1;j++) G[i][s]=addm(G[i][s],1ll*F[j][s]*j*G[i-j][s]%mod);
			G[i][s]=1ll*G[i][s]*invi[i]%mod;
		}
	} 
	for(int i=0;i<=n;i++) FMT(G[i],n,-1);
	for(int i=0;i<(1<<n);i++) g[i]=G[cnt[i]][i];
}

定义(G)的生成子图为包含(G)的所有顶点的子图。给出一个图G,求G的连通生成子图数量

集合幂级数ln

之前我们定义了(e^G-1=F).同理,我们定义(G=ln(F+1))

同样,对第一维做普通卷积意义下的ln,对第二维做or卷积.考虑如何(O(n^2))ln.

我们只需要把exp的式子反过来就好了

[g_n=frac{1}{n} sum_{i=0}^{n-1}if_ig_{n-i}]

[f_n=g_n-frac{1}{n}sum_{i=1}^{n-1}if_ig_{n-i} ]

再把字母换一下就得到了

[g_n=f_n-frac{1}{n}sum_{i=1}^{n-1}ig_if_{n-i} ]

由exp的组合意义可知,ln的组合意义为将S拆分成若干个不相交集合的方案数

void ln(int *f,int *g,int n){
	static int F[maxlogn+5][maxn+5],G[maxlogn+5][maxn+5];
	for(int i=0;i<(1<<n);i++) for(int j=0;j<=n;j++) F[j][i]=G[j][i]=0;
	for(int i=0;i<(1<<n);i++) F[cnt[i]][i]=f[i];
	for(int i=0;i<=n;i++) FMT(F[i],n,1);
	G[0][0]=1;
	FMT(G[0],n,1);
	for(int s=0;s<(1<<n);s++){
		for(int i=1;i<=n;i++){
			for(int j=0;j<=i-1;j++) G[i][s]=addm(G[i][s],1ll*F[i-j][s]*G[j][s]%mod*j%mod);
			G[i][s]=decm(F[i][s],1ll*G[i][s]*invi[i]%mod)%mod;
		}
	} 
	for(int i=0;i<=n;i++) FMT(G[i],n,-1);
	for(int i=0;i<(1<<n);i++) g[i]=G[cnt[i]][i];
}

k-exp

我们在ln和exp的定义中,都没有限制拆分成集合的个数,如(sum_{i geq 1}frac{F^i}{i!}),i的取值是1到n. 如果限制拆分的个数之多为k,我们就得到了k-exp

即(G=sum_{i=1}^k frac{F^i}{i!})

同样两边求导,有(G'=F'(G-frac{F^k}{k!})),因为对右边求导后,每一项都变成了前一项,只有第k项消失了

同样考虑每一列怎么做.对(F^k)做多项式快速幂(即先ln,乘k再exp),设得到的结果为(h).那么上式就可以写成

(ng_n=sum_{i=0}^{n-1}(n-i)f_{n-i}(g_i-h_i))

就可以在(O(n^2))的时间内求解

模板题LOJ 154
代码