隐藏
快速沃尔什变换及快速莫比乌斯变换学习笔记 | Bill Yang's Blog
0%

快速沃尔什变换及快速莫比乌斯变换学习笔记

快速沃尔什变换是用于解决位运算卷积的一种变换。
若无特殊说明,沃尔什变换一般特指异或卷积,而莫比乌斯变换可以指任意位运算卷积,在下文中为了方便统称为沃尔什变换。
又一个神人构造出的算法。

一些记号

定义$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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int mod=10007,inv2=5004;

struct FastWalshTransform {
int n;
void init(int n) {
this->n=n;
}
void transform(int *a,int len,int mul) {
if(len==1)return;
int mid=len>>1;
transform(a,mid,mul);
transform(a+mid,mid,mul);
for(int i=0; i<mid; i++) {
LL x=a[i],y=a[mid+i];
a[i]=(x+y)*mul%mod;
a[mid+i]=(x-y+mod)*mul%mod;
}
}
void fwt(int *a) {
transform(a,n,1);
}
void ufwt(int *a) {
transform(a,n,inv2);
}
} wtf;

伪·蝴蝶变换

众所周知,递归实现效率很低,不妨使用伪·螺旋剑伪·蝴蝶变换。

注意这里的蝴蝶变换没有位置的交换,只需要改掉对应位置的值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const 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
14
struct 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;

参考资料

姥爷们赏瓶冰阔落吧~