子集和 DP

子集和 DP 说的是通过 DP 求出每个子集的贡献之和。也就是说，我们需要对每个 $mask$ 求出

$$f[mask]:=\sum _{sub\subseteq mask}a[sub],$$

其中 $a[mask]$ 表示 $mask$ 的贡献。注意，这里的 $a$ 与整个集合 $mask$ 有关，所以不能够直接分别对于每个元素统计它对于所有包含它的 $mask$ 的 $a$ 的贡献。

设 $dp[mask,i]$ 表示只考虑 $mask$ 的后 $i$ 位的子集、而剩下的位全部取的贡献之和，则显然 $f[mask]=dp[mask,n]$。此外，有转移

$$dp[mask,i]=\{\begin{array}{ll}dp[mask,i-1]& mas{k}_i=0\\ dp[mask,i-1]+dp[mask\oplus 2^i,i-1]& mas{k}_i=1\end{array}$$

如果把 $i$ 作为外层的循环变量，则可以用滚动数组把空间优化到 $O(2^n)$。

for (int i = 0; i < n; ++i) {
    f[i] = a[i];
}
 
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)];
        }
    }
}

参考资料： 【DP】解析 SOSdp（子集和 dp）