概念

快速沃尔什变换是一种类似 FFT，用来加速逻辑位运算卷积的算法。具体地，它被设计为用来解决以下问题：

$$C_k=\sum_{i\oplus j=k}a_i\times b_j$$

其中，$\oplus$ 表示位运算 $\lor, \wedge, \veebar$。直接枚举 $i,j$ 的复杂度是 $\Theta(n^2)$，FWT 能加速这个过程到 $\Theta(n\log n)$。

原理

前面说到它类似 FFT，因为它们都是通过先做一个变换，相乘，然后逆变换得到结果的，而变换的过程都是折半、分治。

我们定义变换为 $tf$，有

$$tf(C)=tf(A)\times tf(B)$$

对于 $tf$，分治的过程只需要前后折半，不像 FFT 需要二进制翻转，更为简洁；麻烦的是，对于每种不同的位运算，$tf$ 和 $utf$ 函数是不同的。

下面列出了三种运算的对应函数：

xor

$$\begin{aligned} tf(A)&= (tf(A_0)+tf(A_1),tf(A_0)-tf(A_1)) \\ utf(A)&= (utf(\frac{A_0+A_1}{2}),utf(\frac{A_0-A_1}{2}))\end{aligned}$$

and

$$\begin{aligned}tf(A)&=(tf({A}{0})+tf({A}{1}),tf({A}{1})) \\ utf(A)&=(utf({A}{0})-utf({A}{1}),utf({A}{1}))\end{aligned}$$

or

$$\begin{aligned}tf(A)&=(tf({A}{0}),tf({A}{1})+tf({A}{0})) \\ utf(A)&=(utf({A}{0}),utf({A}{1})-utf({A}{0})) \end{aligned}$$

所有式子中，$A_0$ 表示 $A$ 的前半部分，$A_1$ 为后半部分。

例题

给定一个序列 $a$，问 $\text{xor}$ 为 $0$ 子序列的最长长度。

思路

我们设所有元素的 $\text{xor}$ 为 $w$，我们实际上要挑出最少的元素，使得它们的 $\text{xor}$ 为 $w$，剩下的元素就是题目中要我们求的最长子序列了。

具体地，我们设 $f(i,x)$ 表示选 $i$ 个数，异或和能否恰好为 $x$。因为在最劣情况下，最大的 $i$ 依然不会超过 $\log$ 级别，我们可以直接 $FWT$ 优化转移。

代码