插头 DP 学习笔记

算法简介

插头 DP 常用于网格图的 DP 中。其核心在于设计如下几部分：

• 分界线的设置。
• 插头状态的定义。
• 合并和延伸插头的转移。

其中，分界线的设置其实规定了 DP 转移的顺序，区别于状压 DP，插头 DP 通常是对每个格子而非整行转移；而插头状态的定义则代表着转移过程中前驱状态对后继的影响。合并插头时常常会进行大量的分类讨论，所以代码难度很大，需要特别注意细节，建议在纸上写好再来写 DP。

为了转移能顺利进行，分界线上应当存储了转移所需的全部信息，这也正是插头的作用。

在此基础上，我们还可以提出一种更广义的插头，也就是在前驱状态钦定一些东西需要在后继状态满足。

2. 例题

其实我感觉插头 DP 拿哈密顿回路计数作为模板有点不合理，本质上哈密顿回路计数是插头 DP 的一个高级应用，要用到哈密顿回路的括号表示来设计状态，这并不是显然的，且没有什么拓展性。个人认为 2.3 才是插头 DP 更简单的一个应用。

2.1 P5056 【模板】插头 DP

考虑用括号表示法刻画“哈密顿回路”的限制。具体而言，如下图所示，以中间绿色的分界线把哈密顿回路切开，然后考虑分界线上方部分的切面。

显然，分界线上方的哈密顿回路分别构成了若干个连通分量，且每个连通分量均为链的形式。我们将链左端的切面转化为左括号 ((，将链右端的切面转化为右括号 ))，其余切面转化为占位符 ##。那么图中的哈密顿回路的上半部分就可以用 (#(##))##(#(##))## 表示。（一个连通分量列数更小的端点为左括号，列数更大的端点为右括号）

分界线上每个切面的状态就称为插头。因为当转移到 (x,y)(x,y) 时，分界线只有两个拐点，且都在 (x,y)(x,y) 处，所以我们称 (x,y)(x,y) 水平方向的切面为下插头，竖直方向的切面为右插头。

容易发现，哈密顿回路能用括号序列来刻画，关键就在于任意两个连通分量的端点不会相交。这和括号匹配的性质恰好吻合。

而带占位符的括号序列可以使用三进制数来表示。为了减小常数，我们将三进制数按照四进制数来存储，因为二的正整数次幂作为进制可以使用位运算优化常数。但是有一个新的问题：转化为四进制数后，状态的值域过大。此时可以使用哈希表来存储状态。

设计插头 DP 为：dpx,y,Sdpx,y,S​ 表示当前考虑到位置 (x,y)(x,y)，分界线的插头状态为 SS 的方案数。

接下来考虑转移。外层肯定是依次枚举位置 (x,y)(x,y)，重点在于内层转移。

首先障碍格的转移在判断合法性后直接继承即可。其余格子在转移的时候需要对右插头、下插头的括号类型进行分类讨论：

• 无右插头，无下插头：因为每个非障碍格都必须铺，所以需要新建一个连通分量——右插头是左括号，下插头是右括号。
• 有右插头，无下插头：右插头的括号类型不变，可以选择向右延伸或拐弯向下。
• 无右插头，有下插头：下插头的括号类型不变，可以选择向下延伸或拐弯向右。
• 有右插头，有下插头：此时会对两个连通分量进行合并，需要对两个插头的类型分类讨论。
  • 右插头是左括号，下插头是右括号：因为括号匹配不能相交，此时右插头与下插头一定处于同一连通分量中，能够转移的充要条件是该格子是最后一个可转移的格子。
  • 右插头是右括号，下插头是左括号：直接合并，消去两插头的括号，其余插头的括号不变。
  • 右插头是左括号，下插头是左括号：消去两插头的括号后，修改下插头所在连通分量的右括号为左括号。
  • 右插头是右括号，下插头是右括号：消去两插头的括号后，修改右插头所在连通分量的左括号为右括号。

注意，换行的时候需要将所有状态集体左移 22 位（对应着四进制下左移 11 位），以匹配新的分界点形态。同时在插头延伸的时候需要判断延伸的方向是否有障碍，否则在进行换行的时候会引发错误。

其中，最后两种情况的分类讨论可以画图进行理解。而后两种的转移则需要用到括号串 ±1±1 转化的性质去做。

如图所示，这是“右插头是右括号，下插头是右括号”情况的解释。

时间复杂度 O(nm3n)O(nm3n)。

一些有关代码的技巧：

• 用哈希表来存储 DP 的状态，然后遍历哈希表中的每一个元素进行刷表法转移。
• 当遍历到 (x,y)(x,y) 时，(x,y)(x,y) 的右插头对应着四进制数的第 y−1y−1 位，而下插头对应着四进制数的第 yy 位。

