前言

考前来复习下，突然发现状压忘得比较干净，赶紧来把笔记写了。

前置知识

位运算，DP。

概念

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。

直接这么说不太好理解。

我们直接上例题。

例 1：AtCoder dp contest problem O-Matching

题目大意：给定 $n$，表示有 $n$ 个男生和 $n$ 个女生。对于给定的矩阵 $a$，如果 $a_{i,j}=1$，说明男生 $i$ 和女生 $j$ 可以配对，否则不能。求出配出 $n$ 对的方案数，答案对 $10^9+7$ 取模。

数据范围：$1\le n\le 21,a_{i,j}\in\{0,1\}$。

对于这道题，如果我们去爆搜，肯定是过不去的。

但由于本题的 $n$ 较小，且对于每个人来说状态都只有 $0$（不选）和 $1$（选）两种，所以我们考虑状压 DP。

设 $dp_{i,k}$ 表示前 $i$ 个男生中配对情况为 $k$ 时的方案数。

假设当前在考虑 $i,j$ 的配对，那么我们可以得到这样的转移：

$dp_{i,k \And 2^j}=\begin{cases} dp_{i,k \And 2^j}+dp_{i-1,k} & a_{i,j}\ \land \ (\left\lfloor \frac{k}{2^j}\right\rfloor \And 1=0) \\ dp_{i,k\And 2^j} & \text{otherwise.} \end{cases}$

时间复杂度看上去是 $O(n^2\times 2^n)$ 的。但事实上有很多无效状态是没有枚举的。时间复杂度为 $O(n\times 2^n)$。

同时我们注意到转移之和前一位有关。所以我们采用滚动数组优化。空间复杂度为 $O(2^n)$。

参考代码：

#include<bits/stdc++.h>

using namespace std;
const int Mod = 1e9 + 7;
int n, a[22][22];
int dp[2][1ll << 21];
int main(){
  cin >> n;
  for (int i = 1; i <= n; i++){
    for (int j = 0; j < n; j++){
      cin >> a[i][j];
    }
  }
  dp[0][0] = 1;
  for (int i = 1; i <= n; i++){
    for (int j = 0; j < n; j++){
      if (!a[i][j]){
        continue;
      }
      for (int k = 0; k < (1 << n); k++){
        if (dp[(i - 1) % 2][k] && ((k >> j) & 1) == 0){
          dp[i % 2][(k | (1 << j))] = (dp[i % 2][(k | (1 << j))] + dp[(i - 1) % 2][k]) % Mod;
        }
      }
    }
  }
  cout << dp[n % 2][((1 << n) - 1)];
  return 0;
}

总结一下，当一道题的状态涉及到进制或者单点状态数量少，且数据范围小（通常在 $20$ 以内）的时候，我们就可以考虑状压 DP。同时，一些题目的部分分也可能可以用状压 DP 写。

由于状压 DP 涉及到位运算，所以一般来说下标从 $0$ 开始会更好写。

例 2：CSES-Hamiltonian Flights

CSES 国内无法直接访问，可以去 VJudge 上交题。

题目大意：$m$ 条单向航线连接着 $n$ 座城市。你想要从第一座城市出发，经过每座城市恰好一次后，抵达第 $n$ 座城市。求出可以选择的线路数量，答案对 $10^9+7$ 取模。

数据范围：$2\le n\le 20,1\le m\le n^2,1\le u,v\le n$。

同样使用状压 DP。

设 $dp_{i,k}$ 表示当前在城市 $i$ 时，经过每个城市的状态为 $k$。

假设现在要走一条 $i\to v$ 的路，不难想到转移如下：

$dp_{v,k\And2^v}=\begin{cases} dp_{v,k\And2^v}+dp_{i,k} & \left\lfloor \frac{k}{2^v}\right\rfloor \And 1=0 \\ dp_{v,k\And2^v} & \text{otherwise.} \end{cases}$

时间复杂度为 $O(n^2\times 2^n)$，会超时。

我们可以发现：当 $dp_{i,k}=0$ 的时候，此时去进行转移是没有意义的。那么我们可以限制只有 $dp_{i,k}\ne0$ 的时候才进行转移。

优化后的时间复杂度为 $O(n\times 2^n)$。

空间复杂度为 $O(n\times 2^n)$。

参考代码：

#include<bits/stdc++.h>

using namespace std;
const int Mod = 1e9 + 7;
int n, m, dp[22][(1 << 21)];
vector<int> a[22];
int main(){
  cin >> n >> m;
  while (m--){
    int u, v;
    cin >> u >> v;
    a[u - 1].push_back(v - 1);
  }
  dp[0][1] = 1;
  for (int k = 0; k < (1 << n); k++){
    for (int i = 0; i < n; i++){
      if (dp[i][k]){
        for (auto v : a[i]){
          if (((k >> v) & 1) == 0){
            dp[v][(k | (1 << v))] = (dp[v][(k | (1 << v))] + dp[i][k]) % Mod;
          }
        }
      }
    }
  }
  cout << dp[n - 1][(1 << n) - 1];
  return 0;
}