状态压缩

by TheBigYellowDuck

题单：https://www.luogu.com.cn/training/327231#information

感觉题目都不是很简单，大部分都写了题解。

前置知识

在进行抽象的搜索的时候，我们要研究状态的表示，有时就需要用状态压缩后的二进制数表示状态或者表示状态的某一维。

利用二进制数，可以方便地进行状态之间的转移。

状态压缩往往复杂度很高，只能解决小数据的问题，所以其实更多时候是从数据范围判断出来要用状压的。

状态压缩的循环顺序天然满足转移的拓扑序。也就是说，当前想更新状态 $S$ 的答案时，$S$ 的子集 $S'$ 一定要先被更新完成，而由于 $S\geq S'$，所以自然成立。

状态压缩常用的一些二进制技巧：

• $S$ 的第 $i$ 位：S >> i & 1

• $S$ 中的最小值：lowbit(S) = S & -S

• $T$ 与 $S$ 的交集：T & S

• $T$ 与 $S$ 的并集：T | S

• $T$ 在 $S$ 中的补集：T ^ S

• 在 $S$ 中加入元素 $j$ ：S |= (1 << j)

• 在 $S$ 中删除元素 $j$ ：S ^= (1 << j)

• 枚举 $S$ 的子集：for (int j = S; j; j = (j - 1) & S)

Problem 1

在 $n\times n$ 的棋盘上恰好放 $k$ 个国王，使他们互不攻击，求方案数。

数据范围：$n\leq 9$，$k\leq n\times n$。

Sol

国王能攻击到的范围很少，下一行的状态只受上一行的影响。

设 $f(i,j,S)$ 表示第 $i$ 行状态为 $S$，且前 $i$ 行一共放了 $j$ 个国王的方案数。

转移枚举第 $i-1$ 行的状态，判断有没有冲突即可。同时 $S$ 自身不能有相邻元素。

时间复杂度 $\mathcal{O}(nk4^n)$。

题目来源：SCOI2005 互不侵犯。

Problem 2

长度为 $n$ 的序列有且仅有 $m$ 种不同的元素，我们希望通过操作让同种元素连续。

定义一次操作为：

• 选取 $1\leq i_1<i_2<i_3<\dots<i_k\leq n$。