#include <bits/stdc++.h> #include <bits/extc++.h> #define fi first #define se second #define eb(x) emplace_back(x) #define pb(x) push_back(x) #define lc(x) (tr[x].ls) #define rc(x) (tr[x].rs) using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ldb; typedef __int128 i128; using pi = pair<int, int>; const int N = 15, M = 2e6; struct HashTable{ int B = 1999993, h[M], id[M], idx, ne[M]; ll val[M]; void clear() { memset(h, 0, sizeof(h)); for(int i = 0; i <= idx; i++) { val[i] = id[i] = ne[i] = 0; } idx = 0; } void insert(int st, ll v) { for(int i = h[st % B]; i ; i = ne[i]) { if(id[i] == st) { val[i] += v; return; } } val[++idx] = v; id[idx] = st; ne[idx] = h[st % B]; h[st % B] = idx; } } dp[2]; int n, m, a[N][N], ex, ey; int bit[N], bas[N]; int main() { //freopen("sample.in", "r", stdin); //freopen("sample.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // Input cin >> n >> m; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { char c; cin >> c; if(c == '.') { ex = i, ey = j; a[i][j] = 1; } } } // Init for(int i = 0; i < N; i++) { bit[i] = (i << 1); bas[i] = (1 << bit[i]); } // DP int now = 0, pre = 1; dp[now].insert(0, 1); ll ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= dp[now].idx; j++) dp[now].id[j] <<= 2; for(int j = 1; j <= m; j++) { swap(now, pre); dp[now].clear(); for(int k = 1; k <= dp[pre].idx; k++) { int st = dp[pre].id[k]; ll val = dp[pre].val[k]; int rht = (st >> bit[j - 1]) & 3; int dwn = (st >> bit[j]) & 3; if(!a[i][j]) { if(!rht && !dwn) dp[now].insert(st, val); } else if(!rht && !dwn) { if(a[i + 1][j] && a[i][j + 1]) dp[now].insert(st | (1 << bit[j - 1]) | (2 << bit[j]), val); } else if(!dwn) { if(a[i][j + 1]) dp[now].insert(st + rht * (bas[j] - bas[j - 1]), val); if(a[i + 1][j]) dp[now].insert(st, val); } else if(!rht) { if(a[i + 1][j]) dp[now].insert(st + dwn * (bas[j - 1] - bas[j]), val); if(a[i][j + 1]) dp[now].insert(st, val); } else { if(rht == 1 && dwn == 2) { if(i == ex && j == ey) ans += val; } else if(rht == 2 && dwn == 1) { dp[now].insert(st - rht * bas[j - 1] - dwn * bas[j], val); } else if(rht == 1 && dwn == 1) { int sm = 0, vst = st - rht * bas[j - 1] - dwn * bas[j]; for(int p = j; ; p++) { int typ = (st >> bit[p]) & 3; if(typ == 1) sm++; else if(typ == 2) sm--; if(sm == 0) { vst -= bas[p]; break; } } dp[now].insert(vst, val); } else if(rht == 2 && dwn == 2) { int sm = 0, vst = st - rht * bas[j - 1] - dwn * bas[j]; for(int p = j - 1; ; p--) { int typ = (st >> bit[p]) & 3; if(typ == 1) sm++; else if(typ == 2) sm--; if(sm == 0) { vst += bas[p]; break; } } dp[now].insert(vst, val); } } } } } cout << ans; return 0; }

拓展：如果题目中不限制一个哈密顿回路，而是可以有多个哈密顿回路的话，就不用记录每个括号到底是左还是右了，因为不需要区分合并时是否形成回路。可以用二进制状压存储括号的存在性，达到 O(nm2m)O(nm2m) 的复杂度。

2.2 P2289 [HNOI2004] 邮递员

下文中称行数为 nn，列数为 mm，与题目中的定义相反。

考虑观察题目中回路的形态：

• 当 n=1n=1 或 m=1m=1 时，此时图的形态是一条链，因此从 (1,1)(1,1) 走到头之后再走回来即可。方案是唯一的，因此答案为 11。
• 当 n,m>1n,m>1 时，由于保证了 n×mn×m 是偶数，所以 n,mn,m 中必然有一个数为偶数。我们一定可以构造出一条长度为 n×mn×m 的路径，且此时显然已经达到了答案的下界。
  • 假设 nn 为偶数。我们从 (1,1)(1,1) 开始先向下走一格抵达 (2,1)(2,1)，然后向右走到 (2,m−1)(2,m−1)，向下走到 (3,m−1)(3,m−1)，向左走到 (3,1)(3,1)，如此往复走 S 形路线，在走到最后一行后沿着最后一列回到第一行即可。
  • 当 mm 为偶数的时候同理，走竖向的 S 形路线即可。

因此当 n,m>1n,m>1 的时候路线的长度（边数）一定得是 n×mn×m。又由于三角形斜边长度大于直角边，所以不能斜着走。容易发现这就是让我们数有多少个有向哈密顿回路，可以直接套用 2.1 的做法，最后答案乘个 22。时间复杂度 O(nm3n)O(nm3n)。

注意答案是个很大的数，需要使用__int128存储。

