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 的还多
