FST

• 子集卷积

[res_k=sum_{i&j=0\i~|~j=k}f_ib_j ]

//Data
const int N=20,M=1<<N;
const int mod=1e9+9;
int n,m,bc[M+7],f[N+7][M+7],g[N+7][M+7],res[N+7][M+7];

//FMT
void FWT(int a[],int t){
	for(int i=1;i<m;i<<=1)
		for(int j=0;j<m;j+=i<<1)
			for(int k=j;k<i+j;k++)
				(a[i+k]+=(a[k]*t+mod)%mod)%=mod;
}

//Main
int main(){
// 	freopen("NON.in","r",stdin);
	scanf("%d",&n),m=1<<n;
	for(int i=1;i<m;i++) bc[i]=bc[i-(i&-i)]+1;
	for(int i=0;i<m;i++) f[bc[i]][i]=ri;
	for(int i=0;i<m;i++) g[bc[i]][i]=ri;
	for(int i=0;i<=n;i++) FWT(f[i],1),FWT(g[i],1);
	for(int i=0;i<=n;i++)
		for(int j=0;j<=i;j++)
			for(int k=0;k<m;k++)
				(res[i][k]+=(ll)f[j][k]*g[i-j][k]%mod)%=mod;
	for(int i=0;i<=n;i++) FWT(res[i],-1);
	for(int i=0;i<m;i++) printf("%d ",res[bc[i]][i]);putchar(10);
	return 0;
}