一个数学不好的菜鸡的快速沃尔什变换(FWT)学习笔记
曾经某个下午我以为我会了FWT，结果现在一丁点也想不起来了……看来“学”完新东西不经常做题不写博客，就白学了 = =
我没啥智商 ，网上的FWT博客我大多看不懂，下面这篇博客是留给我我再次忘记FWT时看的，所以像我一样的没智商选手应该也能看懂！有智商选手更能看懂咯！
（写得非常匆忙，如有任何错误请在评论区指正！TAT）
什么是FWT
FWT是用来快速做位运算卷积的。位运算卷积是什么？给出两个数组(A)和(B)（长度相等且是2的整数次幂），求一个数组(C)，满足(A * B = C)，这个“(*)”的定义如下：$$A * B = C Leftrightarrow C_k = sum_{ioplus j = k}A_i cdot B_j$$ 其中“(oplus)”是一种位运算，可以是与(&)、或(|)、异或(^)。
为什么要有一个变换呢？回想一下FFT，FFT求(A*B)时（这个“(*)”是多项式乘法那个卷积），是把(A)和(B)各自“变换”了一下，然后把变换后的数组按位相乘，得到“变换后的(C)”——(tf(C))，然后把(tf(C))逆变换回去，得到(C)数组。
FWT做位运算卷积的原理也类似，想要实现快速位运算卷积，就要找到一种变换(tf)满足(tf(A*B) = tf(A) imes tf(B))，这里的“( imes)”表示两个数组按位相乘（和那个表示卷积的“(*)”不是一个符号）。
再强调一下本文中符号的定义，在下文中：
用FWT解决或卷积
或卷积，就是把(A * B = C Leftrightarrow C_k = sum_{ioplus j = k}A_i cdot B_j)中的“(oplus)”定义为按位或运算(|)。我们的目标是找到一种变换(tf)满足(tf(A*B) = tf(A) imes tf(B))，还要找到一种逆变换(utf)，能把(tf(C))变回(C)。
目标
- 找到(tf)
- 找到(utf)
找到(tf)
这是位运算，所以应该按位分治。
根据下标在最高位是0还是1，把(A)数组拆成两个数组(A_0)和(A_1)，(A_0)是(A)中下标最高位是0的元素组成的数组，(A_1)是(A)中下标最高位是1的元素组成的数组——实际上，(A_0)就是(A)的前一半，(A_1)是(A)的后一半。用(A = (A_0, A_1))表示这种“等式右边两个数组首尾相接就能得到等式左边的数组”的关系。
定义$$tf(A) = (tf(A_0), tf(A_1) + tf(A_0))$$
当(A)长度为1，无法再划分时，(tf(A) = A)。
对了，显然(tf(X + Y) = tf(X) + tf(Y))，这里“(+)”就是按位相加。
（这个(tf)是怎么找到的？这篇博客讲了讲……但是即使我知道了如何找到或卷积的(tf)，异或卷积的我还是找不出来……还是甩出这个式子然后证明它吧。）
来证明一下(tf(C = A * B) = tf(A) imes tf(B))。
当(A, B)长度均为1时显然。
当(A, B)长度大于1时 ，我们使用归纳法——可以假定“长度除以2后(tf(C = A * B) = tf(A) imes tf(B))是成立的”，即$$tf(A_0*B_0) = tf(A_0) imes tf(B_0) f(A_1 * B_1) = tf(A_1) imes tf(B_1) f(A_0 * B_1) = tf(A_0) imes tf(B_1) f(A_1 * B_0) = tf(A_1) imes tf(B_0)$$如果我们在这四个条件的基础上能证明(tf(C = A * B) = tf(A) imes tf(B))，则这四个条件递归证明即可，递归到长度为1时，就直接证毕了。
那么如何证明当前这一层(tf(C = A * B) = tf(A) imes tf(B))呢？
首先，$$C=(A_0 * B_0, A_1 * B_0 + A_0 * B_1 + A_1 * B_1)$$。这是可以理解的：在(A)中最高位是0的一个下标，和在(B)中最高位是0的一个下标，或起来还是0，所以他俩卷积的结果应该放在(C_0)中，其余三项同理。
然后从等式左边推一下，$$egin{align}tf(C) &= (tf(A_0 * B_0), tf(A_1 * B_0 + A_0 * B_1 + A_1 * B_1) + tf(A_0 * B_0))&=(tf(A_0B_0), tf(A_1B_0) + tf(A_0B_1) + tf(A_1 * B_1) + tf(A_0 * B_0)) &= (tf(A_0) imes tf(B_0), tf(A_1) imes tf(B_0) + tf(A_0) imes tf(B_1) + tf(A_1) imes tf(B_1) + tf(A_0) imes tf(B_0))end{align*}$$
这一步是基于(tf)的定义以及上面的那四个条件的。
然后从等式右边推一下，$$egin{align}tf(A) imes tf(B) &= (tf(A_0), tf(A_1) + tf(A_0)) imes (tf(B_0), tf(B_1) + tf(B_0)))&=(tf(A_0) imes tf(B_0), tf(A_0) imes tf(B_0) + tf(A_1) imes tf(B_0) + tf(A_0) imes tf(B_1) + tf(A_1) imes tf(B_1))end{align}$$
这一步是基于“( imes)”符号的意义——按位相乘得出来的。
这样一来，等式两边恰好相等诶！
所以我们已经找到了或卷积的(tf)：$$tf(A) = (tf(A_0), tf(A_1) + tf(A_0))$$
找到(utf)
目标：找到一个(utf)使得(utf(tf(A)) = A)。
这相当于把上面那个式子倒着推，怎么个倒推法呢？
正着推是已知(A = (A_0, A_1))，求(tf(A) = (tf(A)_0, tf(A)_1))。
倒着推就是已知(tf(A) = (tf(A)_0, tf(A)_1))，求(utf(tf(A)) = A = (A_0, A_1) = (utf(tf(A_0)), utf(tf(A_1))))。
那么根据上面的(tf(A) = (tf(A_0), tf(A_1) + tf(A_0)))，有(tf(A)_0 = tf(A_0), tf(A)_1 = tf(A_0) + tf(A_1))。
所以直接得到(tf(A_0) = tf(A)_0), 两式相减又得到(tf(A_1) = tf(A)_1 - tf(A)_0)。
所以(utf(tf(A)) = A = (A_0, A_1) = (utf(tf(A_0)), utf(tf(A_1)) = (utf(tf(A)_0), utf(tf(A)_1 - tf(A)_0)))
将(tf(A))替换成(A)，得到(utf(A) = (utf(A), utf(A_1) - utf(A_0)))
这就是逆变换(utf)了。
总结
或卷积的FWT：
用FWT解决与卷积
与卷积和或卷积非常类似。
有(C = (A_0*B_0 + A_0*B_1 + A_1 *B_0, A_1*B_1))
定义$$tf(A) = (tf(A_0) + tf(A_1), tf(A_1))$$
类似上面或卷积的证明过程可以证明它。
类似地，$$utf(A) = (utf(A_0) - utf(A_1), utf(A_1))$$
用FWT解决异或卷积
和上面的也很类似，但是异或卷积的式子更复杂一丁点。它是：
证明嘛……和上面的或卷积证明也差不多！
板子
我的异或卷积板子：
ll inc(ll x, ll y){return (x += y) >= P ? x - P : x;}
ll dec(ll x, ll y){return (x -= y) < 0 ? x + P : x;}
void transform(ll *a, int n, bool inv){
for(int l = 2; l <= n; l <<= 1){
int m = l >> 1;
for(ll *p = a; p != a + n; p += l)
for(int i = 0; i < m; i++){
ll t = p[i + m];
p[i + m] = dec(p[i], t);
p[i] = inc(p[i], t);
}
if(inv)
for(int i = 0; i < n; i++)
a[i] = a[i] * inv2 % P;
}
}
异或已经是写起来最长的啦，其他两个都特别短～