子集卷积问题即对于每一个二进制集合 \(S(|S|\leq n)\)，求出：
\[C_S=\sum_{T\in S}A_TB_{S\operatorname{xor}T} \]不难发现其等价于：
\[C_S=\sum_{T1|T2=S,|T1|+|T2|=|S|}A_{T1}B_{T2} \]如果只有第一个条件其可以用 FMT \(O(n2^n)\) 地求出。
加入第二个条件后，我们可以分组进行 FMT，具体而言，对于每一个 \(|S|\)，枚举转移到它的 \(|T1|,|T2|\)，将 \(A\) 中集合大小为 \(|T1|\) 的和 \(B\) 中集合大小为 \(|T2|\) 的提取出来得到 \(A_{|T1|},B_{|T2|}\) 做 FMT，最终得到对应的 \(C_{|S|}\) 数组，在这个得到的数组中，为了满足条件 \(|S|=|T1|+|T2|\)，我们需要将 \(C_{|S|}\) 中所有二进制集合大小不为 \(|S|\) 的位置抛开。
由于 FMT 的线性变换性质，所以 FMT 数组可加，这使得我们可以预先将所有 \(A_{|S|}\) 和 \(B_{|S|}\) 对应的 FMT 数组预处理出来，而 \(C_{|S|}\) 对应的 FMT 数组我们通过枚举对应位置上的 \(A_{|T1|},B_{|T2|}\) 的 FMT 数组进行暴力卷积得到。
分析一下复杂度，对所有位置暴力卷积 \(O(n^22^n)\)，对 \(O(|S|)\) 个数组做 FMT 的复杂度同样为 \(O(n^22^n)\)，故总复杂度为 \(O(n^22^n)\)。
代码
void fmt(ll *f){
for(register int len=1;(len<<1)<=all+1;len<<=1){
for(register int i=0;i<=all;i+=(len<<1)){
rep(j,i,i+len-1){
ll tmp=f[j];
f[j]=C[0][0]*f[j]+C[0][1]*f[j+len];
f[j+len]=C[1][0]*tmp+C[1][1]*f[j+len];
}
}
}
rep(i,0,all) f[i]%=mod;
}
int main(){
C[0][0]=C[1][0]=C[1][1]=1;
rd(n);
all=(1<<n)-1;
rep(i,0,all){
if(i) popcnt[i]=1+popcnt[i^lowbit(i)];
rd(a[popcnt[i]][i]);
}
rep(i,0,all) rd(b[popcnt[i]][i]);
rep(i,0,n){
fmt(a[i]);
fmt(b[i]);
}
C[1][0]=-1;
rep(i,0,n){
rep(j,0,i){
rep(k,0,all){
c[i][k]+=a[j][k]*b[i-j][k];
c[i][k]%=mod;
}
}
fmt(c[i]);
}
rep(i,0,all) printf("%lld ",(c[popcnt[i]][i]+mod)%mod);
}