浅谈 SOS DP

SOS DP 是状压 DP 的一种，全称 Sum over Subsets Dynamic Programming，用来解决一些子集和转移的问题，是高维前缀和的一种体现。

引入

因为大家都是这样引入的，我就这样引入吧。

例题：

给定一个含有 \(n\) 个数的序列 \(a_{n}\)，对于每个集合 \(S \subset \{a_n\}\)，计算 \(f_{S} = \sum_{T \subset S} \sum_{i \in T} a_i\)，即计算所有子集的所有总和。

朴素的做法：暴力枚举每一个初始状态是 \(O(2^n)\) 的，暴力枚举每一个子集状态，总复杂度 \(O(4^n)\)。

for (int i = 0; i < (1 << n); i++) {for (int j = 0; j < i; j++) {f[i] += f[j];}
}

当然这样的暴力复杂度是在是天方夜谭，如果你学过状压，那么你一定会子集枚举，并且知道总复杂度是 \(O(3^n)\) 的。

具体证明一下：假如一个状态上的 \(1\) 一共有 \(k\) 位，那么这样的状态 \(\dbinom{n}{k}\) 种情况，总和为 \(\sum_{k=0}^n \dbinom{n}{k} 2^k = \sum_{k=0}^n \dbinom{n}{k} 1^{n-k}2^k\)，二项式定理得到 \((1+2)^n = O(3^n)\) 复杂度。

for (int i = 0; i < (1 << n); i++) {for (int j = i; j; j = (j - 1) & i) {f[i] += f[j];}
}

不出所料，上述的算法还可以优化，当一个状态的二进制位上有 \(k\) 个 \(0\) 时，它将在其他状态被访问 \(2^k-1\) 次。

通俗来讲：我们有 \(S^{\prime\prime} \subset S^{\prime} \subset S\)，我们计算 \(S\) 时，不光要计算 \(S^{\prime}\)，还要计算 \(S^{\prime\prime}\)，但这不必要，包含 \(S^{\prime}\) 一定意味着包含 \(S^{\prime\prime}\)。

所以我们可以使用 DP 状态进行优化，我们枚举每一位 \(k\) 注意一定是在最外层顺序枚举，接下来枚举每一种状态。

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

考虑转移为什么是对的：我们定义 \(f_i\) 表示所有的子集和，正在转移第 \(k\) 位时，我们发现当前转移的 \(f_i\) 表示前 \(k\) 位是 \(i\) 的子集的子集和。

\[f_i \leftarrow f_{i - 2^k} \]

因为 \(f_{i-2^k}\) 在 \(f_i\) 之前转移。

我们如果任意拿一个二进制举例，比如转移 \(100101\)，转移到了 \(100\ \textbf{1}\ 01\)（加粗的那一位）， 有：

\[f_{100101} = \begin{cases} f_{000001} \\ f_{100001} \\ f_{000101} \\ f_{100101} \end{cases} \]

最开始 \(f_{100101}\) 里面只有 \(f_{100101}\)，转移第 \(1\) 位时加入了 \(000101\)。

因此现在有：

\[f_{100101} = \begin{cases} f_{000001} (无) \\ f_{100001} (无) \\ f_{000101} (有) \\ f_{100101} (有) \end{cases} \]

观察发现如果此时 \(f_{100101}\) 再加上一个 \(f_{100001}\) 即可。

因为转移了第一位后：

\[f_{000101} = \begin{cases} f_{100001} (无) \\ f_{000001} (无) \end{cases} \]

因此我们证明任何转移都可以像上述一样成立。