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$。
例题:
作为 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; }
若设 $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 的还多