子集卷积

#include <iostream>
using namespace std;
const int maxn = (1 << 18) + 5;
int a[50][maxn], b[50][maxn];
int main(){
    int n;
    scanf("%d", &n);
    int U = (1<<n);
    for(int i = 1; i < U; i++)    popct[i] = popct[i >> 1] + (i & 1);
    for(int i = 0; i < U; i++)    scanf("%d", &a[popct[i]][i]);
    for(int i = 0; i < U; i++)    scanf("%d", &b[popct[i]][i]);
    for(int i = 0; i <= n; i++)    FMT(a[i], 1), FMT(b[i], 1);
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= i; j++)
            for(int s = 0; s < U; s++)
                (c[i][s] += 1LL * a[j][s] * b[i-j][s] % mod) %= mod;
    for(int i = 0; i <= n; i++)    FMT(c[i], -1);
    for(int i = 0; i < U; i++)    printf("%d ", c[popct[i]][i]);
    return 0;
}

下面是例子代码

#include<bits/stdc++.h>
#define rep(i,b,e) for(int i=(b);i<(e);++i)
#define dep(i,b,e) for(int i=(b);i>=(e);--i)
#define ll long long
#define inf 0x3f3f3f3f
#define il inline

using namespace std;

const int mod=998244353;
int n,m,u,v,w;ll sum;
int g[20][20];
int cnt[1<<18];
ll h[19][1<<18],f[19][1<<18];

void FMT(ll *A,int n,int o=1){  // 快速莫比乌斯变换,求子集和
    for(int i=1;i<(1<<n);i<<=1)
        for(int j=0;j<(1<<n);++j)
            if(i&j) (A[j]+=A[i^j]*o+mod)%=mod;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m;
    rep(i,0,n){
        rep(j,0,n) g[i][j]=(i==j? 0:inf);
    }
    while(m--){
        cin>>u>>v>>w;
        u--;v--;
        g[u][v]=g[v][u]=min(g[u][v],w);
    }
    rep(k,0,n){
        rep(i,0,n){
            rep(j,0,n) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
        }
    }
    memset(cnt,0,sizeof(cnt));
    memset(h,0,sizeof(h));
    memset(f,0,sizeof(f));
    rep(i,0,1<<n){
        rep(j,0,n) cnt[i]+=((i&(1<<j))>0);
    }
    rep(i,1,1<<n){
        h[cnt[i]][i]=0x3f3f3f3f3f3f3f3f;
        rep(j,0,n){
            if(i&(1<<j)){
                sum=1;
                rep(k,0,n) if(i&(1<<k)) sum+=g[j][k];
                h[cnt[i]][i]=min(h[cnt[i]][i],sum);
            }
        }
        f[cnt[i]][i]=(h[cnt[i]][i]%=mod);
    }
    rep(i,0,n+1){
        FMT(h[i],n);
        FMT(f[i],n);
    }
    rep(i,1,n+1){
        rep(j,0,i+1){
            rep(k,0,1<<n) (f[i][k]+=1ll*h[j][k]*f[i-j][k]%mod)%=mod;
        }
        FMT(f[i],n,-1);
        rep(k,0,1<<n) if(cnt[k]!=i) f[i][k]=0;
        if(i!=n) FMT(f[i],n);
    }
    cout<<f[n][(1<<n)-1]<<endl;
    system("pause");
    return 0;
}