快速沃尔什变换是用于解决位运算卷积的一种变换。
若无特殊说明，沃尔什变换一般特指异或卷积，而莫比乌斯变换可以指任意位运算卷积，在下文中为了方便统称为沃尔什变换。
又一个神人构造出的算法。
一些记号
定义$A,B$是两个向量。
向量的维数是$n$，$n$为$2$的整数次幂。若不满足，高位补零。
定义记号：
- $A\pm B=(A(0)\pm B(0),A(1)\pm B(1),\ldots,A(n-1)\pm B(n-1))$
- $A\cdot B=(A(0)\cdot B(0),A(1)\cdot B(1),\ldots,A(n-1)\cdot B(n-1))$
- $A\times B=(\sum\limits_{i+j=0}A(i)\cdot B(j),\sum\limits_{i+j=1}A(i)\cdot B(j),\ldots,\sum\limits_{i+j=n-1}A(i)\cdot B(j))$
异或卷积
定义$\times$卷积为$\oplus$异或卷积：
$A\oplus B=(\sum\limits_{i\oplus j=0}A(i)\cdot B(j),\sum\limits_{i\oplus j=1}A(i)\cdot B(j),\ldots,\sum\limits_{i\oplus j=n-1}A(i)\cdot B(j))$
显然，异或运算满足交换律与结合律。
正向变换
定义$fwt(A)$为向量$A$经过正向变换后得到的向量，若$A_0$为$A$的前$2^{n-1}$项（即项的最高位为$0$），$A_1$为后$2^{n-1}$项（即项的最高位为$1$），记$A=(A_0,A_1)$。
picks告诉我们$fwt(A)$如此定义：
性质一：$fwt(A\pm B)=fwt(A)\pm fwt(B)$
证明：$fwt(A)$每维都是$A$中元素的线性组合，故加法满足分配率。
性质二：$fwt(A\oplus B)=fwt(A)\cdot fwt(B)$
证明：
下面使用数学归纳法进行证明。
首先，$n=1$时显然成立。
若该性质对于$\frac n2$的向量均成立，则：
逆向变换
在计算完毕异或卷积后，需要通过逆向变换得到原来的值。
定义$ufwt(A)$为$A$经过逆变换后得到的向量。
构造$ufwt(A)$这样定义：
则：
通过数学归纳法同样可以证明其正确性。
这样我们就可以在$O(n\log n)$的时间内进行正逆变换，在$O(n)$时间内计算异或卷积了。
并卷积
定义$\times$卷积为$\&$并卷积：
$A\& B=(\sum\limits_{i\& j=0}A(i)\cdot B(j),\sum\limits_{i\& j=1}A(i)\cdot B(j),\ldots,\sum\limits_{i\& j=n-1}A(i)\cdot B(j))$
显然，并运算满足交换律与结合律。
正向变换
定义$fwt(A)$为向量$A$经过正向变换后得到的向量，若$A_0$为$A$的前$2^{n-1}$项（即项的最高位为$0$），$A_1$为后$2^{n-1}$项（即项的最高位为$1$），记$A=(A_0,A_1)$。
Candy?告诉我们$fwt(A)$如此定义：
性质一：$fwt(A\pm B)=fwt(A)\pm fwt(B)$
证明：$fwt(A)$每维都是$A$中元素的线性组合，故加法满足分配率。
性质二：$fwt(A\& B)=fwt(A)\cdot fwt(B)$
证明：
下面使用数学归纳法进行证明。
首先，$n=1$时显然成立。
若该性质对于$\frac n2$的向量均成立，则：
逆向变换
在计算完毕并卷积后，需要通过逆向变换得到原来的值。
定义$ufwt(A)$为$A$经过逆变换后得到的向量。
构造$ufwt(A)$这样定义：
则：
通过数学归纳法同样可以证明其正确性。
这样我们就可以在$O(n\log n)$的时间内进行正逆变换，在$O(n)$时间内计算并卷积了。
或卷积
定义$\times$卷积为$|$或卷积：
$A| B=(\sum\limits_{i| j=0}A(i)\cdot B(j),\sum\limits_{i| j=1}A(i)\cdot B(j),\ldots,\sum\limits_{i| j=n-1}A(i)\cdot B(j))$
显然，或运算满足交换律与结合律。
正向变换
定义$fwt(A)$为向量$A$经过正向变换后得到的向量，若$A_0$为$A$的前$2^{n-1}$项（即项的最高位为$0$），$A_1$为后$2^{n-1}$项（即项的最高位为$1$），记$A=(A_0,A_1)$。
Candy?告诉我们$fwt(A)$如此定义：
其正确性证明与并卷积类似，不再赘述。
逆向变换
在计算完毕或卷积后，需要通过逆向变换得到原来的值。
定义$ufwt(A)$为$A$经过逆变换后得到的向量。
构造$ufwt(A)$这样定义：
其正确性证明与并卷积类似，不再赘述。
代码实现
此处仅给出异或卷积的代码，并卷积与或卷积类似，修改一点代码即可。
递归实现
1 | const int mod=10007,inv2=5004; |
伪·蝴蝶变换
众所周知，递归实现效率很低，不妨使用伪·螺旋剑伪·蝴蝶变换。
注意这里的蝴蝶变换没有位置的交换，只需要改掉对应位置的值即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25const int mod=10007,inv2=5004;
struct FastWalshTransform {
int n;
void init(int n) {
this->n=n;
}
void transform(int *a,int mul) {
for(int len=2; len<=n; len<<=1) {
int mid=len>>1;
for(int *p=a; p!=a+n; p+=len)
for(int i=0; i<mid; i++) {
LL x=p[i],y=p[mid+i];
p[i]=(x+y)*mul%mod;
p[mid+i]=(x-y+mod)*mul%mod;
}
}
}
void fwt(int *a) {
transform(a,1);
}
void ufwt(int *a) {
transform(a,inv2);
}
} wtf;
并卷积与或卷积的另类推导
此处以或卷积举例。
定义$\times$卷积为$|$或卷积：
$A| B=(\sum\limits_{i| j=0}A(i)\cdot B(j),\sum\limits_{i| j=1}A(i)\cdot B(j),\ldots,\sum\limits_{i| j=n-1}A(i)\cdot B(j))$
令$\hat A$为$A$进行莫比乌斯变换后的结果。
定义$\hat A(x)=\sum\limits_{S\subseteq x}A(S)$。
观察卷积：
成功变成点积。
其实本质和上面的推导是一样的。
代码也很好写：1
2
3
4
5
6
7
8
9
10
11
12
13
14struct FastMobiusTransform {
int n,m;
void init(int n) {
this->n=n;
m=1<<n;
}
void transform(int *a,int mul) {
for(int i=0; i<n; i++)
for(int j=0; j<m; j++)
if(j&(1<<i))a[j]+=a[j^(1<<i)]*mul;
}
void fmt(int *a) {transform(a,1);}
void ufmt(int *a) {transform(a,-1);}
} mtf;
