FWT (快速沃尔什变换)详解 以及 K进制FWT

Posted on Edited on In

FWT (快速沃尔什变换)详解 以及 K进制FWT

约定：\(F'=FWT(F)\)

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

我们常见的卷积，是二进制位上的or ,and ,xor

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

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

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

or 和 and 卷积

ps: 虽然这两个并不是 \(\text{FWT}\)，应该叫 \(\text{FMT}\) (快速莫比乌斯变换)，但是由于常用的是这3个，所以放到一起。

这两种卷积的本质是相同的，所以只解释 \(or\) 卷积。

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

即: \(F'_S=\sum _{T\subseteq S}F_T\)

正确性：

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

左边=

\(F'_S \cdot G'_S=\sum _{T\subseteq S}\sum _{R\subseteq S}F_T\cdot G_R\)

右边=

\[ \begin{aligned} (F\cup G)'_S&=\sum_{T\subseteq S}(F \cup G)_S \\ &=\sum_{T\subseteq S}\sum_{A,B,A\cup B=S}F_A\cdot G_B \\ &=\sum_{T \subseteq S}\sum_{R \subseteq S}F_T \cdot G_R \end{aligned} \]


卷积实现

其实第一次层循环的意思是枚举子集中和自己不同的位最高是 \(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\subseteq S}F_T\)。

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

证明如下：

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

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

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

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

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];
}



应用 : 子集卷积 ( 可以看luogu )

问题描述： 给定 \(F_S,G_T\)，求出 \(H_{R}=\sum_{S\cup T=R,S\cap T=\emptyset}F_S\cdot G_T\)，设有 \(2^n\)个元素。

我们知道直接枚举的复杂度为 \(O(3^n)\)。

直接应用 or 卷积无法保证 \(S\cap T=\emptyset\)，但是可以再记录一个占位数量，即把 \(F,G\) 按照每一位包含 1 的数量分开成 \(n+1\) 部分，卷积完成之后应该满足1的个数恰好为两者之和，否则清空。

需要 \(n\) 次卷积，\(n^2\) 次转移，因此复杂度为 \(O(n^22^n)\)，在渐进意义上更优于 \(O(3^n)\)。

Xor 卷积

这里要用到一个小性质

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

思路介绍：

我们是要构造一个 \(F_S\rightarrow G_T\) 的变换，使得该变换满足Xor的性质，且能在较优的时间复杂度内完成，并且能够在较优的时间内完成反演。

由于上面的这条式子，考虑可以构造 \(F'_S=\sum_{T}(-1)^{|S\cap T|}F_T\)，这样 \((-1)^k\) 的系数在 \(\mod 2\) 意义下可以抵消

正确性

即 \(\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(~j&i) {
            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\subseteq S}(-1)^{|T|}2^{|U|-|S|}=[S=\emptyset]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(~j&i) {
            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}\)的形式卡常

\[ \ \]

\[ \ \]

拓展 K - FWT

实际上学习了这个拓展能让你更好地理解 \(\text{FWT}\)。

不妨考虑 \(n\) 个维度的情况，每个维度是一个 \(0,1,\cdots k-1\) 中的数。

由于 \(k\) 进制下不好用集合描述，因此考虑用一个向量 \(\vec{V}=\lbrace V_0,V_1,\cdots,V_{n-1}\rbrace,V_i\in[0,k-1]\) 表示。

一个多项式可以具象地用 \(0,1,\cdots,k^n-1\) 这个\(k^n\) 个位置上的系数表示。

\(\text{and,or}\) 卷积在 \(k\) 进制下可以拓展为按位取 \(\min,\max\)，这个直接累前缀和就可以了，不作赘述。

而 \(k\) 进制下的 \(\text{xor}\) 可以扩展为两个向量列的取模加法。

\(\vec{A}+\vec{B}=\vec{C},C_i=(A_i+B_i)\bmod k\)

也可以描述为不进位的 \(k\) 进制数加法。

其实用 \(\text{K-FWT}\) 称呼这个似乎不是很形象，更好的可以称之为 \(\text{n-DFT}\)。

也就是说 \(\text{K-FWT}\) 实际上就是在 \(n\) 个维度上分别做大小为 \(k\) 的循环卷积，使用一种结合 \(\text{FWT-DFT}\) 的方法(因此需要用到 \(k\) 次单位根 \(\omega_k\) )。

卷积构造

原多项式 \(F\) 向卷积多项式\(F'\)的转换系数为 \([x^A]F\rightarrow [x^B]F':\omega_k^{A\cdot B}\)。

其中 \(A\cdot B\) 为向量内积，即 \(\sum A_i\cdot B_i\)。

从中也可以很好地看到 \(\text{xor}\) 卷积的影子。

实现方法上，可以依次枚举 \(0,1,\cdots,n-1\) 每一位，将除了这一位上都相同的数取出来。

按照这一位上的值做一次 \(\text{DFT}\)。

需要 \(n\) 位枚举，每次枚举需要做 \(k^{n-1}\) 次 \(k^2\) 的 \(\text{DFT}\)，因而复杂度为 \(O(nk^{n+1})\)。

对于 \(k\) 比较大的情况，如果 \(k=2^t\) 可以直接用 \(\text{FFT/NTT}\)，否则还可以参考这个

可以优化到 \(O(nk^n\log k)\) 。

逆卷积

当然是换成 \(\text{IDFT}\)，最后全部除掉 \(k^n\)。

正确性上，如果你对于 \(\text{IDFT}\) 的原理(单位根反演) 有所了解，就能发现，只有所有位置上都相同的情况才会转移出 \(k^n\) 的系数。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int w[20]; // 单位根的幂次
void K_FWT(int *F,int n,int f){ // 这个n实际上是上面叙述中的n^k
    static int t[20];
    for(int i=1;i<n;i*=k){
        for(int l=0;l<n;l+=i*k){
            for(int j=l;j<l+i;++j){
                for(int a=0;a<k;++a) 
                    for(int b=t[a]=0;b<k;++b) 
                        t[a]=(t[a]+1ll*F[j+b*i]%P*w[b*(k+f*a)%k])%P;
                for(reg int a=0;a<k;++a) F[j+a*i]=t[a];
            }
        }
    }
	if(f==-1) {
        ll base=qpow(n);
        rep(i,0,n-1) F[i]=F[i]*base%P;
    }
}