#include <bits/stdc++.h> #include <bits/extc++.h> #define fi first #define se second #define eb(x) emplace_back(x) #define pb(x) push_back(x) #define lc(x) (tr[x].ls) #define rc(x) (tr[x].rs) using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ldb; typedef __int128 i128; using pi = pair<int, int>; const int N = 30, M = 2e6; void write(i128 x) { if(x < 0) {x = -x; putchar('-'); } if(x < 10) { putchar('0' + x); return; } write(x / 10); putchar('0' + x % 10); } struct HashTable{ int B = 1999993, h[M], id[M], idx, ne[M]; i128 val[M]; void clear() { memset(h, 0, sizeof(h)); for(int i = 0; i <= idx; i++) { val[i] = id[i] = ne[i] = 0; } idx = 0; } void insert(int st, i128 v) { for(int i = h[st % B]; i ; i = ne[i]) { if(id[i] == st) { val[i] += v; return; } } val[++idx] = v; id[idx] = st; ne[idx] = h[st % B]; h[st % B] = idx; } } dp[2]; int n, m, a[N][N], ex, ey; int bit[N], bas[N]; int main() { //freopen("sample.in", "r", stdin); //freopen("sample.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // Input cin >> m >> n; if(n == 1 || m == 1) { cout << 1; return 0; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { char c = '.'; if(c == '.') { ex = i, ey = j; a[i][j] = 1; } } } // Init for(int i = 0; i < N; i++) { bit[i] = (i << 1); bas[i] = (1 << bit[i]); } // DP int now = 0, pre = 1; dp[now].insert(0, 1); i128 ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= dp[now].idx; j++) dp[now].id[j] <<= 2; for(int j = 1; j <= m; j++) { swap(now, pre); dp[now].clear(); for(int k = 1; k <= dp[pre].idx; k++) { int st = dp[pre].id[k]; i128 val = dp[pre].val[k]; int rht = (st >> bit[j - 1]) & 3; int dwn = (st >> bit[j]) & 3; if(!a[i][j]) { if(!rht && !dwn) dp[now].insert(st, val); } else if(!rht && !dwn) { if(a[i + 1][j] && a[i][j + 1]) dp[now].insert(st | (1 << bit[j - 1]) | (2 << bit[j]), val); } else if(!dwn) { if(a[i][j + 1]) dp[now].insert(st + rht * (bas[j] - bas[j - 1]), val); if(a[i + 1][j]) dp[now].insert(st, val); } else if(!rht) { if(a[i + 1][j]) dp[now].insert(st + dwn * (bas[j - 1] - bas[j]), val); if(a[i][j + 1]) dp[now].insert(st, val); } else { if(rht == 1 && dwn == 2) { if(i == ex && j == ey) ans += val; } else if(rht == 2 && dwn == 1) { dp[now].insert(st - rht * bas[j - 1] - dwn * bas[j], val); } else if(rht == 1 && dwn == 1) { int sm = 0, vst = st - rht * bas[j - 1] - dwn * bas[j]; for(int p = j; ; p++) { int typ = (st >> bit[p]) & 3; if(typ == 1) sm++; else if(typ == 2) sm--; if(sm == 0) { vst -= bas[p]; break; } } dp[now].insert(vst, val); } else if(rht == 2 && dwn == 2) { int sm = 0, vst = st - rht * bas[j - 1] - dwn * bas[j]; for(int p = j - 1; ; p--) { int typ = (st >> bit[p]) & 3; if(typ == 1) sm++; else if(typ == 2) sm--; if(sm == 0) { vst += bas[p]; break; } } dp[now].insert(vst, val); } } } } } write(2 * ans); return 0; }

2.3 P4262 [Code+#3] 白金元首与莫斯科

先考虑弱化版：如果障碍物集合已经给定，如何求出合法方案数？

我们依然考虑从左到右、从上到下依次遍历 (x,y)(x,y)，那么分界线就还是只会在 (x,y)(x,y) 处拐两次的形态。接下来尝试将 1×2,2×11×2,2×1 的方块的信息融入分界线中，显然可以记录两个单位方块之间的分界线来记录某个 1×2,2×11×2,2×1 的方块的存在性。于是分界线的状态可以压为一个 m+1m+1 位的二进制数，表示每一条分界线上是否有方块覆盖，即是否为一个多米诺骨牌的插头。

状态定义和转移都与普通的插头 DP 无异，这样做的单次时间复杂度为 O(nm2m)O(nm2m)。

回到原问题中，如果要对每个钦定为障碍物的格子都做一遍复杂度显然会爆炸。而这个问题相当于是一个“撤销单点”的模型，两种常用的思路是缺一分治和记录前后缀信息。这个问题中我们无法快速处理两个不同障碍物集合的 DP 合并，但是却能处理网格前后两部分的合并。

因此考虑“记录前后缀信息”的 trick，分别正着和倒着做一遍插头 DP，记录历史前后缀状态，在钦定撤销点的时候枚举前后缀的状态进行合并即可。这部分的时间复杂度也是 O(nm2m)O(nm2m)。

#include <bits/stdc++.h> #include <bits/extc++.h> #define fi first #define se second #define eb(x) emplace_back(x) #define pb(x) push_back(x) #define lc(x) (tr[x].ls) #define rc(x) (tr[x].rs) using namespace std; using namespace __gnu_pbds; typedef long long ll;