快速沃尔什变换

fengwentao

解决集合卷积。说人话就是把FFT下标的+变成位运算。

&和|的FWT可以用高维前缀和来理解。

考虑对于A | B = C，我们有A‘_i = ∑A_j，其中j⊂i。B同理。

接下来我们把A‘和B‘对位相乘得C‘。显然有C‘_i = ∑C_j，其中j⊂i。

接下来把C逆变换回去即可。

考虑怎么求A‘。

我们先求一次A⁰，A⁰_i表示二进制第0位是i的子集，0位以上都是严格等于i的位置权值和。

然后求A¹，A¹_i表示二进制0,1位都是i的子集，而1位以上严格等于i的位置权值和。

然后搞完最高位就完事了。逆变换就反着来。

FWT

原文：https://www.cnblogs.com/huyufeifei/p/10513402.html