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