算法简介插头 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 pairint, 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与题目中的定义相反。考虑观察题目中回路的形态当 n1n1 或 m1m1 时此时图的形态是一条链因此从 (1,1)(1,1) 走到头之后再走回来即可。方案是唯一的因此答案为 11。当 n,m1n,m1 时由于保证了 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,m1n,m1 的时候路线的长度边数一定得是 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 pairint, 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 的方块的存在性。于是分界线的状态可以压为一个 m1m1 位的二进制数表示每一条分界线上是否有方块覆盖即是否为一个多米诺骨牌的插头。状态定义和转移都与普通的插头 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;