「算法」FWT（快速沃尔什变换）

大家好，欢迎来到IT知识分享网。

用途

$FWT$ 用来在 $O(n{\log }_{2}n)$ 的时间内解决形如 $C_k={\sum }_{i\oplus j=k}{A}_i{B}_j$ 的位运算卷积问题。

其中 $\oplus$ 表示 $\mathrm{and},\mathrm{or},\mathrm{xor},\mathrm{nxor}$ 等位运算中的一种。

思路和 $FFT$ 类似，都是先把多项式 $A,B$ 写成类似 点值表示法 的形式，分别记为 $FWT(A)$ 和 $FWT(B)$ ，使得 $FWT(C{)}_i=FWT(A{)}_i\cdot FWT(B{)}_i$ 。

现在按位运算进行分类讨论。

一些符号

这里作一些规定。

1. 每一个序列的长度都是二的整数幂的；
2. 下文中默认位运算的优先级在 $+$ 之前，即会先计算位运算，再计算加法；
3. $(A,B)$ 表示把 $A,B$ 按 $A$ 在前， $B$ 在后的顺序拼接起来组成一个长度为 $|A|+|B|$ 的序列；
4. $A+B$ 表示把两个长度相等的序列 $A,B$ 的每一个对应下标上的数相加，即 $(A+B{)}_i=A_i+B_i$ ，形成的序列长度为 $|A|$ ；
5. $A-B$ 表示把两个长度相等的序列 $A,B$ 的每一个对应下标上的数相减，即 $(A-B{)}_i=A_i-B_i$ ，形成的序列长度为 $|A|$ 。

不同位运算下的形式

与运算

先给出一个结论：$$FWT(A{)}_i=\sum _{i\mathrm{and}j=i}{A}_j$$

证明：

