SOS dp

SOS dp是解决类似这样的问题 $$\begin{aligned} F[mask] &= \sum _ {i \subseteq mask} A[i]\end{aligned}$$ 的一种解法（其实就是高维前缀和）。

这种问题，有不同的解法，比如：

1.时间复杂度 $O(4^n)$

for(int mask = 0;mask < (1<<N); ++mask){
    for(int i = 0;i < (1<<N); ++i){
        if((mask&i) == i){
            F[mask] += A[i];
        }
    }
}

不过时间复杂度太高，正常一点的出题人出的题目一定过不了。

2.时间复杂度 $O(n^3)$

// iterate over all the masks
for (int mask = 0; mask < (1<<n); mask++){
    F[mask] = A[0];
    // iterate over all the subsets of the mask
    for(int i = mask; i > 0; i = (i-1) & mask){
        F[mask] += A[i];
    }
}

时间复杂度证明见codeforces。

3.SOS dp

我们记 $F[mask][i]$ 为对于数 $mask$ 的二进制中，第 $i$ 位是不同的.

若 $mask$ 的第 $i$ 位是 $0$，则

$F[mask][i]=F[mask][i-1]$

若 $mask$ 的第 $i$ 位是 $1$，则

$F[mask][i]=F[mask][i-1]+F[mask \bigoplus 2^i][i-1]$ 简单来讲，就是：上图描述了我们如何将$S(mask,i)$ 集相互关联。任何集合 $S(mask,i)$的元素都是其子树中的叶子。红色前缀表示掩码的这一部分对其所有成员/子级都是通用的，而掩码的黑色部分可以不同。

请注意，这些关系形成了一个有向无环图，而不一定是有根树。

在实现了这些关系之后，我们可以很容易地提出相应的动态规划。

代码：

//iterative version
for(int mask = 0; mask < (1<<N); ++mask){
    dp[mask][-1] = A[mask];    //handle base case separately (leaf states)
    for(int i = 0;i < N; ++i){
        if(mask & (1<<i))
            dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
        else
            dp[mask][i] = dp[mask][i-1];
    }
    F[mask] = dp[mask][N-1];
}

还可以继续优化：

//memory optimized, super easy to code.
for(int i = 0; i<(1<<N); ++i)
    F[i] = A[i];
for(int i = 0;i < N; ++i)
    for(int mask = 0; mask < (1<<N); ++mask){
        if(mask & (1<<i))
            F[mask] += F[mask^(1<<i)];
}

注意，代码中的 $N$ 为最大的二进制长度，即 $N$ 为题目中给定的最大的 $log n$。

例题：

1.CF165E Compatible Numbers

作为 CF 中 div2 的最后一题，本人认为有点水。

这其实就是一道高维前缀和的模板题。

分析：对于每一对 $ai \& aj = 0$，若 $ai$ 和 $aj$ 的二进制表示中有同一位均为 $1$，那么 $ai \& aj$ 的这一位也会为 $1$。因此可以发现，$ai$ 是 $aj$ 按位取反后的子集。

实现：预处理出数组 $a$ 的高维前缀和，每一次询问时先取反，再看取反后子集是否为空。高维前缀和只需存储子集中的任意一个数即可。

我的代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 1000005;
const int INF = 0x3f3f3f3f;
int a[N];
int f[1 << 22];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        f[a[i]] = i;
    }
    for (int i = 0; i < 22; i++) {
        for (int j = 0; j < 1 << 22; j++) {
            if (f[j] == 0 && (j >> i & 1)) f[j] = f[j ^ 1 << i];
        }
    }
    a[0] = -1;
    for (int i = 1; i <= n; i++) {
        printf("%d ", a[f[a[i] ^ (1 << 22) - 1]]);
    }
    printf("\n");
    return 0;
}

2. CF449D Jzzhu and Numbers

若设 $fs$ 表示子集含有 $s$ 的方案数，那么实际上 $fs$ 就是所有含 $s$ 的集合的高维前缀和,倒着处理一遍所有含 $s$ 的 $a$ 的个数，那么显然 $fs=2^{fs}-1$，接下来根据差分的思想再差分回去就好了。代码：

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const int N = 1000005;
const int INF = 0x3f3f3f3f;
int a[1 << 20];
ll two[N], f[1 << 20];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) {
        scanf("%d", &x);
        a[x]++;
    }
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 1 << 20; j++) {
            if (!(j >> i & 1)) a[j] += a[j ^ 1 << i];
        }
    }
    two[0] = 1;
    for (int i = 1; i <= n; i++) two[i] = two[i - 1] * 2 % mod;
    for (int j = 0; j < 1 << 20; j++) f[j] = two[a[j]] - 1;
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 1 << 20; j++) {
            if (!(j >> i & 1)) f[j] -= f[j ^ 1 << i], f[j] %= mod;
        }
    }
    printf("%lld\n", (f[0] + mod) % mod);
    return 0;
}

最后，我发现这场 CF 做 D 题的人比做 A 的还多

jxy2012的博客

博客

评论

发表评论