高维前缀和、子集 dp、快速沃尔什变换
高维前缀和
二维前缀和
已知二维数组 \(a\)，求 \(a\) 的二维前缀和。
这题我会，容斥！
二维前缀和
设 \(a\) 的二维前缀和为 \(s\)。
\[
\begin{aligned}
s(i, j) = a(i, j) + s(i - 1, j) + s(i, j - 1) - s(i - 1, j - 1) \\
\end{aligned}
\]
你说得对，但如果我掏出十维甚至九维前缀和，阁下该如何应对？
事实上，高维前缀和可以一维一维地求。
高维前缀和
设 \(a\) 共 \(n\) 维，第 \(k\) 维的长度为 \(m_k\)，\(s_k\) 为 \(a\) 只对前 \(k\) 维求和的前缀和，即：
\[
\begin{aligned}
s_k(i_1, \cdots, i_n) = \sum_{j_1 = 1}^{i_1} \sum_{j_2 = 1}^{i_2} \cdots \sum_{j_k = 1}^{i_k} s_k(j_1, \cdots, j_k, i_{k + 1}, \cdots, i_{n}) \\
\end{aligned}
\]
显然 \(s_0\) 即为 \(a\)。
「一维一维地求」即：
\[
\begin{aligned}
s_k(i_1, \cdots, i_n) &= \sum_{j_1 = 1}^{i_1} \sum_{j_2 = 1}^{i_2} \cdots \sum_{j_k = 1}^{i_k} s_k(j_1, \cdots, j_k, i_{k + 1}, \cdots, i_{n}) \\
&= \sum_{j_k = 1}^{i_k} \left[ \sum_{j_1 = 1}^{i_1} \sum_{j_2 = 1}^{i_2} \cdots \sum_{j_{k - 1} = 1}^{i_{k - 1}} s_k(j_1, \cdots, j_k, i_{k + 1}, \cdots, i_{n}) \right] \\
&= \sum_{j_k = 1}^{i_k} s_k(i_1, \cdots, i_{k - 1}, j_k, i_{k + 1}, \cdots, i_n) \\
\end{aligned}
\]
值得注意的是，维度的顺序并不重要。
子集 dp
子集 dp
已知全集 \(\mathbf U\) 中有 \(n\) 个元素，关于集合的函数 \(f(\mathbf S)\)，求 \(g(\mathbf S) = \displaystyle\sum_{\mathbf T \subset \mathbf S} f(\mathbf S)\)。
令 \(\mathbf S_k \in \{0, 1\}\) 表示集合 \(\mathbf S\) 中第 \(k\) 种元素是否存在。可以发现，\(\mathbf T \subset \mathbf S\) 和 \(\forall i, \mathbf T_i \leq \mathbf S_i\) 是充要条件，因此 \(f\) 可以看作一个 \(n\) 维，每一维长度为 \(2\) 的数组，\(g\) 实际上就是 \(f\) 的前缀和，使用高维前缀和的方法即可解决。
第一种实现
| for (int l = 1; l < (1 << n); l <<= 1)
for (int i = 0; i < (1 << n); i += (l << 1))
for (int j = i; j < i ^ l; ++j)
a[j ^ l] += a[j]; // 这里 j ^ l = j | l = j + l，上面 i ^ l 同理
|
第一层循环枚举维度，第二层循环枚举还未计算的维度，第三层循环枚举已计算的维度。
第二种实现
| for (int i = 1; i < (1 << n); i <<= 1)
for (int j = 0; j < n; ++j)
if (j & i)
a[j] += a[j ^ i]; // 这里 j ^ i = j - i
|
第一层循环枚举维度，第二层循环枚举全集的所有子集，通过 if 保证每一维只被计算一次。
第二种实现方式会比第一种慢一些，但时间复杂度相同。
实际上，子集 dp 不只能处理求和的问题（也可以求最大值等），也不只能处理子集的问题（若模板中的求和条件改为 \(\mathbf S \subset \mathbf T\)，求后缀和即可），也可以用差分将 \(g\) 转化为 \(f\)。
快速沃尔什变换(FWT)
FWT
已知 \(a, b\) 两个下标从 \(0\) 开始，长度为 \(2^n\) 的序列，求序列 \(c\)，其中：
\[
c_i = \sum_{j \oplus k = i} a_jb_k
\]
其中 \(\oplus\) 为 \(\operatorname{or}\)，\(\operatorname{and}\) 或 \(\operatorname{xor}\)。
FWT 与 FFT 类似，都是将原序列经过 \(O(n \times 2^n)\) 的变换后相乘，再逆变换得到结果。设 \(\tilde a, \tilde b, \tilde c\) 分别为 \(a, b, c\) 经过 FWT 后的结果。
或卷积
或卷积中，\(\tilde a_i = \displaystyle\sum_{i \operatorname{or} j = i} a_j\)，可以发现：
\[
\begin{aligned}
\tilde a_i \tilde b_i &= \left(\sum_{i \operatorname{or} j = i} a_j \right) \left(\sum_{i \operatorname{or} k = i} b_k \right) \\
&= \sum_{i \operatorname{or} j = i}\sum_{i \operatorname{or} k = i} a_j b_k \\
\end{aligned}
\]
众所周知，位运算可以和集合运算对应，将 \(i, j, k\) 对应到 \(\mathbf A, \mathbf B, \mathbf C\)。\(i \operatorname{or} j = i, i \operatorname{or} k = i\) 可以转化为 \(\mathbf B \subset \mathbf A, \mathbf C \subset \mathbf A\)，根据集合运算，这个条件的充要条件为 \((\mathbf B \cup \mathbf C) \subset A\)，即 \(i \operatorname{or} (j \operatorname{or} k) = i\)。因此：
\[
\begin{aligned}
\tilde a_i \tilde b_i &= \sum_{i \operatorname{or} j = i}\sum_{i \operatorname{or} k = i} a_j b_k \\
&= \sum_{i \operatorname{or} (j \operatorname{or} k) = i} a_j b_k \\
&= \sum_{i \operatorname{or} l = i} \sum_{j \operatorname{or} k = l} a_j b_k \\
&= \sum_{i \operatorname{or} l = i} c_l \\
&= \tilde c_i \\
\end{aligned}
\]
可以发现 \(\tilde a_i\) 实际上就是上文子集 dp 的模板，使用高维前缀和即可求出。而逆变换只需要将前缀和变为差分即可。
第一种实现
| for (int l = 1; l < n; l <<= 1)
for (int i = 0; i < n; i += (l << 1))
for (int j = i; j < (i ^ l); ++j)
a[j ^ l] = inv ? a[j ^ l] - a[j] : a[j ^ l] + a[j];
|
第二种实现
| for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; ++j)
if (j & i)
a[j] = inv ? a[j] - a[j ^ i] : a[j] + a[j ^ i];
|
与卷积
与卷积和或卷积类似，\(\tilde a_i = \displaystyle\sum_{i \operatorname{and} j = i} a_j\)。在求 \(\tilde a\) 时，只需要将高维前缀和改为后缀和。
第一种实现
| for (int l = 1; l < n; l <<= 1)
for (int i = 0; i < n; i += (l << 1))
for (int j = i; j < (i ^ l); ++j)
a[j] = inv ? a[j] - a[j ^ l] : a[j] + a[j ^ l];
|
第二种实现
| for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; ++j)
if (j & i)
a[j ^ i] = inv ? a[j ^ i] - a[j] : a[j ^ i] + a[j];
|
异或卷积
异或卷积和高维前缀和关系不大。
定义 \(i \otimes j = \operatorname{popcount}(i \operatorname{and} j) \bmod 2\)，其中 \(\operatorname{popcount}(x)\) 为 \(x\) 二进制表示中 \(1\) 的个数。
\(\otimes\) 也有类似的性质：
\[
\begin{aligned}
&\operatorname{popcount}(i \operatorname{and} (j \operatorname{xor} k)) \\
=& \operatorname{popcount}(i \operatorname{and} j) + \operatorname{popcount}(i \operatorname{and} k) - 2 \times \operatorname{popcount}(i \operatorname{and} (j \operatorname{and} k)) \\
\end{aligned}
\]
减去一个偶数后奇偶性不变，因此：
\[
\begin{aligned}
\operatorname{popcount}(i \operatorname{and} (j \operatorname{xor} k)) \equiv \operatorname{popcount}(i \operatorname{and} j) + \operatorname{popcount}(i \operatorname{and} k) \pmod 2 \\
\end{aligned}
\]
因为模 \(2\) 意义下的加法和异或是相同的，因此有 \(i \otimes (j \operatorname{xor} k) = (i \otimes j) \operatorname{xor} (i \otimes k)\)。
令 \(\tilde a_i = \displaystyle\sum_{i \otimes j = 0} a_j - \sum_{i \otimes j = 1} a_j\)，有：
\[
\begin{aligned}
\tilde a_i \tilde b_i &= \left(\sum_{i \otimes j = 0} a_j - \sum_{i \otimes j = 1} a_j \right) \left(\sum_{i \otimes k = 0} b_k - \sum_{i \otimes k = 1} b_k \right) \\
&= \left(\sum_{i \otimes j = 0} a_j \right)\left(\sum_{i \otimes k = 0} b_k \right) - \left(\sum_{i \otimes j = 1} a_j \right)\left(\sum_{i \otimes k = 0} b_k \right) - \left(\sum_{i \otimes j = 0} a_j \right)\left(\sum_{i \otimes k = 1} b_k \right) + \left(\sum_{i \otimes j = 1} a_j \right)\left(\sum_{i \otimes k = 1} b_k \right) \\
&= \sum_{i \otimes j = 0} \sum_{i \otimes k = 0} a_j b_k - \sum_{i \otimes j = 1} \sum_{i \otimes k = 0} a_j b_k - \sum_{i \otimes j = 0} \sum_{i \otimes k = 1} a_j b_k + \sum_{i \otimes j = 1} \sum_{i \otimes k = 1} a_j b_k \\
&= \sum_{i \oplus (j \operatorname{xor} k) = 0} a_j b_k - \sum_{i \oplus (j \operatorname{xor} k) = 1} a_j b_k \\
&= \sum_{i \oplus l = 0} \sum_{j \operatorname{xor} k = l} a_j b_k - \sum_{i \oplus l = 1} \sum_{j \operatorname{xor} k = l} a_j b_k \\
&= \sum_{i \oplus l = 0} c_l - \sum_{i \oplus l = 0} c_l \\
&= \tilde c_i \\
\end{aligned}
\]
至于 \(\tilde a\) 的求法，设 \(i\) 的二进制第 \(k\) 位为 \(i_k\)，\(f_k(i_1, \cdots, i_n)\) 为在后 \(n - k\) 位相同且不考虑、只考虑前 \(k\) 位的情况下的 \(\tilde a_i\) 值，\(f_0\) 即 \(a\)。具体来说，对于 \(n = 2\)，\(f_1(1, 1) = f_0(0, 1) - f_0(1, 1)\)，虽然 \((11)_2 \operatorname{and} (01)_2 = (01)_2\)，有一个 \(1\)，但因为我们只考虑第一位，第二位往后相同且不考虑，所以将第二位往后的 \(1\) 忽略。考虑 \(f_k\) 的递推：
\[
\begin{aligned}
f_k(i_1, \cdots i_{k - 1}, 0, i_{k + 1} \cdots i_n) &= f_{k - 1}(i_1, \cdots i_{k - 1}, 0, i_{k + 1} \cdots i_n) + f_{k - 1}(i_1, \cdots i_{k - 1}, 1, i_{k + 1} \cdots i_n) \\
f_k(i_1, \cdots i_{k - 1}, 1, i_{k + 1} \cdots i_n) &= f_{k - 1}(i_1, \cdots i_{k - 1}, 0, i_{k + 1} \cdots i_n) - f_{k - 1}(i_1, \cdots i_{k - 1}, 1, i_{k + 1} \cdots i_n) \\
\end{aligned}
\]
因为 \(0 \operatorname{and} 0 = 0 \operatorname{and} 1 = 0\)，所以若第 \(k\) 位为 \(0\)，加入第 \(k\) 位之后第 \(k\) 位对与运算后结果中 \(1\) 个数没有影响。而 \(1 \operatorname{and} 1 = 1\)，所以若第 \(k\) 位为 \(1\)，加入第 \(k\) 位之后仅当第 \(k\) 位为 \(1\) 时才对 \(1\) 的个数的奇偶性有影响。
逆变换即为：
\[
\begin{aligned}
f_k(i_1, \cdots i_{k - 1}, 0, i_{k + 1} \cdots i_n) &= \frac{f_{k - 1}(i_1, \cdots i_{k - 1}, 0, i_{k + 1} \cdots i_n) + f_{k - 1}(i_1, \cdots i_{k - 1}, 1, i_{k + 1} \cdots i_n)}{2} \\
f_k(i_1, \cdots i_{k - 1}, 1, i_{k + 1} \cdots i_n) &= \frac{f_{k - 1}(i_1, \cdots i_{k - 1}, 0, i_{k + 1} \cdots i_n) - f_{k - 1}(i_1, \cdots i_{k - 1}, 1, i_{k + 1} \cdots i_n)}{2} \\
\end{aligned}
\]
第一种实现
| for (int l = 1; l < n; l <<= 1)
for (int i = 0; i < n; i += (l << 1))
for (int j = i; j < (i ^ l); ++j) {
int tmp1 = a[j], tmp2 = a[j ^ l];
a[j] = tmp1 + tmp2, a[j ^ l] = tmp1 - tmp2;
if (inv)
a[j] >>= 1, a[j ^ l] >>= 1;
}
|
第二种实现
| for (int i = 1; i < n; i <<= 1)
for (int j = 0; j < n; ++j)
if (j & i) {
int tmp1 = a[j ^ i], tmp2 = a[j];
a[j ^ i] = tmp1 + tmp2, a[j] = tmp1 - tmp2;
if (inv)
a[j ^ i] >>= 1, a[j] >>= 1;
}
|