一想到我 FWT 的笔记还没写就来写这个东西，我就忍不住笑了
子集卷积是一种定义在集合幂级数上的运算，虽然作者对集合幂级数一窍不通，但我们可以先从位运算的角度来理解一下子集卷积，做题的时候，你可以把这个东西看成状压来处理
给出子集卷积基本形式：
\[h_k=\sum_{i \,and \,j\,=\,0\,,i\,or\,j\,=\,k}f_i g_j \]这里比起最基本的 FWT 多了一个限制
我们考虑把 and 的限制拆掉，注意到 \(i\,and\,j=0\,\leftrightarrow |i|+|j|=|i \,or\,j|\)
所以柿子变成了这个样子
\[h_k=\sum_{|i|+|j|=|i \,or\,j| ，i\,or\,j\,=\,k}f_i g_j \]考虑构造占位多项式，对于\(f_{i,j}\)，若 \(popcount(j)=i\) ，则 \(f_{i,j}=j\)，反之则为 0
考虑推柿子
\[h_{i,k}=\sum_{i_1+i_2=i}\,\sum _{a \,or\,b=k}f_{i_1,a}g_{i_2,b}\\ \,\,\,\,\,\,\,\,\,\,\,=\sum_{i_1+i_2=i}\,f_{i_1} *g_{i_2} \]很明显后半部分可以进行 FWT
由于我们要进行对 \(i_1\) 和 \(i_2\) 的枚举，所以复杂度是 \(O(n^22^n)\) 的
顺便说一下，这里的序列长度是 \(2^n\)
Luogu 模板题据说卡常，加上了快读和取模优化后在 LOJ 上最慢点 1.2s ，成功排到了第 6 页
#include <iostream>
using namespace std;
const int maxN=(1<<21)+10,mod=1e9+9;
int n,lim;
int A[maxN],B[maxN];
int a[21][maxN],b[21][maxN],c[21][maxN];
int ans[maxN];
inline int read( ) {
char ch = ' '; int ret = 0;
while( ch > '9' || ch < '0' ) ch = getchar();
while( ch >= '0' && ch <= '9' ) ret = ret * 10 + ch - '0' , ch = getchar();
return ret;
}
inline int add(long long x,long long y){
long long q=x+y;
if(q>=mod) q-=mod;
return (int)q;
}
inline int jm(int x,int y){
int q=x-y;
if(q<0) q+=mod;
return q;
}
void fmt(int *f,int len){
for(int i=0;i<len;++i)
for(int j=0;j<(1<<len);++j)
if((j>>i)&1) f[j]=add(f[j],f[j^(1<<i)]);
}
void ifmt(int *f,int len){
for(int i=len-1;i>=0;--i)
for(int j=(1<<len)-1;j>=0;--j) if((j>>i)&1) f[j]=jm(f[j],f[j^(1<<i)]);
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
n=read();lim=(1<<n);
for(int i=0;i<lim;++i) A[i]=read(),a[__builtin_popcount(i)][i]=A[i];
for(int i=0;i<lim;++i) B[i]=read(),b[__builtin_popcount(i)][i]=B[i];
for(int i=0;i<=n;++i) fmt(a[i],n),fmt(b[i],n);
for(int i=0;i<=n;++i){//枚举card
for(int j=0;j<=i;++j)//枚举两部分中的一部分
for(int k=0;k<lim;++k)
c[i][k]=add(c[i][k],(1ll*a[j][k]*b[i-j][k]%mod));
ifmt(c[i],n);
}
for(int i=0;i<lim;++i) cout << c[__builtin_popcount(i)][i] << " ";
cout <<endl;
return 0;
}