FWT (快速沃尔什变换)详解

约定：$F’=FWT(F)$

卷积的问题，事实上就是要构造$F’G’=(FG)’$

$\text{FWT}$涉及的问题，我们看到是二进制位上的or ,and ,xor

但正式来说，是集合幂指数 上的 并 ， 交 ， 对称差

为了说人话，这里就不带入集合幂指数的概念了

一个常识：$\sum_{T\sube S}(-1)^{|T|}=[S=\empty]$

or 和 and 卷积

这两种卷积的本质是相同的，所以只解释$or$卷积

or卷积的本质就是高位前缀和

即:$F’_S=\sum _{T\sube S}F_T$

正确性：

即$\forall S,F’_S \cdot G’_S=(F\cup G)’_S$

左边=

$F’_S \cdot G’_S=\sum _{T\sube S}\sum _{R\sube S}F_T\cdot G_R$

右边=

$(F\cup G)’_S=\sum_{T\sube S}(F \cup G)_S$

$=\sum_{T\sube S}\sum_{A,B,A\cup B=S}F_A\cdot G_B$

$=\sum_{T \sube S}\sum_{R \sube S}F_T \cdot G_R$

卷积实现

其实第一次层循环的意思是枚举子集中和自己不同的位最高是$i$

让$0$向$1$转移即可

1
2
3
4
5
6
7
8
9
10
void FWT(int n,ll *a){
    for(int i=1;i<n;i<<=1) 
        rep(j,i,n-1) if(j&i) s[j]+=s[j^i];
}
void FWT(int n,ll *a){
    for(int i=1;i<n;i<<1)
        for(int l=0;l<n;l+=i*2)
            for(int j=0;j<l+i;++j) 
                s[j+i]+=s[j];
}

Tips:如果要卡常，可以写成类似$\text{FFT}$的形式，因为优化了访问顺序会快一些

实现逆卷积

把上面的加换成减，这是一个类似容斥的东西

但是因为是反解，所以这个过程我么通常称为子集反演

那么每次$0$向$1$的转移意味着多了一个不同的位置

设$F’_S=\sum_{T\sube S}F_T$

实际逆卷积就是$F_S=\sum_{T\sube S}(-1)^{|T\oplus S|} F’_S$

证明如下：

$\Leftrightarrow F_S=\sum_{T\sube S}(-1)^{|T\oplus S|} \sum _{R\in T}F_R$

$\Leftrightarrow F_S=\sum_{T\sube S}F_R\sum _{T\sube R,R\sube S}(-1)^{|S\oplus R|}$

$\Leftrightarrow F_S=\sum_{T\sube S}F_R\sum _{R\sube (S\oplus T)}(-1)^{|R|}$

带入上面所提到的$\sum_{T\sube S}(-1)^{|T|}=[S=\empty]$，成立

1
2
3
4
5
6
7
8
9
10
void FWT(int n,ll *a,int f){
    for(int i=1;i<n;i<<=1) 
        rep(j,i,n-1) if(j&i) s[j]+=f*s[j^i];
}
void FWT(int n,ll *a,int f){
    for(int i=1;i<n;i<<1)
        for(int l=0;l<n;l+=i*2)
            for(int j=0;j<l+i;++j) 
                s[j+i]+=f*s[j];
}

Xor 卷积

这里要用到一个小性质

$|A\cap B|+|A\cap C|\equiv |A\cap (B\bigoplus C)| \pmod 2$

构造$F’_S=\sum_{T}(-1)^{|S\cap T|}F_T$

正确性

即$\forall S,F’_S \cdot G’_S=(F\bigoplus G)’_S$

$F’_S\cdot G’_S=\sum_{T} \sum_{R}(-1)^{|S\cap T|+|S\cap R|}F_T\cdot G_R$

$=\sum _T\sum _R(-1)^{|(T\bigoplus R)\cap S|}F_T\cdot G_R$

显然这个式子与右边相同

卷积实现

考虑和前面相同的方法，枚举二进制位上最高的$1$

之前由于转移是单向的，所以只需要一次加法，这里由于有了系数同时还是双向的转移，所以要格外注意

转移系数也是比较明显的

$0\rightarrow 0 = 1$

$0\rightarrow 1 = 1$

$1\rightarrow 0 = 1$

$1\rightarrow 1 = -1$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void FWT(int n,ll *a){
    for(int i=1;i<n;i<<=1) {
        rep(j,0,n-1) if(i&j) {
            ll t=a[j+i];
            a[j+i]=a[j]-t;
            a[j]=a[j]+t;
        }
    }   
}
void FWT(int n,ll *a){
    for(int i=1;i<n;i<<=1){
        for(int l=0;l<n;l+=i*2) {
            for(int j=l;j<l+i;++j){
                ll t=a[j+i];
                a[j+i]=a[j]-t;
                a[j]+=t;
            }
        }
    }
}

实现逆卷积

考虑再卷一次

$F’’_S=\sum_T\sum_R(-1)^{|S\cap R|+|T\cap R|}F_T$

$=\sum_T \sum_R (-1)^{|(S\bigoplus T)\cap R|}F_T$

$\because \sum_T (-1)^{|S\cap T|}=\sum_{T\sube S}(-1)^{|T|}2^{|U|-|S|}=[S=\empty]2^{|U|-|S|}$(其中$U$是全集)

$\therefore F’’_S=\sum_S2^{|U|}F_S$

所以逆卷积就是再卷一遍，最后除去$n$即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void FWT(int n,ll *a,int f){
    for(int i=1;i<n;i<<=1) {
        rep(j,0,n-1) if(i&j) {
            ll t=a[j+i];
            a[j+i]=a[j]-t;
            a[j]=a[j]+t;
        }
    }   
    if(f==-1) rep(i,0,n-1) a[i]/=n;
}
void FWT(int n,ll *a,int f){
    for(int i=1;i<n;i<<=1){
        for(int l=0;l<n;l+=i*2) {
            for(int j=l;j<l+i;++j){
                ll t=a[j+i];
                a[j+i]=a[j]-t;
                a[j]+=t;
            }
        }
    }
    if(f==-1) for(int i=0;i<n;++i) a[i]/=n;
}

和上面一样的，可以写成类似$\text{FFT}$的形式卡常