快速沃尔什变换
（本文转载自 桃酱的算法笔记，原文戳 链接，已获得作者授权）
简介¶
沃尔什转换（Walsh Transform）是在频谱分析上作为离散傅立叶变换的替代方案的一种方法。——维基百科
其实这个变换在信号处理中应用很广泛，fft 是 double 类型的，但是 walsh 把信号在不同震荡频率方波下拆解，因此所有的系数都是绝对值大小相同的整数，这使得不需要作浮点数的乘法运算，提高了运算速度。
所以，FWT 和 FFT 的核心思想应该是相同的，都是对数组的变换。我们记对数组 进行快速沃尔什变换后得到的结果为 。
那么 FWT 核心思想就是：
我们需要一个新序列 ，由序列 和序列 经过某运算规则得到，即 ；
我们先正向得到 ，再根据 在 的时间复杂度内求出 ；
然后逆向运算得到原序列 。时间复杂度为 。
在算法竞赛中，FWT 是用于解决对下标进行位运算卷积问题的方法。
公式：
（其中 是二元位运算中的某一种， 是普通乘法）
FWT 的运算¶
FWT 之与（&）运算和或（|）运算¶
与运算和或运算的本质是差不多的，所以这里讲一下或运算，与运算也是可以自己根据公式 yy 出来的。
或运算¶
如果有 ，那么 的二进制位为 的位置和 的二进制位为 的位置肯定是 的二进制位为 的位置的子集。
现在要得到 ，我们就要构造这个 fwt 的规则。
我们按照定义，显然可以构造 ，来表示 满足二进制中 为 的子集。
那么显然会有
那么我们接下来看 怎么求。
首先肯定不能枚举了，复杂度为 。既然不能整体枚举，我们就考虑分治。
我们把整个区间二分，其实二分区间之后，下标写成二进制形式是有规律可循的。
我们令 表示 的前一半， 表示区间的后一半，那么 就是 A 下标最大值的最高位为 ，他的子集就是他本身的子集（因为最高位为 了），但是 的最高位是 ，他满足条件的子集不仅仅是他本身，还包最高位为 的子集，即
其中 merge 表示像字符串拼接一样把它们拼起来， 就是普通加法，表示对应二进制位相加。
这样我们就通过二分能在 的时间复杂度内完成拼接，每次拼接的时候要完成一次运算，也就是说在 的时间复杂度得到了 。
接下来就是反演了，其实反演是很简单的，既然知道了 的本身的子集是他自己 ()， 的子集是 ），那就很简单的得出反演的递推式了：
与运算¶
与运算类比或运算可以得到类似结论
异或运算¶
最常考的异或运算。
异或的卷积是基于如下原理：
若我们令 中 数量的奇偶性为 与 的奇偶性，那么 与 的奇偶性异或 与 的奇偶性等于 与 的奇偶性。
对于 的运算其实也很好得到。
公式如下：
( 表示 奇偶性为 ， 表示 的奇偶性为 )
结论：
同或运算¶
类比异或运算给出公式：
( 表示 奇偶性为 ， 表示 的奇偶性为 )
例题¶
【CF103329F】【XXII Opencup, Grand Prix of XiAn】The Struggle
给出一个椭圆 ，其中所有整点的坐标均在 之间。求 的值。
题解
这是一道比较不裸的题，出题人提供了详细的英文题解，具体请见 此链接。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：Xeonacid, nocriz
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用