$$\begin{array}{rl}& \forall i\in [0,|A|)\cup Z,\text{都有}\\ & FWT(A{)}_i\times FWT(B{)}_i=FWT(C{)}_i\\ & ⟸\left(\sum _{j\mathrm{and}i=i}{A}_j\right)\left(\sum _{k\mathrm{and}i=i}{B}_k\right)=\sum _{j\mathrm{and}k\mathrm{and}i=i}{A}_j{B}_k\\ & ⟸\{\begin{array}{ll}j\mathrm{and}i& =i,\\ k\mathrm{and}i& =i\end{array}\text{等价于}j\mathrm{and}k\mathrm{and}i=i\end{array}$$

得证。

根据这个结论直接做是 $O\left(n^2\right)$ 的。

考虑像 $FFT$ 那样，把序列 $A$ 二分为序列 $A_0,A_1$ ，再根据 $FWT(A_0),FWT(A_1)$ 算出 $FWT(A)$ ，这样就可以做到 $O(n{\log }_{2}n)$ 了。

发现如果把序列 $A$ 的下标用 二进制 表示， $A_0$ 是由下标中第 $1+{\log }_2|A|$ 位（也就是当前的最高位）为 $0$ 的元素组成的， $A_1$ 中的元素的最高位则为 $1$ 。

因为 $\mathrm{and}$ 运算有这样的性质：除了 $1\mathrm{and}1=1$ ，其它 $0\mathrm{and}1,0\mathrm{and}0,1\mathrm{and}0$ 的值都为 $0$ 。即 $A_1$ 会贡献到 $A_0$ ，因此可以得到：

$$FWT(A)=(FWT(A_0)+FWT(A_1),FWT(A_1))$$

那反演就容易了：

$$UFWT(A)=(UFWT(A_0)-UFWT(A_1),UFWT(A_1))$$

代码

inline void fwt_and(int f[],int opt) { 
    for(int i=2,j=1;i<=m;j=i,i<<=1) for(int t=0;t<m;t+=i) for(int k=t;k<j+t;++k) f[k]+=f[k+j]*opt; } 

或运算

同样的，先给出结论：$$FWT(A{)}_i=\sum _{i\mathrm{or}j=i}{A}_j$$

证明是类似的，就不写了。结论也是类似的：

$$\begin{array}{rl}FWT(A)& =(FWT(A_0),FWT(A_0)+FWT(A_1))\\ UFWT(A)& =(UFWT(A_0),UFWT(A_1)-UFWT(A_0))\end{array}$$

代码

inline void fwt_or(int f[],int opt) { 
    for(int i=2,j=1;i<=m;j=i,i<<=1) for(int t=0;t<m;t+=i) for(int k=t;k<j+t;++k) f[k+j]+=f[k]*opt; } 

异或运算

注意这个结论长得不一样（ $\mathrm{popcount}(x)$ 表示把 $x$ 写成二进制形式有多少位上的数为 $1$ ）：

$$FWT(A{)}_i=\sum _{2\mid \mathrm{popcount}(i\mathrm{and}j)}{A}_j-\sum _{2\nmid \mathrm{popcount}(i\mathrm{and}j)}{A}_j$$

注意不是直接仿照 与运算 、 或运算 的形式写成

$$FWT(A{)}_i=\sum _{i\mathrm{xor}j=i}{A}_j$$

为了方便起见，定义运算符 $\otimes$ ： $x\otimes y=\mathrm{popcount}(x\mathrm{and}y)\mathrm{mod}2$ 。

那么这个运算符是满足以下性质的：

$$(x\otimes y)\mathrm{xor}(x\otimes z)=x\otimes (y\mathrm{xor}z)$$

证明：

令 $a=\mathrm{popcount}(x\mathrm{and}y\mathrm{and}z),b=\mathrm{popcount}(x\mathrm{xor}y)-a,c=\mathrm{popcount}(y\mathrm{xor}z)-a$ 。

那么

$$\begin{array}{rl}& \mathrm{popcount}(x\mathrm{and}(y\mathrm{xor}z))\\ & =b+c\\ & =\mathrm{popcount}(x\mathrm{xor}y)+\mathrm{popcount}(x\mathrm{xor}z)-2a\\ & \therefore x\otimes (y\mathrm{xor}z)\\ & =(x\otimes y+x\otimes z)\mathrm{mod}2\\ & =(x\otimes y)\mathrm{xor}(x\otimes z)\end{array}$$

得证。

然后现在来证明结论：

证明：

$$\begin{array}{rl}& FWT(A{)}_i\cdot FWT(B{)}_i\\ =& \left(\sum _{j\otimes i=0}{A}_j-\sum _{j\otimes i=1}{A}_j\right)\left(\sum _{k\otimes i=0}{B}_k-\sum _{k\otimes i=1}{B}_k\right)\\ =& \left(\sum _{j\otimes i=0}{A}_j\right)\left(\sum _{k\otimes i=0}{B}_k\right)-\left(\sum _{j\otimes i=0}{A}_j\right)\left(\sum _{k\otimes i=1}{B}_k\right)-\\ & \left(\sum _{j\otimes i=1}{A}_j\right)\left(\sum _{k\otimes i=0}{B}_k\right)+\left(\sum _{j\otimes i=1}{A}_j\right)\left(\sum _{k\otimes i=1}{B}_k\right)\\ =& \sum _{i\otimes (j\mathrm{xor}k)=0}{A}_j{B}_k-\sum _{i\otimes (j\mathrm{xor}k)=1}{A}_j{B}_k\\ =& FWT(C{)}_i\end{array}$$

得证。

因此可以得出：

$$\begin{array}{rl}FWT(A)& =(FWT(A_0)+FWT(A_1),FWT(A_0)-FWT(A_1))\\ UFWT(A)& =\left(\frac{UFWT(A_1)+UFWT(A_0)}{2},\frac{UFWT(A_1)-UFWT(A_0)}{2}\right)\end{array}$$

代码

这份代码里面的 $FWT$ 是在取模意义下的，不用取模的话修改一下就好了。

 inline int plus(int x,int y) { 
    x+=y; if(x>=P) x-=P; else if(x<0) x+=P; return x; } inline void fwt_xor(int f[],int opt) { 
    for(int i=2,j=1,x,y;i<=m;j=i,i<<=1) for(int t=0;t<m;t+=i) for(int k=t;k<t+j;++k) { 
    x=plus(f[k],f[k+j]),y=plus(f[k],P-f[k+j]); opt>0? f[k]=x,f[k+j]=y : (f[k]=inv2*x%P,f[k+j]=inv2*y%P) ; } } 

同或运算

同或运算下的 $FWT$ 与异或的类似。

先给出结论： $$FWT(A{)}_i=\sum _{2\mid \mathrm{popcount}(i\mathrm{or}j)}{A}_j-\sum _{2\nmid \mathrm{popcount}(i\mathrm{or}j)}{A}_j$$

可以得到

$$\begin{array}{rl}FWT(A)& =(FWT(A_0)-FWT(A_1),FWT(A_0)+FWT(A_1))\\ UFWT(A)& =\left(\frac{UFWT(A_1)-UFWT(A_0)}{2},\frac{UFWT(A_1)+UFWT(A_0)}{2}\right)\end{array}$$

在异或运算的代码上改一下可以了。

例题

P4717

P4717 【模板】快速莫比乌斯/沃尔什变换 (FMT/FWT)

#include<cstdio> #include<cstring> using namespace std; #define fo(i,l,r) for(i=l;i<r;++i) #define N  const int P=; const long long inv2=; int m,a[N],b[N],c[N],A[N],B[N]; inline void add(int &x,int y) { 
    x+=y; if(x>=P) x-=P; else if(x<0) x+=P; } inline int plus(int x,int y) { 
    x+=y; if(x>=P) x-=P; else if(x<0) x+=P; return x; } inline void fwt_or(int f[],int opt) { 
    for(int i=2,j=1;i<=m;j=i,i<<=1) for(int t=0;t<m;t+=i) for(int k=t;k<j+t;++k) add(f[k+j],f[k]*opt); } inline void fwt_and(int f[],int opt) { 
    for(int i=2,j=1;i<=m;j=i,i<<=1) for(int t=0;t<m;t+=i) for(int k=t;k<j+t;++k) add(f[k],f[k+j]*opt); } inline void fwt_xor(int f[],int opt) { 
    for(int i=2,j=1,x,y;i<=m;j=i,i<<=1) for(int t=0;t<m;t+=i) for(int k=t;k<t+j;++k) { 
    x=plus(f[k],f[k+j]),y=plus(f[k],P-f[k+j]); opt>0? f[k]=x,f[k+j]=y : (f[k]=inv2*x%P,f[k+j]=inv2*y%P) ; } } int main() { 
    freopen("fwt.in","r",stdin); freopen("fwt.out","w",stdout); int n,i; scanf("%d",&n),m=1<<n; fo(i,0,m) scanf("%d",a+i); fo(i,0,m) scanf("%d",b+i); fo(i,0,m) A[i]=a[i],B[i]=b[i]; fwt_or(a,1),fwt_or(b,1); fo(i,0,m) c[i]=1LL*a[i]*b[i]%P; fwt_or(c,-1); fo(i,0,m) printf("%d ",c[i]);puts(""); memcpy(a,A,sizeof a),memcpy(b,B,sizeof b); fwt_and(a,1),fwt_and(b,1); fo(i,0,m) c[i]=1LL*a[i]*b[i]%P; fwt_and(c,-1); fo(i,0,m) printf("%d ",c[i]);puts(""); memcpy(a,A,sizeof a),memcpy(b,B,sizeof b); fwt_xor(a,1),fwt_xor(b,1); fo(i,0,m) c[i]=1LL*a[i]*b[i]%P; fwt_xor(c,-1); fo(i,0,m) printf("%d ",c[i]);puts(""); return 0; }