sosdp

零、写在前面随便写写。子集和超集和的计算就是高维前后缀和子集反演超集反演的计算就是高维前后缀差分。还是比较easy的。一、SOS DP1.1 高维前缀和SOS DP (Sum Over Subsets Dynamic Programming)也被称为高维前缀和是算法竞赛中处理位运算尤其是子集、超集问题的一项极为优雅和高效的技巧。给定一个大小为2 n 2^n2n的数组A AA下标从0 00到2 n − 1 2^n-12n−1我们需要计算一个新数组F FF使得F [ m a s k ] ∑ i ⊆ m a s k A [ i ] F[mask] \sum_{i \subseteq mask} A[i]F[mask]i⊆mask∑​A[i]注i ⊆ m a s k i \subseteq maski⊆mask表示i ii是m a s k maskmask的子集即(i mask) i1. 暴力做法O ( 3 n ) O(3^n)O(3n)最直观的做法是对于每个m a s k maskmask枚举它的所有子集for (int mask 0; mask (1 n); mask) { F[mask] A[0]; for (int i mask; i 0; i (i - 1) mask) { // 经典枚举子集位运算技巧 F[mask] A[i]; } }3. 高维前缀和O ( n ⋅ 2 n ) O(n \cdot 2^n)O(n⋅2n)思考初学算法的时候怎么求一维数组前缀和——从左往右扫一遍。怎么求二维数组前缀和不用一次遍历的容斥写法——先对每一行做一维前缀和再对每一列做一维前缀和。扩展到n维——依次对第0 00维、第1 11维、…、第n − 1 n-1n−1维做一维前缀和。状态定义d p [ i ] [ m a s k ] dp[i][mask]dp[i][mask]表示在只允许改变m a s k maskmask的前i ii位即第0 00到第i − 1 i-1i−1位的前提下所有子集的和。状态转移考虑m a s k maskmask的第i ii位如果m a s k maskmask的第i ii位是0它的子集在这一位也必须是0所以d p [ i ] [ m a s k ] d p [ i − 1 ] [ m a s k ] dp[i][mask] dp[i-1][mask]dp[i][mask]dp[i−1][mask]。如果m a s k maskmask的第i ii位是1它的子集在这一位可以是0也可以是1。因此d p [ i ] [ m a s k ] d p [ i − 1 ] [ m a s k ] d p [ i − 1 ] [ m a s k ⊕ ( 1 ≪ i ) ] dp[i][mask] dp[i-1][mask] dp[i-1][mask \oplus (1 \ll i)]dp[i][mask]dp[i−1][mask]dp[i−1][mask⊕(1≪i)]。空间优化滚动数组因为d p [ i ] dp[i]dp[i]只依赖于d p [ i − 1 ] dp[i-1]dp[i−1]我们可以省去第一维for(inti0;in;i){// 枚举维度for(intmask0;mask(1n);mask){// 枚举所有状态if(mask(1i)){// 如果第 i 位是 1F[mask]F[mask^(1i)];// 加上第 i 位为 0 的状态}}}1.2 存在性与最值问题SOS DP 不仅仅能求和只要满足结合律和交换律的操作如 max⁡,min⁡按位或/与都可以用 SOS DP。一个经典问题E. Compatible Numbers对数组中每个数A[i] 找到 一个 A[j] 使得 A[i] A[j] 0。我们利用 sosdp 求子集max然后每个数的答案就是 dp[~A[i] U]代码实现(C#)public void Solve() { int n br.ReadInt32(); int[] a br.ReadInt32(n); int U 1 (int.Log2(a.Max()) 1); int[] dp new int[U]; foreach (var x in a) { dp[x] x; } for (int i 0; i 30; i) { for (int s 1; s U; s) { if ((s i 1) 0) { dp[s] Math.Max(dp[s], dp[s ^ (1 i)]); } } } bw.AppendJoin( , a.Select(x ~x (U - 1)).Select(x dp[x] 0 ? dp[x] : -1)); }1.3 求超集题意不求子集了求超集。即F [ m a s k ] ∑ m a s k ⊆ i A [ i ] F[mask] \sum_{mask \subseteq i} A[i]F[mask]∑mask⊆i​A[i]。这个很好求就是把高维前缀和变成高维后缀和。for(int i 0; i n; i) { for(int mask (1 n) - 1; mask 0; --mask) { // 从小到大也可以 if(!(mask (1 i))) { // 重点如果第 i 位是 0 F[mask] F[mask ^ (1 i)]; // 加上第 i 位为 1 的超集状态 } } }1.4 高维差分前/后 缀和的逆运算是差分那么高维前/后缀和 的逆运算就是高维差分。在很多场景中利用高位前缀和做高维差分被称为子集反演。利用高维后缀和做高维差分被称为超集反演。以子集反演为例子集反演的过程是从“至多”到“恰好”在组合数学中我们经常会遇到两个函数f ( S ) f(S)f(S)和g ( S ) g(S)g(S)其中S SS是一个集合。假设g ( S ) g(S)g(S)表示“恰好是集合S SS”的值而f ( S ) f(S)f(S)表示“包含于集合S SS的所有子集”的值之和即“至多”是S SS。它们的关系是f ( S ) ∑ T ⊆ S g ( T ) f(S) \sum_{T \subseteq S} g(T)f(S)T⊆S∑​g(T)如果我们已知f ff数组想要反推g gg数组这就需要用到子集反演公式g ( S ) ∑ T ⊆ S ( − 1 ) ∣ S ∣ − ∣ T ∣ f ( T ) g(S) \sum_{T \subseteq S} (-1)^{|S| - |T|} f(T)g(S)T⊆S∑​(−1)∣S∣−∣T∣f(T)(其中∣ S ∣ |S|∣S∣表示集合S SS的大小即二进制中 1 的个数)。我们发现和S 相差元素为奇数那么贡献是负的偶数贡献是正的这其实就是容斥原理的应用。代码实现很简单// 初始时 F 数组里存的是 f(S) for(int i 0; i n; i) { for(int mask 0; mask (1 n); mask) { if(mask (1 i)) { // 第 i 位是 1 F[mask] - F[mask ^ (1 i)]; // 减去第 i 位是 0 的情况 } } } // 结束时 F 数组里存的就是 g(S)Q为什么代码实现中一律全是减号Asosdp 就是沿着dag求和的过程在逐层做减法的过程中自动完成了奇偶交替符号的容斥计算。一个板题D. Jzzhu and Numbers计算有多少个子集满足按位与为0这显然需要我们做超集反演。代码实现C#其中Z是取模数public void Solve() { int n br.ReadInt32(); int[] a br.ReadInt32(n); int hi int.Log2(a.Max()) 1; int U 1 hi; Z[] dp new Z[U]; foreach (var x in a) { dp[x]; } for (int i 0; i hi; i) { for (int s 0; s U; s) { if ((s i 1) 0) { dp[s] dp[s ^ (1 i)]; } } } for (int s 0; s U; s) { dp[s] ((Z)2).Pow(dp[s].Value) - 1; } for (int i 0; i hi; i) { for (int s 0; s U; s) { if ((s i 1) 0) { dp[s] - dp[s ^ (1 i)]; } } } bw.AppendLine(dp[0].Value); }