自动搬运

查看原文

来自洛谷，原作者为

	Purslane AFO

搬运于2025-08-24 23:13:52，当前版本为作者最后更新于2025-04-19 16:09:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Solution

集合幂级数的 $\exp$ 解决的是这样一个问题：给定全集 $U$ 和它的一个子集 $S$，计算：

$$\sum_{S_1 \cup S_2 \cup \cdots \cup S_k = S , |S_1| + \cdots + |S_k| = |S|} \prod a_{S_i} $$

注意这里的 $S_i$ 是无序的，我们只考虑他们构成的子集族。

定义两个集合幂级数的乘法为子集卷积，那么给定集合幂级数 $F$（要求 $[x^{\varnothing}]F = 0$）求出 $T = \sum_{i \ge 0 } \dfrac{F^i}{i!}$。

经典的，我们定义 $F_i = \sum_{S} [x^S] F \times [\text{popcount}(S) = i]$。

那么对于每个 $S$ 和正整数 $t$，我们只用求出 $g_t = \sum_k \frac{1}{k!} \sum_{i_1 + i_2 + \cdots i_k = t} \prod_j F_{i_j,S}$。发现对于固定的 $S$，$g_*$ 就是 $F_{*,S}$ 在形式幂级数意义下的 $\rm exp$。

但是这里我们不用真的去算 $\rm exp$，因为维数太小了！事实上，我们有 $O(n^2)$ 求 $\exp$ 的方法，直接递推即可。

复杂度 $O(n^2 2^n)$。

#include<bits/stdc++.h>
#define int long long 
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=(1<<20)+10,MOD=998244353;
int n,a[MAXN],f[21][MAXN],g[21][MAXN];
void fwt(int *f,int l,int r) {
	if(l==r) return ;
	int mid=(l+r)>>1;
	fwt(f,l,mid),fwt(f,mid+1,r);
	ffor(i,l,mid) {
		int j=i-l+mid+1;
		int x=f[i],y=f[j];
		f[i]=(x+y)%MOD,f[j]=(x-y)%MOD;
	}
	return ;
}
int inv[MAXN];
int qpow(int base,int p) {
	int ans=1;
	while(p) {
		if(p&1) ans=ans*base%MOD;
		base=base*base%MOD,p>>=1;
	}
	return ans;
}
void exp(int *f,int *g) {
	g[0]=1;
	ffor(i,1,n) {
		ffor(j,1,i) g[i]=(g[i]+g[i-j]*f[j]%MOD*j)%MOD;
		g[i]=g[i]*inv[i]%MOD;	
	}
	return ;
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,0,(1<<n)-1) cin>>a[i],f[__builtin_popcount(i)][i]=a[i];
	ffor(i,1,n) inv[i]=qpow(i,MOD-2);
	ffor(i,0,n) fwt(f[i],0,(1<<n)-1);
	ffor(i,0,(1<<n)-1) {
		int F[21],G[21];
		memset(F,0,sizeof(F)),memset(G,0,sizeof(G));
		ffor(j,0,n) F[j]=f[j][i];
		exp(F,G);
		ffor(j,0,n) g[j][i]=G[j]; 
	}
	ffor(i,0,n) fwt(g[i],0,(1<<n)-1);
	int div=qpow(1<<n,MOD-2);
	ffor(i,0,(1<<n)-1) cout<<(g[__builtin_popcount(i)][i]*div%MOD+MOD)%MOD<<' ';
	return 0;
}

把 $\exp$ 换成 $\ln$ 或者乘法逆就可以把另外两个模板题给过了。