FWT 快速沃尔什变换

FWT 快速沃尔什变换

对于整数数组进行位运算卷积的快速计算方式，和 FFT 类似的时间复杂度 \(O(n\log n)\)

---

引入

位运算卷积：\(C_i=\sum\limits_{i=j\otimes k} A_jB_k\) ，其中 $\otimes $ 表示某种位运算操作

正变换：通过 \(A,B\) 序列计算 \(f(A),f(B)\) ，然后进行运算 \(f(C)=f(A)\cdot f(B)\)

逆变换：通过 \(f(C)\) 得到原序列 \(C\)

定义 \(f\) 函数的原则是需要满足 \(f(A)=f(B)\cdot f(C)\)

---

或运算

设 \(k=i\cup j\) ，那么 \(i,j\) 的二进制位为 \(1\) 的位置一定也是 \(k\) 的二进制为 \(1\) 的位置的子集

定义 \(A=a_0,a_1,\cdots a_n\) 表示序列 \(A\) 的多项式函数的系数，\(f(A)_i=\sum\limits_{i=i\cup j}A_j\) 则表示 \(j\) 满足二进制中 \(1\) 为 \(i\) 的子集

检验：

\[f(B)_i\cdot f(C)_i=\left(\sum\limits_{i=i\cup j}B_j\right)\cdot \left(\sum\limits_{i=i\cup k}C_k\right)=\sum\limits_{i=i\cup j}\sum\limits_{i=i\cup k}A_jB_k\\ =\sum\limits_{i=i\cup (j\cup k)}A_jB_k=f(c)_i \]

枚举的时间复杂度是 \(O(n^2)\) ，可以通过分治优化到 \(O(n\log n)\)

对形式化的多项式 \(A(x)\) 而言，设它的最高次为 \(2^n\) ，将其拆分为 \(A_0,A_1\) 两个部分，最高次都为 \(2^{n-1}\)

有关或运算卷积的正变换计算可以被表示为：

\[f(A)=merge\left[f(A_0),f(A_0)+f(A_1)\right] \]

因为前半部分的 \(A_0\) 一定不包含 \(A_1\) 的最高位 \(1\) ，所以 \(f(A)\) 的前半部分只与 \(f(A_0)\) 有关

\(merge\) 操作相当于把两个多项式直接连接起来

同样的有逆变换：

\[f^{-1}(A)=merge\left[f^{-1}(A_0),f(A_1)^{-1}-f^{-1}(A_0)\right] \]

采用迭代的方式，集成正逆变换

