概念

快速沃尔什变换是一种类似 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$ 优化转移。

代码