```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1048576,mod=1000000009;
#define MP make_pair
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
int x=0,f=0;char ch=getchar();
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,lim,sz[maxn],f[21][maxn],g[21][maxn],h[21][maxn],s[21][maxn],sl[21];
inline void dec(int &x){x+=x>>31?mod:0;}
void FMT(int *A,int lwr){
for(int i=1;i<lim;i<<=1){
int x=max(0,lwr-sz[i-1]),uprx=sl[x];
FOR(j_,0,uprx-1){
int j=(i<<1)*s[x][j_];
if(j>=lim) break;
int y=max(0,lwr-sz[j]),upry=sl[y];
FOR(k_,0,upry-1){
int k=s[y][k_];
if(k>=i) break;
dec(A[i+j+k]+=A[j+k]-mod);
}
}
}
}
void IFMT(int *A,int lwr){
for(int i=1;i<lim;i<<=1){
int x=max(0,lwr-sz[i-1]),uprx=sl[x];
FOR(j_,0,uprx-1){
int j=(i<<1)*s[x][j_];
if(j>=lim) break;
int y=max(0,lwr-sz[j]),upry=sl[y];
FOR(k_,0,upry-1){
int k=s[y][k_];
if(k>=i) break;
dec(A[i+j+k]-=A[j+k]);
}
}
}
}
int main(){
n=read();lim=1<<n;
FOR(i,1,lim-1) sz[i]=sz[i>>1]+(i&1);
FOR(i,0,lim-1) f[sz[i]][i]=read();
FOR(i,0,lim-1) g[sz[i]][i]=read();
FOR(i,0,n) FOR(j,0,lim-1) if(sz[j]>=i) s[i][sl[i]++]=j;
FOR(i,0,n){
FMT(f[i],i);FMT(g[i],i);
FOR(j,0,i){
int x=max(j,i-j),uprx=sl[x];
FOR(k,0,uprx-1) h[i][s[x][k]]=(h[i][s[x][k]]+1ll*f[j][s[x][k]]*g[i-j][s[x][k]])%mod;
}
IFMT(h[i],(i+1)>>1);
}
FOR(i,0,lim-1) printf("%d ",h[sz[i]][i]);
}
```
by AThousandSuns @ 2020-02-16 18:12:46
这是新题？
by 诱宵美⑨ @ 2020-02-16 18:13:07
Fast Mobius Transform! ~~但是据说这玩意可以被 FWT 完全代替吧~~
by Hydrate @ 2020-02-16 18:14:52
@[北辰yama](/user/244079) 我一般 FMT 是用长得像 FWT 的方式实现的，而且实测常数能省掉不少。
by AThousandSuns @ 2020-02-16 18:16:44
理论上好像没啥问题，要不待会我自己写一下？
by 诱宵美⑨ @ 2020-02-16 18:17:51
@[AThousandSuns](/user/72118) 这您得问编译器。估计是您在里面加了 if 以后编译器没法优化了？
by mrsrz @ 2020-02-16 18:21:09
/jk
by AThousandSuns @ 2020-02-16 18:22:15
@[AThousandSuns](/user/72118) 其实“直接自然溢出啥事没有”是我喷这题出题人给它加了个取模…………
by mrsrz @ 2020-02-16 18:23:29
然后被 lxl 拿去当题目名了/px
by mrsrz @ 2020-02-16 18:23:43
膜一下奇怪的ntf
by 1saunoya @ 2020-02-16 18:25:52