快速沃尔什变换

（本文转载自桃酱的算法笔记，原文戳链接，已获得作者授权）

简介

沃尔什转换（Walsh Transform）是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。——维基百科

其实这个变换在信号处理中应用很广泛，fft 是 double 类型的，但是 walsh 把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度。

所以，FWT 和 FFT 的核心思想应该是相同的，都是对数组的变换。我们记对数组进行快速沃尔什变换后得到的结果为。

那么 FWT 核心思想就是：

我们需要一个新序列，由序列和序列经过某运算规则得到，即 $C = A \cdot B$ ；

我们先正向得到，再根据 $FWT[C]=FWT[A] \cdot FWT[B]$ 在的时间复杂度内求出；

然后逆向运算得到原序列。时间复杂度为 $O(n \log{n})$ 。

在算法竞赛中，FWT 是用于解决对下标进行位运算卷积问题的方法。

公式： $C_{i} = \sum_{i=j \bigoplus k}A_{j} B_{k}$

（其中 $\bigoplus$ 是二元位运算中的某一种，是普通乘法）

FWT 的运算

FWT 之与（&）运算和或（|）运算

与运算和或运算的本质是差不多的，所以这里讲一下或运算，与运算也是可以自己根据公式 yy 出来的。

或运算

如果有，那么的二进制位为的位置和的二进制位为的位置肯定是的二进制位为的位置的子集。

现在要得到，我们就要构造这个 fwt 的规则。

我们按照定义，显然可以构造 $FWT[A] = A' = \sum_{i=i|j}A_{j}$ ，来表示满足二进制中为的子集。

那么显然会有 $C_{i} = \sum_{i=j|k}A_{j}*B_{k} \implies FWT[C] = FWT[A] * FWT[B]$

那么我们接下来看怎么求。

首先肯定不能枚举了，复杂度为。既然不能整体枚举，我们就考虑分治。

我们把整个区间二分，其实二分区间之后，下标写成二进制形式是有规律可循的。

我们令表示的前一半，表示区间的后一半，那么就是 A 下标最大值的最高位为，他的子集就是他本身的子集（因为最高位为了），但是的最高位是，他满足条件的子集不仅仅是他本身，还包最高位为的子集，即

其中 merge 表示像字符串拼接一样把它们拼起来，就是普通加法，表示对应二进制位相加。

这样我们就通过二分能在 $O(\log{n})$ 的时间复杂度内完成拼接，每次拼接的时候要完成一次运算，也就是说在 $O(n\log{n})$ 的时间复杂度得到了。

接下来就是反演了，其实反演是很简单的，既然知道了的本身的子集是他自己 ()，的子集是 $（$ ），那就很简单的得出反演的递推式了：

与运算

与运算类比或运算可以得到类似结论

异或运算

最常考的异或运算。

异或的卷积是基于如下原理：

若我们令 $i\And j$ 中数量的奇偶性为与的奇偶性，那么与的奇偶性异或与的奇偶性等于 $i \operatorname{xor} j$ 与的奇偶性。

对于的运算其实也很好得到。

公式如下：

$A_{i} = \sum_{C_1}A_{j} - \sum_{C_2}A_{j}$ ( 表示 $i \And j$ 奇偶性为，表示 $i \And j$ 的奇偶性为 )

结论：

UFWT[A'] = merge(\frac{UFWT[A_0'] + UFWT[A_1']}{2}, \frac{UFWT[A_0'] - UFWT[A_1']}{2})

同或运算

类比异或运算给出公式：

$A_{i} = \sum_{C_1}A_{j} - \sum_{C_2}A_{j}$ ( 表示奇偶性为，表示的奇偶性为 )

UFWT[A'] = merge(\frac{UFWT[A_1'] - UFWT[A_0']}{2}, \frac{UFWT[A_1'] + UFWT[A_0']}{2})

例题

【CF103329F】【XXII Opencup, Grand Prix of XiAn】The Struggle

给出一个椭圆，其中所有整点的坐标均在 $[1,4 \cdot 10^6]$ 之间。求 $\sum_{(x,y) \in E} (x \oplus y)^{33}x^{-2}y^{-1} \mod 10^9+7$ 的值。

题解

这是一道比较不裸的题，出题人提供了详细的英文题解，具体请见此链接。

本页面最近更新：2023/5/25 17:17:02，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：Xeonacid, BinDir0, Enter-tainer, Ir1d, lxlonlyn, nocriz, nocrizwang, Tiphereth-A, TrisolarisHD, xyf007
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用