快速沃尔什变换

(本文转载自 桃酱的算法笔记,原文戳 链接,已获得作者授权)

简介

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

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

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

那么 FWT 核心思想就是:

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

我们先正向得到 FWT[A], FWT[B] ,再根据 FWT[C]=FWT[A] \cdot FWT[B] O(n) 的时间复杂度内求出 FWT[C]

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

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

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

(其中 \bigoplus 是二元位运算中的某一种, * 是普通乘法)

FWT 的运算

FWT 之与(&)运算和或(|)运算

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

或运算

如果有 k=i|j ,那么 i 的二进制位为 1 的位置和 j 的二进制位为 1 的位置肯定是 k 的二进制位为 1 的位置的子集。

现在要得到 FWT[C] = FWT[A] * FWT[B] ,我们就要构造这个 fwt 的规则。

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

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

那么我们接下来看 FWT[A] 怎么求。

首先肯定不能枚举了,复杂度为 O(n^2) 。既然不能整体枚举,我们就考虑分治。

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

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

FWT[A] = merge(FWT[A_0], FWT[A_0] + FWT[A_1])

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

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

接下来就是反演了,其实反演是很简单的,既然知道了 A_0 的本身的子集是他自己 ( A_0 = FWT[A_0] ), A_1 的子集是 FWT[A_0] + FWT[A_1](A_1 = A_0' + A_1' ),那就很简单的得出反演的递推式了:

UFWT[A'] = merge(UFWT[A_0'], UFWT[A_1'] - UFWT[A_0'])

与运算

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

FWT[A] = merge(FWT[A_0] + FWT[A_1], FWT[A_1])
UFWT[A'] = merge(UFWT[A_0'] - UFWT[A_1'], UFWT[A_1'])

异或运算

最常考的异或运算。

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

若我们令 i\And j 1 数量的奇偶性为 i j 的奇偶性,那么 i k 的奇偶性异或 j k 的奇偶性等于 i \operatorname{xor} j k 的奇偶性。

对于 FWT[A] 的运算其实也很好得到。

公式如下:

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

结论:

FWT[A] = merge(FWT[A_0] + FWT[A_1], FWT[A_0] - FWT[A_1])
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} ( C_1 表示 i|j 奇偶性为 0 C_2 表示 i|j 的奇偶性为 1 )

FWT[A] = merge(FWT[A_1] - FWT[A_0], FWT[A_1] + FWT[A_0])
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

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

题解

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


评论