\(\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_{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\),其中
若每一维的大小为 \(2\),则可以状态压缩,然后用 \(\text{SOSDP}\) 来做。