SOSDP

\(\text{SOSDP: Sum over Subsets DP}\)

例子：给定一个序列长度为 \(2^n\) 的序列 \(a\)，求对于 \(i = 0,1,\cdots,2^n-1\) 求 \(A_i\)，其中 \(A_i = \sum\limits_{j\&i=j}a_j\)，即 \(i\) 的子集和。

设 \(f_{i,s}\) 表示 \(s\) 的前 \(i+1\) 个低位子集的和，有：

\[f_{i,s} = \begin{cases} f_{i-1,s}, & (s>>i)\&1=0\\ f_{i-1,s} + f_{i-1, s \oplus 2^i}, & (s>>i)\&1=1 \end{cases} \]

初始化 \(f_{0, i} = a_i + a_{i\oplus 1}\)。时间复杂度 \(O(n2^n)\)，空间复杂度 \(O(n2^n)\)

rep(i, 1, 1 << n) f[0][i] = a[i] + a[i ^ 1];
rep(i, 1, n - 1) rep(j, 0, (1 << n) - 1)
{f[i][j] = f[i - 1][j];if((j >> i) & 1) f[i][j] += f[i - 1][j ^ (1 << i)];
}

\(f_i\) 的转移只和 \(f_{i-1}\) 有关，考虑优化掉这一位。

当 \((s>>i)\&1=1\) 时，\(s \oplus 2^i < s\)，可以将 \(s\) 这一维倒序枚举：

rep(i, 0, 1 << n) f[i] = a[i];
rep(i, 1, n) per(j, 0, (1 << n) - 1) if((j >> i) & 1) f[j] += f[j ^ (1 << i)];

再仔细想一下，在第 \(i\) 轮时，\(f_j\) 都是由 \(f_{j\oplus 2^i}\) 转移来的，更新为第 \(i\) 层的 \(f_j\) 的 \(j\) 的第 \(i\) 位都是 \(1\)，第 \(i-1\) 层的 \(f_{j\oplus 2^i}\) 的 \(j\oplus 2^i\) 的第 \(i\) 为都是 \(0\)。所以正序枚举 \(j\) 也是可以的。

rep(i, 0, 1 << n) f[i] = a[i];
rep(i, 1, n) rep(j, 0, (1 << n) - 1) if((j >> i) & 1) f[j] += f[j ^ (1 << i)];

时间复杂度 \(O(n2^n)\)，空间复杂度 \(O(2^n)\)

以上是求 \(i\) 的子集的和，要是求超集，可以把二进制的 \(0\) 看做 \(1\)，\(1\) 看做 \(0\) 来做一次 \(DP\)：

rep(i, 0, 1 << n) f[i] = a[i];
rep(i, 1, n) rep(j, 0, (1 << n) - 1) if(!((j >> i) & 1)) f[j] += f[j ^ (1 << i)];

\(\text{SOSDP}\) 与高维前缀和的关系：

给定 \(n\) 维序列 \(a\)，求所有 \(S\)，其中

\[S_{i_1,i_2,\cdots,i_n} = \sum\limits_{j_1\le i_1,j_2\le i_2,\cdots,j_n\le i_n}a_{j_1,j_2,\cdots,j_n} \]

若每一维的大小为 \(2\)，则可以状态压缩，然后用 \(\text{SOSDP}\) 来做。