状压 dp 及相关技巧归纳

· · 个人记录

平凡状压 dp

笼统的来讲，对于一些复杂度要求不高的 dp，我们的状态可以设计的较为复杂，达到指数量级，而这样的 dp 维数一般不低，转移处理起来较为复杂，复杂度高。我们考虑把这些状态按位压缩成一个数，拿常数较小的位运算来处理这些状态的变换，降低复杂度和处理难度。

具体的讲，如题：

此题有较小的数据范围 1\leq N,M\leq 12，那么我们可以考虑指数级的状态.

考虑暴力计算，枚举后判断是否合法有 O(2^{NM}NM) 的暴力，而对对枚举加以约束，仅枚举合法状态，则有 O(2^{NM}) 的暴力，依然无法通过。

那么复杂度瓶颈在哪里呢？我们考虑填一个位置判断是否合法的相关参数只有左侧相邻的格子是否填和上侧格子是否填，对于一行来说判断是否合法来说只需要知道这一行填了什么和上一行填了什么，需要的信息量是 O(2^{2N}) 的，而直接暴力却用了 O(2^{NM}) 的信息量。

我们考虑按行填和计算方案，把行状态压缩起来，那么我们求第 i 行填 T 且合法时有多少方案时只需要知道，对于所有合法的 S，满足前 i-1 行合法，且第 i-1 行填 S 的方案数，和相邻两行分别填 S 和 T 是否合法即可。

那么状态怎么设计呢？不妨把 S 二进制下的第 i 位设为行中这位是否能被选中，那么我们得到了一个状态数为 O(2^NM) 的 dp：dp_{i, S} 表示填完前 i 行，第 i 行填 S 且整体合法的方案数有多少，设 U_i 为行内合法的第 i 行放置情况集合，g(S,T) 当且仅当 S,T 两行相邻放置合法时为真，那么答案为：

\sum _{S\in U_M}dp_{M, S}

转移有：

