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

起始：求联通子图个数

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

下可能略写$F(x)$为$F$

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

$\begin{aligned} F\times G=\sum_{S\ne \empty}\sum_{T\ne \empty,S\cap T=\empty} [x^S]F\cdot [x^T]G\cdot x^{S\cup T} \end{aligned}$

显然满足关系式$\begin{aligned} G=\sum_{i\ge 1} \frac{F^i} {i!}=e^{F}-1\end{aligned}$

$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$

$\begin{aligned}G'_i=F'_i+\sum_{j=1}G_jF'_{i-j}\end{aligned}$

可能在子图计数题中出现

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
42
43


#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);
}