集合幂级数的 $\\ln,\\exp$

Posted on Edited on In

集合幂级数的 \(\ln,\exp\)

起始：求联通子图个数。

令 \(F(x)\) 为联通的生成子图个数的形式幂级数，可以简单求出 \(G(x)\) 为生成子图个数的形式幂级数。

下可能略写 \(F(x)\) 为 \(F\)。

不连通的子图可以通过联通子图做集合并运算得到，即构造卷积：

\[ F\times G=\sum_{S\ne \emptyset}\sum_{T\ne \emptyset,S\cap T=\emptyset} [x^S]F\cdot [x^T]G\cdot x^{S\cup T} \]

显然满足关系式 \(\displaystyle G=\sum_{i\ge 1} \frac{F^i}{i!}=e^{F}-1\)，\(F=\ln (G+1)\)

计算集合幂级数 \(\ln\) 的方法似乎非常抽象：

  1. 类似子集卷积，把所有项按照占位数（集合包含元素个数）分开，记录在第二维。

  2. 求出 \(\text{FMT}\)。

  3. 对于集合幂级数每一位（现在是一个形式幂级数）求出其 \(\ln\) 的前 \(n\) 项。

  4. 求出 \(\text{IFMT}\)

求出形式幂级数 \(\ln\) 的 \(n^2\) 方法是。

\(F=\ln (G+1)\)，

\(F'=\frac{G'}{G+1}\)，

\(F'(G+1)=G'\)，

\(\begin{aligned}F'_i=G'_i-\sum_{j=1}G_jF'_{i-j}\end{aligned}\)。

类似的，可以计算集合幂级数的 \(\exp\)，即由上面的 \(F\) 求 \(G\)：\(\displaystyle G'_i=F'_i+\sum_{j=1}G_jF'_{i-j}\)。

可能在子图计数题中出现：

LOJ6729

LOJ6719

LOJ6730

下面是代码实现上的参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a;i<=b;++i)

int I[N];// 模逆元
void FMT(int F[M][N],int f){
	for(int i=1;i<m;i<<=1) for(int l=0;l<m;l+=i*2) 
		for(int j=l;j<l+i;++j) if(f==1) rep(d,1,n) F[j+i][d]+=F[j][d],Mod1(F[j+i][d]);
		else rep(d,1,n) F[j+i][d]-=F[j][d],Mod2(F[j+i][d]);
}

void Ln(int *a){
	static int b[N];
	rep(i,0,n-1) {
		int t=0;
		rep(j,0,i-1) t=(t+1ll*b[j]*a[i-j])%P;
		b[i]=(1ll*a[i+1]*(i+1)-t+P)%P;
	}
	rep(i,1,n) a[i]=1ll*b[i-1]*I[i]%P;
}
void Exp(int *a){
	static int b[N];
	rep(i,0,n-1) b[i]=1ll*a[i+1]*(i+1)%P;
	rep(i,0,n-1) {
		int t=b[i];
		rep(j,1,i) t=(t+1ll*a[j]*b[i-j])%P;
		a[i+1]=1ll*t*I[i+1]%P;
	}
}

void Ln(int F[M][N]) {
    FMT(F,1);
	rep(i,1,m-1) Ln(F[i]);
	FMT(F,-1);
}
void Exp(int F[M][N]) {
    FMT(F,1);
	rep(i,1,m-1) Exp(F[i]);
	FMT(F,-1);
}