UPD:智商着急现场...这个做法其实就是vfk论文的快速莫比乌斯变换......并不是什么新做法.....我是文盲...

给出$f[0..(2^n)-1],g[0..(2^n)-1]$,求$h[0…(2^n)-1]$,满足h[x]=sigma{f[i]*g[j],1<=i<=n,1<=j<=n,i|j==x}

N<=20

传说中的集合并卷积？作为不会FWT的选手,我们考虑如何写暴力.

暴力算法1:枚举i和j更新h[i|j]可以做到O(4^n).

暴力算法2:容斥原理+枚举子集的子集可以做到O(3^n)

我们记F[i]=sigma(f[j],j&i==j),G[i]=sigma{g[j],j&i==j},H[i]=F[i]*G[i],那么H[i]=sigma{h[j],i&j==j}, 通过枚举子集的子集可以O(3^n)得到H[]数组，通过枚举子集的子集可以O(3^n)用H[]数组容斥出h[]数组,求 h[i]的时候,枚举i的所有子集,如果子集j的元素个数和i相差偶数个那么H[j]对h[i]的贡献是正的,如果子集j的元素和i相差奇数个那么H[j]对h[i]的贡献是负的.

也就是说: h[i]=sigma{H[j]*(-1)^(cnt1(i-j)),j&i==j},cnt1(x)表示x的二进制表示中1的个数

接下来我们把O(3^n)的容斥算法优化到O(n*2^n).

考虑第一步预处理,我们需要求出F[x]=sigma(f[i],i&x==i)（G数组的处理和F数组相同） 如果我们求出了1到x-1的F值,并不能利用前面这些项较快地计算出F[x]。

不妨考虑x的最高位2^i,我们把x的子集分成两部分，一部分包含元素i，一部分不包含元素i，不包含元素i的部分就是F[x-(2^i)],关键是包含i的部分.我们无法从F[1],F[2],…一直顺序推到F[2^n-1]

我们记F[j][i]为只允许最后j位和i不同的i的所有子集的和,那么边界是F[0][i]=f[i] F[j][i]=F[j-1][i](i的第j位为0) =F[j-1][i]+F[j-1]i-(2^j) 前一维可以直接滚掉,那么我们就用O(n*2^n)的时间解决了F数组和G数组

for(int j=0;j<n;++j){
    for(int i=0;i<lim;++i){
        if((i>>j)&1)f[i]+=f[i^(1<<j)];
    }
}

(其实是一个n维前缀和？这个技巧是以前别人讲课的时候看见的) 接下来考虑H数组.我们发现从H数组求h数组相当于从F数组求f数组,我们把之前的DP过程倒过来就可以了…就是加号改成减号…因为每个二进制位本质一样所以从高位向低位枚举还是从低位向高位枚举都一样.

这个地方也可以理解为,h[j][i]为只允许最后j位和i不同的i的所有子集对i的贡献之和,

边界是 $h[0][i]=f[i]$

$h[j][i]=h[j-1][i](i的第j位为0)$

$h[j][i]=h[j-1][i]-h[j-1][i-(2^j)](i的第j位为1)$ 可以理解为每增加一个二进制位会使贡献的正负号改变一次所以把加号变成减号.

然后这个方法并没有什么可扩展性,只能算集合并卷积。

下面这个代码是mod 2^32意义下的,利用unsigned int自然溢出

#include<cstdio>
#include<cctype>
typedef unsigned int u32;
void read(u32 &x){
    char ch;while(ch=getchar(),!isdigit(ch));x=ch-'0';
    while(ch=getchar(),isdigit(ch))x=x*10+ch-'0';
}
const int maxn=1<<20;
u32 f[maxn],g[maxn];
u32 H[maxn];
int main(){
    freopen("evaluation.in","r",stdin);
    freopen("evaluation.out","w",stdout);
    u32 n;read(n);int lim=1<<n;
    for(int i=0;i<lim;++i){
        read(f[i]);
    }
    for(int i=0;i<lim;++i){
        read(g[i]);
    }
    for(int i=0;i<n;++i){
        for(int j=0;j<lim;++j){
            if((j>>i)&1)f[j]+=f[j^(1<<i)];
        }
      }
    for(int i=0;i<n;++i){
      for(int j=0;j<lim;++j){
          if((j>>i)&1)g[j]+=g[j^(1<<i)];
      }
     }
    for(int i=0;i<lim;++i)H[i]=f[i]*g[i];
    for(int i=0;i<n;++i){
        for(int j=0;j<lim;++j){
            if((j>>i)&1)H[j]-=H[j^(1<<i)];
        }
    }
    u32 ans=0;
    for(int i=0;i<lim;++i){
        ans+=H[i]*(i+1);
    }
    printf("%u\n",ans);
    fclose(stdin);fclose(stdout);
    return 0;
}