浅谈集合幂级数

叠甲：读者很菜。

集合幂级数是一个很厉害的东西。

我们对于是有限集的全集 U=1,2,…n，我们利用占位符 xS 来表示一个序列 f，其中对于 S⊆U 的值为 fS。

一般记为 F=∑S⊆UfSxS。

对于占位符的运算，有 xS×xT={xS∪T,S∩T=∅0,S∩T≠∅。

我们考虑最基本的卷积运算：

已知 F=∑S⊆UfSxS 和 G=∑S⊆UgSxS 如何求解 H=F×G。

【模板】子集卷积

如果运算有 xS×xT=xS∪T，这就是普通的或卷积，可以 O(n2n) 实现。

但是并不是，只有在 S∩T=∅ 的时候才会做贡献，考虑在或卷积的基础上增加一些修改，使得其满足这个条件。

我们知道 |S|+|T|≥|S∪T|，取等的时候当且仅当 S∩T=∅，这就完美的满足了我们的条件。

所以我们添加一个占位符 y。xS 变成 xSy|S|，则 (xSy|S|)×(xTy|T|)=xS∪Ty|S|+|T|，这样就完美的符合了我们的要求。

具体的实现，就是增加以为，这一位的运算是朴素的多项式卷积。

多项式卷积使用暴力算法可以做到 O(n22n)，可以用 FFT/NTT 优化到 O(nlog⁡n2n)，但是常数太大，完全没有必要。

void mul(int *F,int *G,int *H)
{
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(int i=0;i<st;i++) f[pct[i]][i]=F[i],g[pct[i]][i]=G[i];
	for(int i=0;i<=n;i++) FMT(f[i]),FMT(g[i]);
	for(int S=0;S<st;S++)
	{
		for(int i=n;~i;i--)
		{
			g[i][S]=1ll*g[i][S]*f[0][S]%Mod;
			for(int j=1;j<=i;j++)
				add(g[i][S],1ll*f[j][S]*g[i-j][S]%Mod);
		}
	}
	for(int i=0;i<=n;i++) iFMT(g[i]);
	for(int i=0;i<st;i++) H[i]=g[pct[i]][i];
}

子集卷积 exp

我们来考虑上面卷积运算的一些组合意义：

如果我们想要查询有 f 中两个不交集合构成集合对应的方案数，其为 F×F2=F22。

依此类推选择 k 个构成的不交集合就是 Fkk!（除 k! 的原因是选择这些集合的相对顺序是无关的）。

我们考虑选择若干个不交集合（考虑可以不选），有 G=x∅+∑k=1Fkk!。

发现 ∑k=1Fkk!，这个东西就是 exp⁡F−1。也就是说 G=exp⁡F。

因此，还是在 x 维上做或卷积，在 y 维上我们做多项式 exp，我们就可以通过 F 来生成 G=exp⁡F 了。

G=exp⁡F，所以 G′=(exp⁡F)′。

所以 G′=exp⁡F×F′⇒G′=G×F。

∑iigiyi−1=(∑igiyi)×(∑iifiyi−1)。

所以 ngn=∑i=1nfi×gn−i。这样单次 exp 可以做到 O(n2)，所以整体就可以做到 O(n22n)。

而子集卷积 exp 的组合意义就是：选择若干个不交集合组合在一起的所有方案。

void exp(int *F,int *G)
{
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(int i=1;i<st;i++) f[pct[i]][i]=F[i];
	for(int i=0;i<=n;i++) FMT(f[i]);
	for(int S=0,tmp;S<st;S++)
	{
		g[0][S]=1;
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=i;j++)
				add(g[i][S],1ll*j*f[j][S]%Mod*g[i-j][S]%Mod);
			g[i][S]=1ll*g[i][S]*inv[i]%Mod;
		}
	}
	for(int i=0;i<=n;i++) iFMT(g[i]);
	for(int i=0;i<st;i++) G[i]=g[pct[i]][i];
}

子集卷积 ln

有 exp 就自然会有 ln。

既然 exp 是组合，那么 ln 就是拆分。

exp 是已知 f 得到 g，ln 就是通过 g 得到 f。

由于 ngn=∑i=1nfi×gn−i，所以 ngn=nfng0+∑i=1n−1fi×gn−i（g0=1）。

fn=gn−1n∑i=1n−1fi×gn−i。

这样实现的复杂度也是 O(n22n) 的。

组合意义就是：拆分成若干个不交集合。

void ln(int *F,int *G)
{
	memset(f,0,sizeof(f)),memset(g,0,sizeof(g));
	for(int i=1;i<st;i++) f[pct[i]][i]=F[i];
	f[0][0]=1;
	for(int i=0;i<=n;i++) FMT(f[i]);
	for(int S=0,tmp;S<st;S++)
	{
		for(int i=1;i<=n;i++)
		{
			g[i][S]=f[i][S],tmp=0;
			for(int j=1;j<i;j++)
				add(tmp,1ll*j*g[j][S]%Mod*f[i-j][S]%Mod);
			del(g[i][S],1ll*tmp*inv[i]%Mod);
		}
	}
	for(int i=0;i<=n;i++) iFMT(g[i]);
	for(int i=0;i<st;i++) G[i]=g[pct[i]][i];
}