浅谈 高维前缀和 与 sosdp

前言：暑假的时候听学长讲过一次高维前缀和，当时听得一头雾水，后面查阅资料在网上也没要找到能让我看懂的文章（我好菜 qwq）。最近进行学习之后决定来浅谈高维前缀和。

高维前缀和

所谓高维前缀和，就是很多维前缀和。

看到我们常写的二维前缀和，相信大家通常会使用这样的写法。

for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
  s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

这是一个容斥的想法。但大家有没有考虑过，这里的维度是 3 的时候，你要怎么写？此时你要设计 8 个容斥系数，当维数来到 k 时，这个数字是 2^k。于是使用一个更好的写法势在必行。

我们有一个想法，就是一维一维地做前缀和，那我们只要一维一维递推即可。实现非常容易，以下是一个三维的例子。

for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
  s[i][j][k] += s[i - 1][j][k];
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
  s[i][j][k] += s[i][j - 1][k];
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
  s[i][j][k] += s[i][j][k - 1];

但是一个问题还是没有解决，如果要做十维前缀和，难道要开十维数组吗？我们联想到可以使用状态压缩来把它压成一维。在上面这个例子中，我们设计一个状态压缩函数 f 就可以把数组压到一维。

int f(int i, int j, int k) { return i * (n + 1) * (n + 1) + j * (n + 1) + k; }
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
    s[f(i, j, k)] += s[f(i - 1, j, k)];
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
    s[f(i, j, k)] += s[f(i, j - 1, k)];
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++)
    s[f(i, j, k)] += s[f(i, j, k - 1)];

我们显然可以把这几个循环搞到一起，并且可以直接枚举压缩后的状态。比较普适性的，当维数为 k，状态总数为 m，一维有 n 种可能的时候，我们可以这样实现。

for (int o = 0; o < k; o++) 
    for (int i = 0; i < m; i++)
        if (g(i, o) > 0) s[i] += s[i - h(n, o)]
// g(i, o) 可以提取状态 i 的第 o 位
// h(n, o) 可以表示状态第 o 位的 "1"

这就是高维前缀和的实现方法，时间复杂度 kn^k，相较于容斥写法的 2^kn^k，时间复杂度也会更优秀。当然了，这里的前缀和也可以变成前缀 max 等等东西。接下来看一道例题。

ARC136D

题意：求满足 a_i 和 a_j 做加法不进位且 i < j 的 (i, j) 的数量。n \le 10^6,0 \le a_i < 10^6。

考虑对于每一位作为一维做前缀和，就是六维前缀和。考虑不进位就是每一位都满足和 \le 9，考虑状压之后的状态表示，对于每个数求 s[99999 - a[i]] 即可。注意 i \neq j 并且 i, j 有序。

const int N = 1e6 + 5, M = 999999;
int n, a[N], s[N];

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); 
    cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; s[a[i]]++;
        bool flag = false;
        for (int j = 1; j <= M; j *= 10) flag |= ((a[i] / j % 10) >= 5);
        ans -= !flag;
    }
    for (int j = 1; j <= M; j *= 10) for (int i = 1; i <= M; i++)
        if (i / j % 10 > 0) s[i] += s[i - j];
    for (int i = 1; i <= n; i++) ans += s[M - a[i]];
    cout << ans / 2;
    return 0;
}

sosdp

以下规定对于二进制数 x, y，如果 x 的每一个 1 的位 y 也是 1，称 x 为 y 的子集，y 为 x 的超集。

在一些问题中，我们会遇到要维护所有子集信息的问题（二进制意义下的）。我们考虑到在高维前缀和中，维数为 \log V，每个维度为 0/1，可以写出这样的代码。

for (int j = 0; j < K; j++) for (int i = 0; i < (1 << K); i++)
  if (i >> j & 1) f[i] += f[i ^ (1 << j)];

这样我们对于二进制下的每一位都做了前缀和，显然也就维护了所有子集的信息。同时我们也可以维护所有超集的信息。

for (int j = 0; j < K; j++) for (int i = (1 << K) - 1; i >= 0; i--)
  if (!(i >> j & 1)) f[i] += f[i ^ (1 << j)]

也可以通过 dp 的方式来理解，注意这里的转移顺序，每次从一位有 1 的转移到 0，所以要从大到小转移。这种写法也叫 sosdp（子集 dp，实际上也可以解决超集的问题），实际上就是高维前缀和的想法。时间复杂度 O(\log V 2^{\log V}) = O(V \log V)，比枚举子集的 O(3^{\log V}) 看起来优秀许多。接下来看一道简单的例题。

CF165E

题意：对于所有 i 求出任意一个 j 使 a_i \ \text{and}\ a_j = 0 或报告无解。

对于每一位或起来都是 0，那对于一位，a_i 是 1 时，a_j 是 0；a_i 是 0 时，a_j 是 1 或 0。发现如果把 a_i 按位反转，a_j 就是 a_i 的子集。那我们直接 sosdp 转移即可。

const int N = 1e6 + 5, K = 23;
int n, a[N], b[N], f[1 << K];

signed main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n; memset(f, -1, sizeof f);
    for (int i = 1; i <= n; i++) {
        cin >> a[i]; f[a[i]] = a[i];
        for (int j = 0; j < K; j++) b[i] += (!(a[i] >> j & 1)) << j;
    }
    for (int j = 0; j < K; j++) for (int i = 0; i < (1 << K); i++)
        if (i >> j & 1 && f[i ^ (1 << j)] != -1) f[i] = f[i ^ (1 << j)];
    for (int i = 1; i <= n; i++) cout << f[b[i]] << ' ';
    return 0;
}

后记：sosdp 是高维前缀和最广泛的应用，遇到与二进制有关的问题，可以想想能不能转化成子集/超集相关的问题。FMT（快速莫比乌斯变换）运用的就是这个想法，大家可以去了解一下（我太菜了我不会 qwq）。