题解：P12230 集合幂级数 exp

· · 题解

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 或者乘法逆就可以把另外两个模板题给过了。