[学习笔记] 快速沃尔什变换 (FWT)
- 0. 引入与一些约定
- 1. 按位或卷积
- 1.1. 定义与正确性
- 1.2. 正变换
- 1.3. 逆变换
- 1.4. 代码实现
- 2. 按位与卷积
- 2.1. 定义
- 2.2. 正变换
- 2.3. 逆变换
- 2.4. 代码实现
- 3. 按位异或卷积
- 3.1. 定义
- 3.2. 正变换
- 3.3. 逆变换
- 3.4. 代码实现
- 4. 高维前/后缀和与各类卷积的联系
- 4.1. 按位或卷积
- 4.2. 按位与卷积
- 4.3.
- 5. 题目小结
0. 引入与一些约定
想要快速计算
\[C[k]=(A\text{ opt }B)[k]=\sum_{i\text{ opt }j=k}a_ib_j \]我们可以利用 的思想：将系数多项式转化成点值多项式，\(\mathcal O(n)\) 求得答案后将其还原成系数多项式。
假设 \(A,B\) 均为多项式，则 \(A+B,A-B,A\times B\) 都代表着 对位运算。
\(\mid,\&,\oplus\) 分别表示或、与、异或。且若无特殊说明，\(i\subseteq j\) 表示在二进制意义下 \(i\) 是 \(j\) 的子集。
1. 按位或卷积
1.1. 定义与正确性
定义
\[\mathtt{FWT}(A)[i]=\sum_{j\mid i=i}a_j\\ \mathtt{IFWT}(\mathtt{FWT}(A))=A \]所以有
\[\begin{align} \big[\mathtt{FWT}(A)\times \mathtt{FWT}(B)\big][i]&=\sum_{j_1\cup j_2\subseteq i}a_{j_1}b_{j_2}\\ &=\sum_{(j_1\mid j_2)|i=i}a_{j_1}b_{j_2} \end{align} \]按照定义将上面那个柿子 \(\mathtt{IFWT}\) 一下就是 \(A|B\) 了。
1.2. 正变换
对于一个多项式 \(A\)，不妨设其长度为 \(2^n\)，令 \(A_0,A_1\) 分别为前 \(2^{n-1}\) 项，后 \(2^{n-1}\) 项（其实也可以理解为将下标以二进制的最高位分组），有：
\[\mathtt{FWT}(A)= \begin{cases} \big(\mathtt{FWT}(A_0),\mathtt{FWT}(A_0+A_1)\big) & & n>0\\ A && n=0 \end{cases} \]这个递归式可以这样理解：最终能贡献到前 \(2^{n-1}\) 项的项的最高位一定为零，此时 \(A_1\) 这一部分一定无用，所以由 \(\mathtt{FWT}(A_0)\) 组成；贡献到后 \(2^{n-1}\) 项的项的最高位可以为 \(0/1\)，所以相当于没有限制，此时贡献到哪一位只由二进制的后 \(n-1\) 位决定，所以 \(A_0[i]\) 和 \(A_1[i]\) 是等价的，可以对位相加。
由上文的证明，我们也可以得到 \(\mathtt{FWT}(A_0+A_1)=\mathtt{FWT}(A_0)+\mathtt{FWT}(A_1)\).
1.3. 逆变换
\[\mathtt{IFWT}(A)= \begin{cases} \big(\mathtt{IFWT}(A_0),\mathtt{IFWT}(A_1-A_0)\big) & & n>0\\ A && n=0 \end{cases} \]\(n=0\) 的情况就不再赘述，对于 \(n>0\) 的情况，我们直接将 \(\mathtt{FWT}(A)\) 代入柿子：
\[\begin{align} \mathtt{IFWT}\big(\mathtt{FWT}(A)\big)&=\big(\mathtt{IFWT}(\mathtt{FWT}(A_0)),\mathtt{IFWT}(\mathtt{FWT}(A_0+A_1)-\mathtt{FWT}(A_0))\big)\\ &=\big(A_0,\mathtt{IFWT}(\mathtt{FWT}(A_0)+\mathtt{FWT}(A_1)-\mathtt{FWT}(A_0)) \big)\\ &=(A_0,A_1) \end{align} \]1.4. 代码实现
void OR(int *f,int opt=1) {
for(int l=2;l<=n;l<<=1)
for(int o=0,p=l>>1;o2. 按位与卷积
2.1. 定义
定义
\[\mathtt{FWT}(A)[i]=\sum_{j\& i=i}a_j\\ \mathtt{IFWT}(\mathtt{FWT}(A))=A \]所以有
\[\begin{align} \big[\mathtt{FWT}(A)\times \mathtt{FWT}(B)\big][i]&=\sum_{j_1\cap j_2\supseteq i}a_{j_1}b_{j_2}\\ &=\sum_{(j_1\& j_2)\&i=i}a_{j_1}b_{j_2} \end{align} \]按照定义将上面那个柿子 \(\mathtt{IFWT}\) 一下就是 \(A\&B\) 了（其实计算 \(\mathtt{FWT}(A\&B)\) 应该会更好理解，你会发现 \(\mathtt{FWT}(A\&B)[i]\) 就是枚举 \(i\) 的超集 \(j\)，再枚举 \(j_1,j_2\) 使得 \(j_1\&j_2=j\)）。
2.2. 正变换
\[\mathtt{FWT}(A)= \begin{cases} \big(\mathtt{FWT}(A_0+A_1),\mathtt{FWT}(A_1)\big) & & n>0\\ A && n=0 \end{cases} \]理解方式同上，就不再阐述。
2.3. 逆变换
\[\mathtt{IFWT}(A)= \begin{cases} \big(\mathtt{IFWT}(A_0-A_1),\mathtt{IFWT}(A_1)\big) & & n>0\\ A && n=0 \end{cases} \]证明方式同上，就不再阐述。
2.4. 代码实现
void AND(int *f,int opt=1) {
for(int l=2;l<=n;l<<=1)
for(int o=0,p=l>>1;o3. 按位异或卷积
3.1. 定义
定义 \(i\circledast j\) 为 \(i\& j\) 在二进制下 \(1\) 的个数的奇偶性。
定义
\[\mathtt{FWT}(A)[i]=\sum_{i\circledast j=0}a_j-\sum_{i\circledast j=1}a_j=\sum (-1)^{i\circledast j}\cdot a_j\\ \mathtt{IFWT}(\mathtt{FWT}(A))=A \]在证明 \(\mathtt{FWT}(A\oplus B)=\mathtt{FWT}(A)\times \mathtt{FWT}(B)\) 之前，首先有结论：\((i\circledast j)\oplus (i\circledast k)=i\circledast (j\oplus k)\).
具体证明可以对 \(i,j,k\) 二进制的每一位考虑，如果每一位都成立那么总结论也可以推知。只证明一位的话分类讨论或者打表都行 /ww.
那么
\[\begin{align} \big[\mathtt{FWT}(A)\times \mathtt{FWT}(B)\big][i]&=\left(\sum_{i\circledast j=0}a_j-\sum_{i\circledast j=1}a_j \right)\cdot\left(\sum_{i\circledast k=0}b_k-\sum_{i\circledast k=1}b_k\right)\\ &=\sum_{i\circledast (j\oplus k)=0}a_jb_k-\sum_{i\circledast (j\oplus k)=1}a_jb_k=\mathtt{FWT}(A\oplus B)[i] \end{align} \]3.2. 正变换
\[\mathtt{FWT}(A)= \begin{cases} \big(\mathtt{FWT}(A_0)+\mathtt{FWT}(A_1),\mathtt{FWT}(A_0)-\mathtt{FWT}(A_1)\big) & & n>0\\ A && n=0 \end{cases} \]证明就是暴力推柿子：
\[\begin{align} \mathtt{FWT}(A)[i]&=\sum_{j=0}^{2^n-1}(-1)^{i\circledast j}a_j\\ &=\sum_{j=0}^{2^{n-1}-1}(-1)^{i\circledast j}a_j+\sum_{j=2^{n-1}}^{2^{n}-1}(-1)^{i\circledast j}a_j\\ &=\mathtt{FWT}(A_0)[i]+\sum_{j=0}^{2^{n-1}-1}(-1)^{i\circledast j}a_{j+2^{n-1}}\\ &=\mathtt{FWT}(A_0)[i]+\mathtt{FWT}(A_1)[i] \end{align} \]3.3. 逆变换
若 \(n>0\)：
\[\mathtt{IFWT}(A)=\left(\frac{\mathtt{IFWT}(A_0)+\mathtt{IFWT}(A_1)}{2},\frac{\mathtt{IFWT}(A_0)-\mathtt{IFWT}(A_1)}{2}\right) \]需要证明 \(\mathtt{FWT}(A_0+A_1)=\mathtt{FWT}(A_0)+\mathtt{FWT}(A_1)\)，这个由 \(\mathtt{FWT}(A)[i]=\sum (-1)^{i\circledast j}\cdot a_j\) 可以轻松得出。
接下来就与 1.3. 逆变换 相同，直接代入即可。
3.4. 代码实现
void XOR(int *f,int opt=1) {
for(int l=2;l<=n;l<<=1)
for(int o=0,p=l>>1;o4. 高维前/后缀和与各类卷积的联系
4.1. 按位或卷积
其实就是将所有下标看作长度为 \(n\) 的二进制串。比如 \(i=(0010)_2\) 对应数组编号 \([0][0][1][0]\). 令 \(s_i,t_i\) 分别为 \(a_i,b_i\) 的前缀和。为了更清楚地说明，令 \(i=(p_1p_2\dots p_n)_2\)，那么可以这样表示：
\[s_i=\sum a_{(j_1j_2\dots j_n)_2}\cdot \prod_{k=1}^n [0\le j_{k}\le p_k] \]可以发现，所谓的 \(\mathtt{FWT}(A)[i]\) 其实就是 \(s_i\). 那么我们将 \(s_i\) 与 \(t_i\) 相乘，看看得到了什么：
\[s_it_i=\sum a_{(j_1j_2\dots j_n)_2}\cdot b_{(k_1k_2\dots k_n)_2}\cdot \prod_{l=1}^n [0\le j_{l}\le p_l]\cdot [0\le k_{l}\le p_l] \]\(\bf FBI\ Warning\)：以下内容全是辣鸡博主在乱扯，如果扯得不对请在评论区指出，别点踩嗄 /ww
定义 \(f(i)=(\max(0,p_1-1)\max(0,p_2-1)\dots \max(0,p_n-1))_2\). 是的，你没有看错，这个玩意儿就是零，我也觉得好它吗怪。那么
怎么说呢，这个柿子可以用多重 for 循环来理解。如果只考虑 \(1\) 维前缀和（二进制只有 \(1\) 位）就可以画一个矩形来表示 \(s_it_i\)，那么 \(s_it_i-s_{f(i)}t_{f(i)}=s_it_i-s_{i-1}t_{i-1}\)，其实这个差可以看作旋转 \(180^\circ\) 的 L 形图案。
这个图案就是我们要求的 \((A|B)[i]\) 了。所以说，高维前缀和的差分就是 \(\mathtt{IFWT}\).
4.2. 按位与卷积
其实是一样的，只不过是前缀和变成了后缀和，\(\max\) 卷积变成了 \(\min\) 卷积。
4.3. \(\rm more?\)
我也只会口胡，你可以发现 \(\gcd\) 和 \(\text{lcm}\) 卷积实际上是幂次上的 \(\min\) 和 \(\max\) 卷积。
5. 题目小结
例 1. \(\text{CF662C Binary Table}\)
考虑到 \(n\) 是很小的，可以枚举行的翻转状态，定义状态 \(i\) 得到的最小 \(1\) 个数为 \(C_i\). 设 \(A_i\) 为列状态为 \(i\) 的列数，\(B_i\) 为 \(i\) 和 \(2^n\oplus i\) 更少的 \(1\) 的个数（枚举列的翻转）。那么有：\(C_i=\sum A_jB_{i\oplus j}\). 这就是一个很板的 \(\mathtt{FWT}\) 了。但一定要注意 数据范围的计算。
例 2. \(\text{BZOJ - 4589 Hard Nim}\)
令 \(P(x)=[x\text{ is prime}\wedge x\le m ]\)，那么答案显然是 \(P^n[0]\)，定义 "乘法" 为 \(\oplus\).
这道题目其实就是将 \(\mathtt{FWT}(A\oplus B)=\mathtt{FWT}(A)\times \mathtt{FWT}(B)\) 拓展到
\[\mathtt{FWT}(A_1\oplus A_2\oplus\dots \oplus A_n)=\mathtt{FWT}(A_1)\times \mathtt{FWT}(A_2)\times \dots\times \mathtt{FWT}(A_n) \]类似于 \(A\oplus B=\mathtt{IFWT}(\mathtt{FWT}(A)\times \mathtt{FWT}(B))\)，再乘上 \(C\) 得：
\[\begin{align} (A\oplus B)\oplus C&=\mathtt{IFWT}(\mathtt{FWT}(A\oplus B)\times \mathtt{FWT}(C))\\ &=\mathtt{IFWT}(\mathtt{FWT}(A)\times \mathtt{FWT}(B)\times \mathtt{FWT}(C)) \end{align} \]结论可以归纳证明。