快速沃尔什变换

刚了一道题超级久...最后 solution 给的做法是 FWT 。觉得做法还挺妙的。
顺带讲讲对 FWT 的理解，怕自己又不记得了。

原理

FWT 是求形如下式的卷积式子的高效方法：

$C_{k}=\sum_{i\odot j=k} A_iB_j$

其中 $\odot$ 代表了一种二进制运算。

一般而言，我们要求高效地求 $A$ 和 $B$ 的某种卷积，都是让某种线性变换作用在 $A$ 和 $B$ 上，得到 $A'$ 和 $B'$ 。然后如果 $A$ 和 $B$ 卷完是 $C$ ，那么我们要求通过 $A'$ 和 $B'$ 可以快速地求出 $C'$ （最常见的情况是直接点乘） ，再将 $C'$ 逆变换回去得到 $C$ 。FFT 就是生动的例子。

注意：我们做的一定是线性变换，即只存在加减。我们可以这样定义一种线性变换：

$A'_x=\sum_if(x,i)A_i$

则有

$C'_x=\sum_if(x,i)C_i=\sum_if(x,i)\sum_{j\odot k=i}A_jB_k\\ A'_xB'x=\sum_{i}f(x,i)A_i\sum_{j}f(x,j)B_j=\sum_{i}\sum_{j}f(x,i)f(x,j)A_iB_k$

所以可以得到变换 $f$ 应满足的重要要求：

$f(x,i\odot j)=f(x,i)f(x,j)$

我们来考虑怎么对二进制运算构造 $f$ 。

考虑或。因为有恒等式 $i\text{ or } j\in x=i\in x \text{ or } j\in x$ 。所以此时可以构造 $f(x,i)=[i\in x]$。

与类似，构造 $f(x,i)=[x\in i]$ 。

异或操作比较麻烦。考虑两个性质：

• $x \text{ xor } y$ 中 $1$ 的个数的奇偶性与 $x$ 中 $1$ 的个数和 $y$ 中 $1$ 的个数的和的奇偶性相同；
• $(x\text{ xor } y) \text{ and } z=(x\text{ and } z) \text{ xor } (y\text{ and } z)$

故我们可以构造 $f(x,i)=(-1)^{|x \text{ and } i|}$ 。

实现

上面是 FWT 的原理。下面讲讲如何实现。

对每一位单独考虑。假设 $f_k(u)$ 表示 $u$ 的二进制拆分下，前 $k$ 位代表的 $2^{k}$ 个数的 $f(x,i)A_i$ 的和，后面的位数与 $u$ 严格相等。

假设 $u$ 和 $v$ 仅在第 $k+1$ 位不同，且 $u<v$ 。

所以对于或操作有 $f_{k+1}(u)=f_k(u),f_{k+1}=f_{k}(u)+f_{k}(v)$ 。
对于与操作有 $f_{k+1}(u)=f_{k}(u)+f_{k}(v),f_{k+1}=f_k(u)$ 。

对于异或， $u$ 在第 $k+1$ 无影响，而 $v$ 在第 $k+1$ 位恰好有 $(-1)$ 的影响（之前未考虑过这个 $-1$），所以有 $f_{k+1}(u)=f_{k}(u)+f_{k}(v),f_{k+1}(v)=f_k(u)-f_k(v)$ 。

例题 CF662C Binary Table

$\text{Link}$

设 $\text{sta}_i$ 表示第 $i$ 列的初始状态，第 $j$ 位为 $1$ 表示 $(j,i)$ 为 $1$ 。

记 $F(s)=\sum_{i=1}^{m} [\text{sta}_i]$ ，即状态的数量。

设长度为 $n$ 的二进制串 $\text{trans}$ 表示每一行的翻转情况。那么每一列的最终情况为 $\text{sta}\text{ xor } \text{trans}$ 。

可以发现，假设钦定了行的翻转情况，那么每一列的翻转情况是确定的—— $1$ 少 $0$ 多则不翻，否则翻。我们可以设 $G(s)$ 表示 $s$ 的 $\min\{\text{cnt}_0,\text{cnt}_1\}$ 。所以有式子：

$\text{Ans}_{\text{trans}}=\sum_{i}F(i)G(i\text{ xor } \text{trans})$

这样子没办法优化。我们把它写成两重循环，尝试写成卷积。

$\begin{aligned} \text{Ans}_{\text{trans}}=&\sum_{i}\sum_{j}[i\text{ xor }\text{trans}=j]F(i)G(j)\\ &=\sum_{i}\sum_{j}[i\text{ xor }j=\text{trans}]F(i)G(j) \end{aligned}$

于是就可以用 FWT 来优化做到 $\mathcal{O}(n2^n)$ 了。或许在习惯的人眼里很板子，但是自我感觉那步化两重循环还是挺不容易想到的...？所以说以后碰见下面的式子也要小心哦：

$H_i=\sum_{j}F_jG(j\text{ xor }i)$