$\huge 简介$
$FWT$ 是用于解决对下表进行位运算卷积问题的方法
更确切地说,给定两个多项式 $A$ 和 $B$ ,求多项式 $C$
$$c_i = \sum _{i=j⊕k}a_jb_k$$
其中, ⊕表示任意位运算符号(与(&),或(|),异或(^)之一)
与 $FFT$ 类似,$FWT$ 先将 $A,B$ 转换成 $FWT$ 的形式,相乘后再用逆变换转换成多项式形式。
以下会对三种位运算符号分别推导。
$\huge 或$
要求
$$c_i = \sum _{i=j\|k}a_jb_k$$
若 $FWT[a]_i$ 表示为 $a$ 转成 $FWT$ 形势下的第 $i$ 位
构造 $$FWT[a]_i = \sum_{j\|i=i}a_j$$
则
$$FWT[a]_i \times FWT[b]_i = \left( \sum_{j\|i=i}a_j \right) \left( \sum_{k\|i=i}b_k\right)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$=\sum_{j|i=i} \sum_{k|i=i}a_jb_k$$
$$=\sum_{(j|k)|i=i}a_jb_k\ \ $$
$$=FWT[c]_i\ \ \ \ \ $$
且就是说可以通过按位相乘的方式,以 $O(n)$ 的复杂度解决两个 $FWT$ 的卷积。
接下来要解决的是如何求一个多项式的 $FWT$ 。
采用分治策略,每一次将多项式分为左半边 $a_0$ 和右半边 $a_1$ 。
其一定满足左半边下标最高位为 $0$ ,右半边下标最高位为 $1$ 。
如图所示,先分别计算两边的值,由于 $0|1=1$ ,所以最终合并的结果为
$$FWT[a] = merge(FWT[a_0],FWT[a_0]+FWT[a_1])$$
其中 $+$ 表示按位相加。
易得反演递推式:
$$UFWT[a] = merge(UFWT[a_0],UFWT[a_1] - UFWT[a_0])$$
$实现$
void OR(int *a, int x) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j ++ )
a[i + j + k] = a[i + j + k] + a[i + j] * x;
}
$\Huge 与$
要求
$$c_i = \sum_{j\&k=i} a_jb_k $$
构造 $$FWT[a]_i = \sum _{j\&i=i} a_j$$
则
$$FWT[a]_i \times FWT[b]_i = \left( \sum_{j\&i=i}a_j \right) \left( \sum_{k\&i=i}b_k\right)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
$$=\sum_{j\&i=i} \sum_{k\&i=i}a_jb_k$$
$$=\sum_{(j\&k)\&i=i}a_jb_k\ \ $$
$$=FWT[c]_i\ \ \ \ \ \ \ \ $$
同上或的递推式,由于 $0\&1=0$ ,所以递推式为
$$FWT[a] = merge(FWT[a_0]+FWT[a_1],FWT[a_1])$$
$$UFWT[a] = merge(UFWT[a_0]-UFWT[a_1],UFWT[a_1])$$
$实现$
void AND(int *a, int x) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j ++ )
a[i + j] = a[i + j] + a[i + j + k] * x;
}
$\Huge 异或$
定义 $x⊗y=popcount(x\&y) \bmod 2$,其中 $popcount$ 表示二进制下 $1$ 的个数
满足 $(i⊗j) \textsf{xor} (i⊗k) = i⊗(j \ \textsf{xor} \ k)$
构造 $$fwt[a]_i=\sum_{i⊗j=0}a_j-\sum_{i⊗j=1}a_j$$
则有
$$fwt[a]_i \times fwt[b]_i = \left( \sum_{i⊗j=0}a_j-\sum_{i⊗j=1}a_j \right) \left( \sum_{i⊗k=0}b_k-\sum_{i⊗k=1}b_k \right)\ \ \ \ \ \ \ \ \ \ $$
$$=\sum_{i⊗(j\ \textsf{xor}\ k)=0}a_jb_k - \sum_{i⊗(j\ \textsf{xor} \ k)=1}a_jb_k$$
$$=fwt[c]_i\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $$
根据定义得出
$$FWT[a] = merge(FWT[a_0]+FWT[a_1],FWT[a_0]-FWT[a_1])$$
$$UFWT[a] = merge(\frac{UFWT[a_0]+UFWT[a_1]}{2},\frac{UFWT[a_0]-UFWT[a_1]}{2})$$
$实现$
void XOR(int *a, int x) {
for (int o = 2, k = 1; o <= n; o <<= 1, k <<= 1)
for (int i = 0; i < n; i += o)
for (int j = 0; j < k; j ++ ) {
a[i + j] = a[i + j] + a[i + j + k];
a[i + j + k] = a[i + j] - a[i + j + k] - a[i + j + k];
a[i + j] = a[i + j] * x, a[i + j + k] = a[i + j + k] * x;
}
}