【高维前缀和与位运算】学习笔记

· · 算法·理论

一、高维前缀和

常见形式是类似多维数组的形式，求法是逐维递推，设维度为 k，值域为 n，则时间复杂度为 O(n^k \times k)。

另一种形式是二进制集合形式，每一维的值域都是 [0, 1]，即以一个数的二进制数做下标，通过位运算来递推，时间复杂度为 O(n \times 2^n)。

二、FMT（快速莫比乌斯变换）与应用——与或卷积

FMT 的主要变换形式为在二进制集合下进行高维前缀、后缀和，分别用来求解或、与卷积。

1. 或变换

正变换式子：a_i = \sum_{j | i = i} a_j，本质上是高维前缀和，逆变换自然就是高维前缀差分。

inline void Fwt_or(ll* f, int opt) {
    for (int len = 2, k = 1; len <= U; len <<= 1, k <<= 1)
        for (int i = 0; i < U; i += len)
            for (int j = 0; j < k; ++j)
                f[i + j + k] = (f[i + j + k] + f[i + j] * opt + Mod) % Mod;
    return ;
}

2. 与变换

与或变换类似，本质上是翻转了二进制位，及转变为高维后缀和与高维后缀差分。

inline void Fwt_and(ll* f, int opt) {
    for (int len = 2, k = 1; len <= U; len <<= 1, k <<= 1)
        for (int i = 0; i < U; i += len)
            for (int j = 0; j < k; ++j)
                f[i + j] = (f[i + j] + f[i + j + k] * opt + Mod) % Mod;
    return ;
}

3. 应用

此处以或变换求或卷积为例，也可以求与卷积、\gcd 卷积。

题面：求数组 c，满足 c_k = \sum_{i | j = k} a_i b_j。

算法思路：对 a, b 做或变换得到 A, B，对结果数组 c 也做或变换得 C，易证 C_i = A_i B_i，再对 C 做 IFMT 得到 c，即答案数组。

本质：通过线性变换将问题加在一种空间里满足简单点乘关系，再通过逆变换求原数组，构造这种线性变换是解决问题的关键。

三、子集卷积

问题形如：c_S = \sum_{T \subset S} a_T b_{S \setminus T}，关键在于要求两子集不重合。

解法思路：固定大小再做普通或卷积。具体地，令 A_{i, S} = \sum_{T \subset S, |T| = i} a_T，B_{i, S}, C_{i, S} 同理，且令 c'_{i, S} = [|S| = i] c_S，则可以得到如下两个式子：

C_{i, S} = \sum_{j = 0} ^ i A_{j, S} B_{i - j, S} C_{i, S} = \sum_{T \subset S} c'_{i, T}

则可以通过 FMT 求出每一层次的 A, B, C 数组，再进行 IFMT 逆变换求出 c' 数组，最后 c'_{|S|, S} 即 c_S。

cin >> n, U = (1 << n);
    for (int i = 0; i < U; ++i)
        cin >> A[popcount(i)][i];
    for (int i = 0; i < U; ++i)
        cin >> B[popcount(i)][i];
    for (int i = 0; i <= n; ++i)
        FMT(A[i], 1), FMT(B[i], 1);
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= i; ++j)
            for (int S = 0; S < U; ++S)
                C[i][S] = (C[i][S] + A[j][S] * B[i - j][S] % Mod) % Mod;
    for (int i = 0; i <= n; ++i)
        FMT(C[i], -1);
    for (int i = 0; i < U; ++i)
        cout << C[popcount(i)][i] << ' ';

子集卷积也可以半在线实现，常应用于动态规划。

四、FWT（快速沃尔什变换）与异或卷积

通过构造针对异或位运算的线性变换可以得到 FWT 的异或变换。

inline void Fwt_xor(ll* f, int opt) {
    for (int len = 2, k = 1; len <= U; len <<= 1, k <<= 1)
        for (int i = 0; i < U; i += len)
            for (int j = 0; j < k; ++j)
                f[i + j] = (f[i + j] + f[i + j + k]) % Mod, f[i + j + k] = (f[i + j] - (f[i + j + k] << 1) + (Mod << 1)) % Mod,
                f[i + j] = f[i + j] * opt % Mod, f[i + j + k] = f[i + j + k] * opt % Mod;
    return ;
}

正、逆变换的参数为 1, \frac{1}{2}。

五、整体总结

FMT、高维前缀和、FWT、子集卷积都是难度较大的技巧，真正掌握需要深刻的理解！

六、例题

模板题如下：P4717 与 P6097，比较不错的题目目前有 CF449D。