void FWTOR(LL a[],int op){for (int d=2;d<=(1<<m);d<<=1){//枚举分块数int k=d>>1;//分治for (int i=0;i<(1<<m);i+=d){for (int j=0;j<k;j++){//块内运算(a[i+j+k]+=a[i+j]*op)%=mod;}}}
}

---

与运算

类比或运算可以得到相应运算：

\[f(A)=merge\left[f(A_0)+f(A_1),f(A_0)\right]\\ f^{-1}(A)=merge\left[f^{-1}(A_0)-f^{-1}(A_0),f(A_1)\right] \]

void FWTAND(LL a[],int op){for (int d=2;d<=(1<<m);d<<=1){int k=d>>1;for (int i=0;i<(1<<m);i+=d){for (int j=0;j<k;j++){(a[i+j]+=a[i+j+k]*op)%=mod;}}}
}

---

异或运算

定义 \(x\circ y=\mathrm{popcnt}(x\cap y)\ (\mathrm{mod}\ 2)\) 表示 \(x\cap y\) 中二进制 \(1\) 的个数，所以有 \((x\circ y)\mathrm{xor}(x\circ z)=x\circ(y\ \mathrm{xor}\ z)\)

设 \(f(A)_i=\sum\limits_{i\circ j=0}A_j-\sum\limits_{i\circ j=1}A_j\) ，检验：

\[f(B)_i\cdot f(C)_i=\left(\sum\limits_{i\circ j=0}B_j -\sum\limits_{i\circ j=1}B_j\right)\left(\sum\limits_{i\circ k=0}C_k -\sum\limits_{i\circ k=1}C_k\right)\\ =\left(\sum\limits_{i\circ j=0}B_j \sum\limits_{i\circ k=0}C_k+\sum\limits_{i\circ j=1}B_j \sum\limits_{i\circ k=1}C_k\right)-\left(\sum\limits_{i\circ j=0}B_j \sum\limits_{i\circ k=1}C_k+\sum\limits_{i\circ j=1}B_j \sum\limits_{i\circ k=0}C_k\right)\\ =\sum\limits_{(j\ \mathrm{xor}\ k)\circ i=0}B_jC_k-\sum\limits_{(j\ \mathrm{xor}\ k)\circ i=1}B_jC_k=f(c)_i \]

正逆变换计算：

\[f(A)=merge\left[ f(A_0)+f(A_1),f(A_0)-f(A_1) \right]\\ f^{-1}(A)=merge\left[ \frac{f^{-1}(A_0)+f^{-1}(A_1)}{2},\frac{f^{-1}(A_0)-f^{-1}(A_1)}{2}\right] \]

void FWTXOR(LL a[],int op){for (int d=2;d<=(1<<m);d<<=1){int k=d>>1;for (int i=0;i<(1<<m);i+=d){for (int j=0;j<k;j++){(a[i+j]+=a[i+j+k])%=mod;(a[i+j+k]=a[i+j]-a[i+j+k]*2)%=mod;(a[i+j]*=op)%=mod;(a[i+j+k]*=op)%=mod;}}}
}

---

注意到的是，在函数执行过程中可能存在对负数取模的场景

(a[i+j+k]+=a[i+j]*op)%=mod;//op=-1时

为了降低常数我们不在过程中取模而是统一在全部计算后再依次取正数模

for (int i=0;i<n;i++)if (a[i]<0) a[i]+=mod;

---

FMT 快速莫比乌斯变换优化

莫比乌斯变换：定义 \(f,g\) 是全集 \(U\) 上的任意一个子集的函数，若：

\[f(S)=\sum\limits_{S=S\cup T} g(T) \]

则有：

\[g(S)=\sum\limits_{S=S\cup T} (-1)^{\lvert S\rvert-\lvert T\rvert} f(T) \]

证明：

\[\begin{aligned} \sum_{T \subseteq S} (-1)^{|S|-|T|} f(T) &= \sum_{T \subseteq S} (-1)^{|S|-|T|} \sum_{I \subseteq T} g(I) \\ &= \sum_{I \subseteq S} g(I) \sum_{I \subseteq T,\, T \subseteq S} (-1)^{|S|-|T|} \\ &= \sum_{I \subseteq S} g(I) \sum_{T \subseteq S \setminus I} (-1)^{|S \setminus I| - |T|} \\ &= \sum_{I \subseteq S} g(I) \sum_{k=0}^{|S \setminus I|} \binom{|S \setminus I|}{k} (-1)^{|S \setminus I| - k} \\ &= \sum_{I \subseteq S} g(I) \cdot 0^{|S \setminus I|} \\ &= g(S) \end{aligned} \]

在某些场景下，我们可能并不需要逆变换后 \(C\) 的每一项系数，而是只需要其中某一项次数为 \(k\) 的系数

对 \(f(C)\) 进行逆变换的时间复杂度为 \(O(n\log n)\) ，利用 FMT/容斥原理 可以在 \(O(\log n)\) 的时间复杂度内计算出某一项的系数

LL sum=0;
for (int i=0;i<n;i++){if (__builtin_popcount(n-1-i)&1) sum-=A[i];//这里的n-1是二进制全1的数else sum+=A[i];sum=(sum+mod)%mod;
}