子集卷积

前置知识：FMT 或卷积

FMT

$FMT(x)=\sum_{i|x}x_i$

void FMT(int *A){
	for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]+=A[j^(1<<i)])%=mod;
}

IFMT

FMT的逆运算。

void IFMT(int *A){
	for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]-=A[j^(1<<i)])%=mod;
}

---

或卷积

$C=A|_{or}B \ ->C_i=\sum_{j|k==i}A_jB_k$

有

$FMT(C)=FMT(A)*FMT(B)$

这里的乘是点乘。

证明的话，带入拆开即可。

这样IFMT一遍就可以求$C$了。

---

子集卷积

题目传送门

多了个麻烦的限制，我们考虑多加一维。

$A(pc(i),i)$表示状态为$i$，有$pc(i)$个1。

那么：

$C_i=\sum_{i==j+k}A_j|_{or}B_k$

暴力枚举卷积是$O(n^32^n)$

把卷积写成FMT形式。

把求和号移到后面：

$C_i=IFMT(\sum_iFMT(A_j)*FMT(B_{i-j}))$

预处理FMT，点成、转回来。每一个部分都是$O(n^22^n)$。

code

#include<bits/stdc++.h>
using namespace std;
const int M=1e6+1e5+5,N=21,mod=1e9+9;
int n,m,up,a[N][M],b[N][M],c[N][M],cnt[M];
void FMT(int *A){
	for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]+=A[j^(1<<i)])%=mod;
}
void IFMT(int *A){
	for(int i=0;i<=n;i++) for(int j=0;j<=up;j++) if(j&(1<<i)) (A[j]-=A[j^(1<<i)])%=mod;
}
signed main(){
	ios::sync_with_stdio(false);
	cin>>n;up=(1<<n)-1;m=(1<<n);
	for(int i=1;i<=up;i++) cnt[i]=cnt[i&(i-1)]+1;
	for(int i=0;i<m;i++) cin>>a[cnt[i]][i];
	for(int i=0;i<m;i++) cin>>b[cnt[i]][i];
	for(int i=0;i<=n;i++) FMT(a[i]),FMT(b[i]);
	for(int i=0;i<=n;i++) for(int s=0;s<=up;s++) for(int j=0;j<=i;j++) (c[i][s]+=(1ll*a[j][s]*b[i-j][s])%mod)%=mod;
	for(int i=0;i<=n;i++) IFMT(c[i]);
	for(int i=0;i<m;i++) cout<<(c[cnt[i]][i]%mod+mod)%mod<<" ";	
	return 0;
}