• 以任意顺序重排 $\{i_k\}$ 为 $\{i'_k\}$。

• 对于任意 $1\leq j\leq k$，令 $a_{i_j}$ 赋值为 $a_{i'_j}$。

若只能进行一次操作，求最少选出元素的数量，即上述 $k$ 的最小值。

数据范围：$n\leq 10^5$，$m\leq 20$。

Sol

发现同种元素之间的排列不影响答案，不妨将已经排好的元素全都放在队首。

记 $c_j$ 为元素 $j$ 的个数，$s(j,i)$ 为元素 $j$ 在前 $i$ 个数中的出现次数。

设 $f(S)$ 为队首已经排好的元素种类为 $S$ 的答案。设 $L=\sum\limits_{j\in S} c_j$，即队首 $L$ 个元素已经排好。

枚举排在末尾的一组，设为 $j$，则排好这些元素需要区间 $[L-c_j+1,L]$ 内不是 $j$ 的元素全部出队，代价为 $c_j-[s(j,L)-s(j,L-c_j)]$，排之前的状态 $S'=S-\{j\}$。

转移方程为

$f(S)=\min\limits_{j\in S}\{f(S')+c_j-s(j,L)+s(j,L-c_j)\}$

时间复杂度 $\mathcal{O}(nm+m2^m)$。

题目来源：P3694 邦邦的大合唱站队。

Problem 3

求 $n$ 个点 $m$ 条边的简单无向图的简单环的个数。

数据范围： $n\leq 19$，$m\leq\dfrac{n(n-1)}{2}$。

Sol

注意到当一个点走回自己时会产生环，而环的数量取决于一个点走回自己的路径数量。

设 $f(u,v,S)$ 为从 $u$ 到 $v$ 经过点集为 $S$ 的简单路径数量。

由于环上每一个点是等价的，这样统计会造成重复。不妨令环上的起点为 $\min\{S\}$，将状态简化为 $f(u,S)$ 为从 $\min\{S\}$ 到 $u$ 经过点集为 $S$ 的简单路径数量。

枚举与 $u$ 相连的点 $v$，分类讨论：

• 若 $v=\min\{S\}$ 且 $|S|\geq 3$，则将 $f(u,S)$ 计入答案。

• 若 $v\notin S$，则扩展状态。

注意，我们只统计从起点走回起点的环，所以 $v\in S$ 且 $v\neq \min\{S\}$ 不应该被统计。

同时注意到，每一个环会被算两次，答案需要除以 $2$。

时间复杂度 $\mathcal{O}(n^22^n)$。

题目来源：CF11D。

Problem 4

给定 $n$ 个长度相同的由小写英文字母和 ? 组成的字符串 $S_1,S_2,\dots,S_n$，求恰好和其中 $k$ 个匹配的只包含小写英文字母的字符串 $T$ 的数量。

字符串 $S_i$ 和 $T$ 匹配需要同时满足以下两个条件：

• $|S_i|=|T|$。

• $\forall 1\leq j\leq |S_i|$ 满足 $S_{ij}=\texttt{?}$ 或 $S_{ij}=T_j$。

数据范围：$n\leq 15$，$|S_i|\leq 50$。

Sol

看到数据范围显然是状压 $n$ 这一维。

设 $f(i,S)$ 为前 $i$ 位能够匹配的字符串集合为 $S$ 的 $T$ 的数量， $g(i,j)$ 为第 $i$ 位上字符 $j$ 能够匹配的字符串集合。

预处理 $g(i,j)$，枚举第 $i+1$ 位上的字符，正向转移到 $f(i+1,S\cap g(i+1,j))$ 即可。

时间复杂度 $\mathcal{O}(|\sum|m2^n)$。

? 其实没啥特殊作用，预处理 $g$ 的时候当成任意字符就行了。

题目来源：SDOI2009 Bill 的挑战。

Problem 5

给定第一象限内的 $n$ 个实数点 $(x_i,y_i)$，你需要构造 $m$ 条形如 $y_i=a_ix^2+b_ix$ 且开口向下（即 $a_i<0$）的二次函数，使得每个点都至少被某条曲线经过一次。求 $m$ 的最小值。

多组数据。

数据范围：$n\leq 18$，$0<x_i,y_i<10$，$T\leq 30$。

Sol

一个很有意思的题目。

考虑三个点确定一条抛物线，且这些抛物线必须过原点，不妨设 $h(i,j)$ 为经过第 $i$ 个点和第 $j$ 个点的合法抛物线所经过的点的集合。

设 $f(S)$ 为穿过点集 $S$ 的答案，转移需要考虑两种情况：

• 这条线穿过 $h(i,j)$ 的所有点，则由 $f(S)$ 转移到 $f(S\cup h(i,j))$。

• 这条线只能穿过一个点，则由 $f(S)$ 转移到 $f(S\cup \{j\})$。

时间复杂度 $\mathcal{O}(Tn^22^n)$，还不足以通过所有数据。

考虑一个优化，在决策时我们只考虑从未在 $S$ 中的最小点转移。由于穿过点的顺序不影响答案，这样做能减少很多重复决策，需要考虑的抛物线数从 $n^2$ 个缩减到了 $n$ 个。

最终时间复杂度 $\mathcal{O}(Tn2^n)$。

题目来源：NOIP2016 提高组 愤怒的小鸟。

Problem 6

一座桥的最大承重为 $W$， $n$ 个人想要过桥，第 $i$ 个人过桥的时间为 $t_i$，重量为 $w_i$。一批人过桥的时间为过桥时间最长的人的时间，且必须一组全部过桥另一组才能上桥。求最短过桥时间。

数据范围：$W \le400$，$n\le 16$，$t_i\le50$，$w_i\le100$。

Sol

子集枚举的经典题目。

设 $f(S)$ 为过河的人集合为 $S$ 的最短时间，枚举 $S$ 的子集，用子集的最优答案更新即可。

需要预处理集合 $T$ 的人一次过河的重量 $w'(T)$ 和时间 $t'(T)$。

转移方程为

$f(S)=\min\limits_{T\subset S}\left\{f(T)+t'\left(\complement_ST\right)\right\}\left[w'\left(\complement_ST\right)\leq W\right]$

时间复杂度 $\mathcal{O}(3^n)$。

题目来源：POI2004 PRZ。

Problem 7

对于一棵有根树，设每个节点 $u$ 连向其父亲的边的权值为 $L$，到根的路径经过的边数为 $K$，定义其权值 $w(u)=L\times K$。特别地，根节点权值为 $0$。定义这棵树的权值为 $\sum w(u)$。

给定 $n$ 个点 $m$ 条边的无向图，求其生成树权值的最小值。

数据范围：$n\leq 12$，$m\leq 10^3$，$w_i\leq 5\times 10^5$。

Sol

一道很综合的题目。

翻译一下题目，设根节点深度为 $0$，则 $K$ 的值就是节点 $u$ 的深度。

考虑一个点的权值只受到边权和深度的影响，我们把树按照深度分层，每一层的 $K$ 都相同，影响贡献的只有每个点连向父亲的边权和。

先处理这一部分。设 $f(S,T)$ 为当前已经加入生成树的点集为 $S$，想要把集合 $T$ 中的点加入生成树的边权和最小值。令 $T$ 从小到大遍历 $S$ 的补集的子集，手模一下发现这样每次只需要在之前的基础上贪心地把 $\min\{T\}$ 加入即可。

不妨考虑深度由浅入深地加点。设 $g(d,S)$ 为当前深度为 $d$，已经加入生成树的点集为 $S$ 的答案，根据前面的 $f$ 数组不难统计答案。

转移方程为

$g(d,S)=\min\limits_{T\subset S}\left\{g\left(d-1,\complement_ST\right)+d\times f\left(\complement_ST,T\right)\right\}$

最后答案为 $\min\limits_{d=0}^{n-1}\left\{g(d,U)\right\}$，其中 $U=\{1,2,3,\cdots,n\}$。

处理 $f$ 和 $g$ 的复杂度都是 $\mathcal{O}(n3^n)$，故总时间复杂度 $\mathcal{O}(n3^n)$。

题目来源：NOIP2017 提高组 宝藏。

Problem 8

$n\times m$ 的地图上有些格子是山地，有些格子是平原。只能在平原上部署炮兵。若在 $(x,y)$ 部署炮兵，则可以攻击到 $(x,y+k)$ 和 $(x+k,y)$，其中 $k\in \{-2,-1,0,1,2\}$。若希望炮兵互不攻击，求部署炮兵数量的最大值。

数据范围：$n\leq 100$，$m\leq 10$。

Sol

应该是方格表类状压 dp 中比较麻烦的一道题了。

由于当前行的状态受到前两行的影响，设 $f(i,S,T)$ 为第 $i$ 行状态为 $S$，第 $i-1$ 行状态为 $T$ 的答案。单独处理 $i=1,2$ 的情况，转移时枚举前两行的状态即可。

直接暴力枚举状态复杂度是 $\mathcal{O}(n8^m)$，不能接受。可以拿到地图先预处理出来每一行的合法状态，相当于一个剪枝。

数组不能开太大，需要滚动数组压掉 $i$ 这一维。

时间复杂度不会算。最坏应该还是 $\mathcal{O}(n8^m)$，但是远远跑不满。

题目来源：NOI2001 炮兵阵地。

Problem 9

一个长度为 $n$ 的环，第 $1$ 个围栏与第 $n$ 个围栏相邻。共有 $c$ 个小朋友，第 $i$ 个小朋友只能看到 $E_i\sim E_i+4$ 这 $5$ 个围栏里的动物（大于 $n$ 则从 $1$ 开始）。第 $i$ 个小朋友害怕的动物分别处于第 $X_{i,j}(1\leq j\leq F_i)$ 个围栏内，喜欢的动物分别处于第 $Y_{i,j}(1\leq j\leq L_i)$ 个围栏内，保证这些动物在小朋友视野内。

对于第 $i$ 个小朋友，若至少有一个其害怕的动物被移走，或至少有一个其喜欢的动物被保留，则他会感到高兴。现在移走任意个动物，求最多可以让多少个小朋友感到高兴。

数据范围：$n\leq 10^4$，$c\leq 5\times 10^4$，$E_i\leq 5$。

Sol

注意到每个小朋友能看到的动物数量很少，小朋友是否高兴只和这五个围栏移除的状态有关，考虑对这五个围栏状压。

设 $g(i,S)$ 为从第 $i$ 个围栏开始的 $5$ 个围栏状态为 $S$ 时视野恰为这 $5$ 个围栏的小朋友中高兴的个数。对于 $S$ 的每一位，$1$ 表示移除，$0$ 表示保留。

设 $f(i,S)$ 为为从第 $i$ 个围栏开始的 $5$ 个围栏状态为 $S$ 时高兴的小朋友的最大值。考虑从第 $i-1$ 个围栏转移，转移方程为

$f(i,S)=\max\{f(i-1,S')\}+g(i,S)$

其中 $S'$ 的后四位应该是 $S$ 的前四位。用一些二进制的技巧可以推过来。

最后是环的处理。可以建一个 $0$ 号围栏，枚举 $0\sim 4$ 号围栏的状态并开始转移，最后强制要求 $n\sim 4$ 的状态与 $0\sim 4$ 一样即可。因为在环上，所以 $0$ 号围栏就相当于 $n$ 号围栏。

时间复杂度 $\mathcal{O}(n+c)$，但是有状压的 $2^{10}$ 倍常数。

题目来源：APIO2007 动物园。

Problem 10

有一个 $n$ 个节点的环，节点编号按照顺时针顺序分别为 $1\sim n$，且第 $1$ 号节点和第 $n$ 号节点相邻。初始每个节点均为白色，现在要将部分节点染黑，满足任意相邻 $m$ 个节点中至多有 $k$ 个被染黑，求总方案数。

数据范围：$n\leq 10^{15}$，$m\leq 5$，$k\leq m$。

Sol

先考虑一个普通的 dp。跟上一题的思路类似。

设 $f(i,S)$ 为第 $1\sim i$ 号节点中 $[i-m+1,i]$ 被染黑的状态为 $S$ 时的答案。考虑从 $i-1$ 的状态推过来，大概就是一个错位的过程。转移方程为

$f(i,S)=\sum\limits_{S'}f(i-1,S')$

其中 $S'$ 的最后 $m-1$ 位恰为 $S$ 的前 $m-1$ 位。

对于环的处理，仍然采用同样的方法。考虑一个 $0$ 号节点，枚举 $[-m+1,0]$ 的状态并开始转移，最后强制要求 $[n-m+1,n]$ 号节点的状态与 $[-m+1,0]$ 一致。

这样做时间复杂度是 $\mathcal{O}(n4^m)$，还远远达不到要求。

面对这种巨大的数据范围，一般都需要矩阵快速幂优化。考虑构造一个转移矩阵。

抽象一下转移过程。最终的答案是 $\sum\limits_{S} f(n,S)$，而 $S$ 是由若干 $S'$ 转移过来，$S'$ 又是由若干 $S''$ 转移过来，如此循环。由于初始状态为 $f(0,S)$，所以一共会发生 $n$ 次转移。

也就是说，如果把每一个状态抽象为一个点，每个点向自己能转移到的下一个状态连边，会形成一张图，而答案就是整张图中长度为 $n$ 的路径数量。

这是一个经典问题。图上长度为 $n$ 的路径数量即为邻接矩阵 $n$ 次幂矩阵中所有元素之和。

由于进行了破环，要求起始状态和最终状态一致，也就是需要能够自己转移到自己。体现在统计答案上，只统计最后矩阵中主对角线上的元素之和即可。

时间复杂度优化到 $\mathcal{O}(8^m\log n)$。

题目来源：P1357 花园。

Problem 11

（旅行商问题）给定 $n$ 个点 $m$ 条边的有向图，求从 $1$ 号点出发恰经过每个点一次并回到点 $1$ 的最短路程。

数据范围：$n\leq 20$，$m\leq \dfrac{n(n-1)}{2}$。

Sol

经典问题。到现在才找到洛谷竟然有这道题。

图上数据范围比较小的状压题目一般直接状压点集就可以。

设 $f(S,j)$ 为经过点集为 $S$ 且当前在 $j$ 点的答案。考虑 $j$ 加入点集之前的集合 $S'=S-\{j\}$，枚举与 $j$ 相连的点 $k$ 作为上一次最后经过的点即可。

转移方程为

$f(S,j)=\min\limits_k\{f(S',k)+dis(k,j)\}$

最后还要回到 $1$ 点，设全集 $U=\{1,2,3,\cdots,n\}$，则答案为

$\min\limits_{i=1}^n \{f(U,i)+dis(i,1)\}$

时间复杂度 $\mathcal{O}(n^22^n)$。

题目来源：P1171 售货员的难题。

Problem 12

给定数字串 $T$ 和整数 $m$，求能被 $m$ 整除的 $T$ 的排列个数。

$\text{Version 1}$：可以有前导 $0$。$|T|\leq 10$，$m\leq 1000$。

$\text{Version 2}$：不可以有前导 $0$。$|T|\leq 18$，$m\leq 100$。

Sol

可以有前导 $0$，相当于 $0$ 的地位和其他数字是一样的。

下面令 $n=|T|$。

设 $f(S,i)$ 为已选的数字下标集合为 $S$ 且模 $m$ 的余数为 $i$ 的方案数。考虑从末尾接入新数字 $j$，集合变为 $S\cup \{j\}$，模 $m$ 的余数变为 $(10\times i+j)\bmod m$，正向转移即可。

注意到相同数字的地位是相同的，而按照上面的方式计算会有重复。设 $c_i$ 为数字 $i$ 在原串中的出现次数，则排列中数字 $i$ 会被重复计算 $c_i!$ 次。设全集 $U=\{1,2,3,\cdots,n\}$，则最后答案为

$f(U,0)\times\prod\limits_{i=0}^9\dfrac{1}{c_i!}$

时间复杂度 $\mathcal{O}(nm2^n)$。

考虑不能有前导 $0$ 的情况。发现是否有前导 $0$ 只由最高位上是否为 $0$ 决定。

状态设计不变，考虑把加数的过程倒过来，变为从开头接入新数字 $j$。此时集合变为 $S\cup \{j\}$，模 $m$ 的余数变为 $\left(i+j\times 10^{|S|}\right)\bmod m$。

这样只需要用总方案数减去最后一次在开头接入了 $0$ 的方案数，就可以得到不含前导 $0$ 的答案。时间复杂度显然不会改变。

$\text{Version 1}$：SCOI2007 排列

$\text{Version 2}$：CF401D。