子集卷积
<pre><code class="language-cpp">#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;
} </code></pre>
<p>下面是例子代码</p>
<pre><code class="language-cpp">#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;
}</code></pre>