快速沃尔什变换

SE の摆烂窝 / 2023-08-21 / 原文

FWT 用于解决对下标进行位运算的卷积问题。

及求 \(\displaystyle c_i=\sum_{j\oplus k=i}a_jb_k\)，其中 \(\oplus\) 是二元位运算的一种。

板子

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

对 \(\oplus=\operatorname{or},\operatorname{and},\operatorname{xor}\) 分别求出 \(c\).

记对序列 \(a\) 进行 FWT 后的序列为 \(fwt[a]\).

我们希望能够做到 \(a\rightarrow fwt[a]\)，\(b\rightarrow fwt[b]\)，\(fwt[c]\rightarrow c\) 的时间都是 \(O(n\log n)\)，\(fwt[c]=fwt[a]\cdot fwt[b]\) 这部分的时间是 \(O(n)\) 的。

或

此时 \(\displaystyle c_i=\sum_{j|k=i}a_jb_k\).

有 \(j|i=i,k|i=i\rightarrow (j|k)|i=i\).

构造 \(\displaystyle fwt[a]_i=\sum_{j|i=i}a_j\).

那么

\[fwt[a]\times fwt[b]=\sum_{j|i=i}\sum_{k|i=i}a_jb_k \]

\[=\sum_{(j|k)|i=i}a_ib_k=fwt[c] \]

FWT

现在思考 \(a\rightarrow fwt[a]\) 的过程。

\[fwt[a]_i=\sum_{j|i=i}a_j \]

把当前区间分为两部分，记为 \(A_0\) 和 \(A_1\)，它们在最高二进制位的值分别为 \(0,1\).

发现 \(A_0\) 的子集即其本身，\(A_1\) 的子集是它本身与最高位为 \(0\) 的子集，也就是

\[fwt[a]=\operatorname{merge}(fwt[A_0],fwt[A_0]+fwt[A_1]) \]

\(\operatorname{merge}\) 表示拼接，\(+\) 表示对应二进制位相加。

这样时间复杂度为 \(O(n\log n)\).

IFWT

怎么反演使得 \(fwt[a]\rightarrow a\)？

已知 \(A_0=fwt[A_0]\)，\(A_1=fwt[A_0]+fwt[A_1]\)，容易得到

\[ifwt[a']=\operatorname{merge}(ifwt[A_0'],ifwt[A_1']-ifwt[A_0']) \]

code

将 \(x=1/-1\) 代入即可，中间做一遍点积。

void OR(int *a,int x){
	for(int p=2,k=1;p<=n;p<<=1,k<<=1)
		for(int i=0;i<n;i+=p)
			for(int j=0;j<k;j++)
				a[i+j+k]+=a[i+j]*x;
}

且

与或运算十分相似，构造 \(\displaystyle fwt[a]_i=\sum_{j\And i=i}a_i\).

FWT/IFWT

\[fwt[a]=\operatorname{merge}(fwt[A_0]+fwt[A_1],fwt[A_1]) \]

\[ifwt[a']=\operatorname{merge}(ifwt[A_0']-ifwt[A_1'],fwt[A_1']) \]

code

void AND(int *a,int x){
	for(int p=2,k=1;p<=n;p<<=1,k<<=1)
		for(int i=0;i<n;i+=p)
			for(int j=0;j<k;j++)
				a[i+j]+=a[i+j+k]*x;
}

异或

构造

定义 \(x\oplus y=\operatorname{popcount}(x\And y)\operatorname{mod}2\).

有 \((i\oplus j)\operatorname{xor}(i\oplus k)=i\oplus(j\operatorname{xor}k)\).

构造 \(\displaystyle fwt[a]_i=\sum_{i\oplus j=0}a_j-\sum_{i\oplus j=1}a_j\).

那么

\[fwt[a]\times fwt[b] \]

\[=\Bigg(\sum_{i\oplus j=0}a_j\sum_{i\oplus k=0}b_k\Bigg)-\Bigg(\sum_{i\oplus j=0}a_j\sum_{i\oplus k=1}b_k\Bigg)-\Bigg(\sum_{i\oplus j=1}a_j\sum_{i\oplus k=0}b_k\Bigg)+\Bigg(\sum_{i\oplus j=1}a_j\sum_{i\oplus k=1}b_k\Bigg) \]

\[=\sum_{i\oplus(j\operatorname{xor}k)=0}a_jb_k-\sum_{i\oplus(j\operatorname{xor}k)=1}a_jb_k \]

\[=fwt[c] \]