博客园我的博客快速沃尔什变换解决的卷积问题快速沃尔什变换（FWT）是解决这样一类卷积问题：\[c_i=\sum_{i=j\odotk}a_jb_k\]其中，\(\odot\)是位运算的一种。举个例子，给定数列\(a,b\)，求：\[c_i=\sum_{j\oplusk=i}a_jb_k\]FWT的思想看到FWT的名字，我们可以联想到之前学过

本文中使用\(\cap\)表示按位与，用\(\cup\)表示按位或Part1.与/或卷积First.问题引入给定长度为\(2^n\)的数列\(A,B\)，求\(C_i=\sum_{j\cupk=i}A_j\timesB_k\)显然有\(O(4^n)\)的暴力Second.变换这一部分可以参考快速莫比乌斯变换中的Zeta变换，即

省流：输+赢D按位分析。既然两个数异或后的结果是\(C\)，那就考虑\(C\)中为\(1\)的数中有几个是在\(X\)当中的。假如\(\text{a-popcnt(X)==b-popcnt(Y)}\)，那么在\(C\)中为\(0\)的数中随便选\(\text{a-popcnt(x)}\)个即可。注意longlong。codeE假如