0 引
为什么没在标题里写 SOS DP ？因为这 SOS 这个名字我第一次看的时候怎么看怎么觉得不正经，所以写全称让他看着正经一些。
个人感觉这个东西更像是一个套路而不是 DP 类型。
1 什么是 SOS DP
Sum over Subsets DP，即求子集和的 DP。更具体的说，用于在 $O(k \cdot 2^k)$ 的时间求出以下式子：
$$
f_{mask} = \sum_{i \subseteq mask} a_i
$$
2 做法
一种非常朴素的方式是直接对于每个子集枚举其子集，复杂度是 $O(4^n)$。这个复杂度显然是无法接受的。
定义 $S(k,i) = \{ x | x \subseteq k \land k \oplus x < 2^{i+1} \}$。
则显然有
$$
S(k,i) =
\begin{cases}
S(k,i-1) & k \& 2^i = 0 \\
S(k,i-1) \cup S( k \oplus 2^i, i – 1 ) & otherwise
\end{cases}
$$
注意到现在已经可以递推 S 来得到我们想要的结果了。
但是更广为人知的是这个滚动数组的写法：
for( int st = 0; st < ( 1 << K ); st ++ )
f[i] = a[i];
for( int j = 0; j < K; j ++ ) {
for( int st = 0; st < ( 1 << K ); st ++ ) {
if( st & ( 1 << j ) )
f[i] += f[ i ^ ( 1 << j ) ];
}
}