dp_{i, S}= [S\in U_i]\sum_{T\in U_{i-1}\land g(S,T) } dp_{i-1, T} 则最终复杂度为 $O(2^NM \times 2^N)$，可以通过本题。 其他类似的平凡状压 dp 题目与本题本质相同，不再赘述. **图论平凡状压 dp** 显然状压还可以压缩一些图的点集，那么还能做一些东西。 + [P1171 售货员的难题](https://www.luogu.com.cn/problem/P1171) 还是从暴力的过程进行思考，假若我们暴力枚举排列计算，那么存在 $O(n!)$ 的做法，显然无法通过，考虑依次选点的过程，这样做冗杂的信息则是已选点集合的顺序性。显然我们只需要知道选了谁和最后一个选的是谁，和已经选的集合即可，这样单次的信息量从 $O(n!)$ 则降到了 $O(2^n)$。 考虑 $dp_{i, S}$ 表示已经选了的集合是 $S$，最后一个选的点是 $i$ 的最小总路程，那么转移： $$dp_{i, S}=\sum_{j \in S} dp_{j, S/i} + dis_{j, i}$$ 复杂度 $O(2^nn^2)

图的连通性

给出一个 n 个点 m 条边的无向图 G，求有多少种边集满足删掉集合中的所有边，这张图还是联通的。

设 f(S) 表示仅考虑点集 S，边集为 G 中 S 之间的边的子图的答案，考虑怎么转移，正着考虑如何组出联通图难以划分和计数，正难则反，考虑对不联通的方案计数，枚举 S 一个极大联通子图 T，显然 T 与 S/T 之间的边必删，T 内的边随意删或不删都可以，这样就保证了 S 一定是不联通的，则有：

f(S) = 2^{cnt_S} - \sum _{T\subset S} f(T) \times 2^{cnt_{S/T}}

考虑这个式子会计重，每种不联通图会计其联通块个数次，那么不妨强制枚举的联通块包含 1，则不会计重：

f(S) = 2^{cnt_S} - \sum _{1\subseteq T\subset S} f(T) \times 2^{cnt_{S/T}}

例题：[ABC213G] Connectivity 2

边双联通分量

给出 n 个点边带权的完全图 G，求出权值最小的边双子图。

考虑如果进行一次 dfs 求出一颗生成树，那么其中的非树边必返祖且覆盖了所有树边。

从图中随意选出一个非树边，把这个非树边与树边的构成的环单独做一个集合，并从这个链开始向外选择集合，具体的，假如已经选择的点与环 x 有交，则可以选择环 x上没有覆盖的那部分作为新集。那么除了第一个指定的环，其他集相比其对应的环一定是不完全的，而又因为这样的扩散式的选法得到选出的集必然是连续的，所以这些集在图上一定是链状的。

对于任意边双联通图来说，必然可以被这样的分解方法完全分解；而按这样分解方法，若干个环组成的图必然是一个边双联通图，则我们反向构造所有能被这样分解的图，其中边权和的最小值就是所有全点集双连通子图中边权和的最小值。

这样的分解方法即为耳分解，分出来的集即为去头去尾的耳。

考虑每次转移加入一个耳，再维护点和集连边的最大值和次大值，有 O(3^n n^2) 的做法，不再赘述，而维护枚举耳当前起点终点，依次枚举点加入耳，有 O(2^n n^3) 的做法：

设 f_{S,i} 是已选点集为 S，有一个起点为 i，终点为 j 的耳还未填充时边权和的最小值，g_{S} 是已选点集为 S，所有耳已选好时边权的最小值，e_{S,i,j} 为选两条边，分别从 i, j 出发到达 S 内点的不同的两边边权和的最小值，有：

f_{S,i,j}=\min(g_{S/\{i,j\}} + M_{S,i,j}, \min_{k\in S/\{i,j\}}(f_{S/\{i\},k,j}+ dis_{k,i})] g_{S}=\sum_{i\in S} f_{S,i,i}

初始仅选一个点即可，剩下的都为耳。

仙人掌

考虑钦定点 1 为这个树的根，假若把无向边连接的两点看作一个二元环，那么按 1 同时处于的若干个环就可以把图分成若干个除 1 外无交的子仙人掌。

设 f_{S,i} 为以 i 为根，点集为 S 时构成仙人掌的方案数，g_{S, i} 为以 i 为根，划分后 i 的一个子仙人掌点集为 S 的方案数，f 与 g 的关系就是一个类似子集卷积的形式。

考虑如何算 g_{S,i}，显然此时 i 上仅仅只能挂一个环，那我们考虑维护环点集，起点与终点，每次加点时加入环上以环上点为根的一个子仙人掌即可，设其为 h_{S,i,j}，用 f 转移即可。

假若我们把边当做二元环特殊处理，那么 g_{S,i} = h_{S,i,i}，只需在转移 h_{S,i,j} 时注意转移到 i =j 的情况时不会有新贡献产生。

不过转移时可能会计重，比如三元及以上的环环会对称的计重一次，那么把二元环单独出来，其他除 2 即可。

DAG

习题

题目来源：iee 推的状压 dp list

考虑从前往后添加字符串，设 ( 为 1，) 为 -1，则要求的即为前缀里前缀和非负且前缀和为 0 的位置数最大值。

考虑选好了若干个数，会影响后面前缀的只有权值和和是否存在前缀和非负的前缀， 维护 dp_{S,p} 表示 S 中的字符串已经被选，和为 p，每次造成负前缀和或选完时对答案贡献即可，考虑如何转移：

f_{S,p}=\max_{i\in S} \{f_{S/i,sum_{S/i}} + calc(i,sum_{S/i})\}[min_S +sum_{S/i} \geq 0]

其中 calc(i, x) 代表给字符串 i 的前缀和同时加 S，在出现负数前有多少 0，即我们要维护的就是查某个字符串某个前缀有多少某个数。离线下来，维护一个桶表示前缀内的出现次数，那么能做到 O(2^nn + L) 预处理，暴力转移即可。

简单题，直接维护 dp_{i,S} 表示选到 i，选手位置 S 内的已经被选的最大能力值。剩下的问题就是考虑如何求未选的 kth 和。naive 的做法是转移过程中每个状态维护一个当前未选的 kth，则 i 不选选手时只会更新 kth 中比 a_i 小的数，那么按 a_i 从大到小排序，则 kth 转移时一定不会删数，只会添加。

dp_{i, S} = \max[ \max_{j\in S} (dp_{i, S/j} + s_{i,j}), dp_{i-1,S}+ a_i[i-|S|\leq k]]

设 dp_{S,T} 表示已选点集为 S，叶子集为 T 的方案数，从上往下加边，发现有重，则强制给定一个加边顺序，不会计重，复杂度 O(3^nn^2)。

考虑优化，我们有单次 O(n^3) 的矩阵树定理，则钦定 S 中的点都是叶子上的点，对于 S 外的点我们跑一个矩阵树定理对生成树个数进行计数，然后再在这两个集合间任意连边即可。

显然这个东西就是个经典集合容斥的形状，很好处理，复杂度 O(2^n n^3)

集合幂级数还有 O(2^n n^2) 做法，在此不涉及。

一眼单调，二分答案为 len，考虑如何判断是否可行。

比较平凡的做法是设 dp_{n,S} 为只考虑前 n 位是否能使 S 中字母都有长至少为 len 的子串，则我们有 O(n2^kk) 的做法，显然无法通过。

dp 状态数是 O(n2^k) 的一定不可行，且 dp 维护的信息量过少，考虑把状态里的东西塞进 dp 里维护：设 dp_S 为 S 最小的前缀满足可以使 S 中的字母都有长度至少为 len 的子串。

那么我们预处理一个自动机形状的东西，转移 \delta(x,c) 表示从 x 开始至少需要多少位能得到一个长为 len 的连续 c 子串，则 O(nk) 递推即可，而 dp 的转移更为简单，每个 dp 值对应自动机上一个点，在自动机上转移即可，有：

dp_{S} =\min_{i\in S} (\delta(dp_{S/i},i))

考虑只能按行转移，把每一行相同的打包成一个集合处理，选使这一个集合相互独立，则一定是改掉除了价值最大那一位外其他位，另一种方法为则是单独改掉一位。

则存在至多 O(nm) 个集合，有 O(2^nnm) 的做法，依旧无法通过。

因为最终状态一定，考虑我们强制给定一个转移顺序，在 S 状态往外转移时，只考虑 mex(S) 相关的转移，那么单次转移只会存在 O(m) 个集合，总复杂度 O(2^nm)，可以通过。

考虑对于 G_{a_i,a_j} =0 的 i,j 来说，如果 i,j 未删去，a[i+1,j-1] 里的字符不能都删去，对于这样不合法的集合，我们可以通过高维前缀和，高维前缀差分处理出。

则我们需要找出来最大的集合，满足存在一种操作序列，依次删除每一位这些集合都是合法的，定义 f_S =0/1 为 f_S 是否合法，则：

g_S = \max_{i\in S}(f_{S/i} \times g_{S/i}) ans = n- \max_{f_{S} \land g_{S}} |\{a_i| a_i\in S\}|

很厉害的题。

考虑设 f_S 为剩下人的集合为 S 的概率，显然此时能缩减 S 的题都还未出现，不会缩减 S 的题对 f_S 的转移没有影响，考虑枚举能缩减 S 的集合 T，则有转移：

\frac{f_{S}}{cnt_T}\to f_{S\cap T}

复杂度 O(2^n\times 2^n)=O(4^n)，考虑优化枚举过程，转移式相关的只有 cnt_T 和 S\cap T，而 S\cap T 一定是 S 的子集，的总数是 3^n 的。

考虑统计 g_{S,U} 表示题目中满足 S\cap T=U 的本质不同 T 的个数，那么直接枚举 U 前面那个式子就是 O(3^n) 的了。

考虑 g_{S,U} 的转移，要求做到 O(1)，枚举一个 S/U 中的元素 x 删去，则有：

f_{S,U} = f_{S/x,U} - f_{S,U\cup x}

其中：f_{S,S} 需要一个高维前缀和算出，总复杂度 O(3^n+2^nn)

而看了 AW 的题解，有一个更好一点的，枚举一个 S 外的元素 x，则有：

f_{S,U}=f_{S\cup x, U\cup x} +f_{S\cup x, U}

这个就不用高维前缀和了。

参考资料

Para: 图论状压

Mackerel_Pike: 一类图论相关的状压 DP 题的常见解法