插头 dp 学习笔记 | P2289 [HNOI2004]邮递员 题解
做法
插头 dp。
这道题其实和模板题是差不多的，只是要开高精度，然后输出的时候 ans 要乘二而已。
首先分析一下题目。很容易发现，一个格子只能经过一次，要不然就不是最短路了。并且一定不会斜着走，因为三角形的两条直角边都比斜边短，“直角边+直角边”一定比“直角边+斜边”短。
注意，在本文里，我把邮筒称作“格子”。
什么是插头 dp？
插头 dp 是一种很神奇的 dp 算法，它还有另外一个大名：轮廓线 dp。顾名思义，轮廓线 dp 就是在一条叫轮廓线的线上进行 dp，而插头 dp 就是在轮廓线的概念上再引入“插头”概念的 dp。
轮廓线是什么?
当推到黄色格子时，轮廓线就是那条绿色的线。
而 dp 转移的过程，就像把轮廓线往前推一格，把它从
变成
接下来就可以去考虑黄色格子右边的那个格子（蓝色格子）啦。
什么是插头？
插头就像一根链子，把两个格子连了起来。
下图中棕色的就是插头，可以发现它们把格子连了起来
从图中可以发现，每个格子最多能有四个插头，分别指向上、下、左和右。而插头指向的格子必定会有插头指回来，所以插头是成双成对出现的。又因为路径经过格子的话一定有一个插头是进格子的，还有一个是出格子的，所以插头数只能是 2 或者 4。
又由于一个格子只能经过一遍，所以插头数只能为 2。
如何定义状态？
插头 dp 毕竟还是一种 dp，所以还得定义状态。
定义
考虑如何表示状态
看这张图，很容易发现，轮廓线会把路径切开，每条路径都会先从轮廓线下面穿过轮廓线，转一圈，再从轮廓线上面穿过轮廓线。所以对于每条路径，在轮廓线上都有两个插头，所以所有轮廓线上的插头一一匹配。
但注意，虽然经过轮廓线时方向不同，但插头的方向却都是向下或者向右！
而路径不会相交，要不然就有格子走了两遍了，所以一一匹配的两对插头一定不会相交。
“一一匹配，不会相交”你想到了什么？没错！括号匹配！
括号表示法
可以把一条路径在轮廓线上左边的插头看作左括号 (，把右边的插头看作右括号 )，那么刚才的那幅图就可以变成这样：
写出来就是:（# 表示没有交点）
(#(##))(#)看到这里你肯定会感到奇怪，为什么第二和第三个括号之间有两个 #？很简单，因为它们之间有两个插头位置！（一个下插头位置和一个右插头位置）。
到这里，我们终于可以表示状态 0/1/2 时分别表示:
这个位置没有插头/这个位置有一个左括号插头/这个位置有一个右括号插头。
由于三进制实在是太慢太慢了，所以我们采用四进制。
问题又来了，什么插头是左括号插头，什么插头是右括号插头呢？
别急，这个问题在状态转移的时候自然就会解决啦。
如何转移？
首先枚举上一格的状态
到这里问题又双叒叕来了：状态实在是太多啦，暴力枚举肯定会 TLE + MLE 的！
所以需要滚动一下数组，只存当前格的信息和上一格的信息，来确保不会 MLE。
对于 TLE，我们可以用哈希表来优化。细心的同学肯定早就发现了，那么多状态里肯定有一大堆不合法的。（括号不匹配）而暴力判断括号匹配麻烦又费事，所以我们采用优秀的哈希技术，把上一格可行的状态全存起来，同时 dp 状态的定义也变成了
由于状态转移只和当前格左边和上面的插头有关系（图中红色的插头），所以定义当前格左边那个往右插的插头状态为 p（0/1/2），当前格上面那个往下插的插头状态为 q（0/1/2）。
终于可以开始分类讨论了。
容易发现，其实一共就只有 7 种状态。
注意，在接下来的状态图中，灰色的箭头表示那里没有插头，红色的箭头表示那里有插头。
p==0&&q==0
这时，状态看起来是这样的
没有插头指向当前格！我们只好新建一个路径了：
这样，我们就新建了一对括号，解决了之前遗留下来的插头类型问题了。
p!=0&&q==0
这时，状态看起来是这样的
这时，我们可以让它拐个弯儿，或者让它往前走，变成这样
或者这样
注意，拐弯不能拐去地图边界了，往前走也不能走到地图边界。
p 的类型并不重要，因为转移之后的类型和转移之前的类型相同。
p==0&&q!=0
这时，状态看起来是这样的
和 2 号状态一样，我们可以让它拐个弯儿或者让它往前走。拐弯也不能拐去地图边界，往前走也不能走到地图边界。
q 的类型依然不重要。
p!=0&&q!=0
这时，状态看起来是这样的
对于这种情况，就要分四个子情况讨论了。
-
p==1&&q==1
这时，p 和 q 对应的路径是这样的
当我们把它们俩连起来后，路径就变成这样了
所以我们需要找到 q 对应的右括号（2），把它改成左括号（1），并把 p 和 q 改成井号（0）。
-
p==2&&q==2
这时，p 和 q 对应的路径是这样的
当我们把它们俩连起来后，路径就变成这样了
所以我们需要找到 p 对应的左括号（1），把它改成右括号（2），并把 p 和 q 改成井号（0）。
-
p==2&&q==1
这时，p 和 q 对应的路径是这样的
当我们把它们俩连起来后，路径就变成这样了
所以我们只要把 p 和 q 改成井号（0）就行了。
-
p==1&&q==2
这时，p 和 q 对应的路径是这样的
当我们把它们俩连起来后，路径就变成这样了
这可不得了！我们把路径闭合起来了！由于轮廓线下面的部分都还没有路径经过，所以这样做只有在 i==n&&j==m 的情况下才是合法的。
合法的话我们只要把 p 和 q 改成井号（0）就行了。
并且闭合之后答案要累加。
如何初始化？
当换行时，我们发现右插头位置没了……
而上一状态却有右插头位置
所以要补一个右插头位置。
输出什么？
最后要输出 答案*2。
因为老李可以顺时针走也可以逆时针走。
结束了？
没有……
这题太坑了，并没有 答案对 xxx 取模 这一句话，所以需要高精度……
因为我太懒了，所以高精度直接用了 __int128。（大家千万不要学我，因为 __int128 在赛场上不给用）
最后注意有个特判，当 1 时输出 1。
AC 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#define S 300005
#define mod 2001
typedef __int128 ll;
using namespace std;
int n,m;
ll dp[2][S];
int d; // 滚动数组下标
int tot[2],h[S],nxt[S],val[2][S]; // 哈希表相关
int only[15]; // only[i] 存 4^i
ll ans;
void write(ll x)
{
if(x<0)
{
putchar('-');
x=-x;
}
if(x>9)
{
write(x/10);
}
putchar(x%10+'0');
}
inline void ins(int x,ll num) // 插入哈希表并更新
{
int id=x%mod;
for(int p=h[id];p;p=nxt[p])
{
if(val[d][p]==x)
{
dp[d][p]+=num;
return;
}
}
nxt[++tot[d]]=h[id];
h[id]=tot[d];
val[d][tot[d]]=x;
dp[d][tot[d]]=num;
}
inline void _dp()
{
d=0;
tot[d]=1;
val[d][1]=0;
dp[d][1]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=tot[d];j++)
{
val[d][j]<<=2; // 初始化：插入一个空插头，补一下右插头位置
}
for(int j=1;j<=m;j++)
{
// 滚动
int las=d;
d^=1;
memset(h,0,sizeof(h));
tot[d]=0;
for(int k=1;k<=tot[las];k++) // 枚举状态
{
int zlt=val[las][k]; // 当前状态（zltzlt：zlt 好评）
ll num=dp[las][k];
int p=(zlt>>j*2-2)%4,q=(zlt>>j*2)%4; // 获取 q、p
// 各种状态
if(!p&&!q)
{
// 弄一个新路径
if(i<n&&j<m)
{
ins(zlt+only[j-1]+2*only[j],num);
}
}
else if(p&&!q)
{
// 拓展路径
if(i<n) // 拐个弯儿
{
ins(zlt,num);
}
if(j<m) // 直走
{
ins(zlt+only[j]*p-only[j-1]*p,num);
}
}
else if(!p&&q)
{
// 拓展路径
if(j<m) // 直走
{
ins(zlt,num);
}
if(i<n) // 拐个弯儿
{
ins(zlt-only[j]*q+only[j-1]*q,num);
}
}
else if(p==1&&q==1)
{
// 暴力找括号
int top=1;
for(int l=j+1;l<=m;l++)
{
if((zlt>>l*2)%4==1)
{
top++;
}
if((zlt>>l*2)%4==2)
{
top--;
}
if(top==0)
{
ins(zlt-only[j]-only[j-1]-only[l],num); // 改一下
break;
}
}
}
else if(p==2&&q==2)
{
// 暴力找括号
int top=1;
for(int l=j-2;l>=0;l--)
{
if((zlt>>l*2)%4==1)
{
top--;
}
if((zlt>>l*2)%4==2)
{
top++;
}
if(top==0)
{
ins(zlt+only[l]-only[j]*2-only[j-1]*2,num); // 改一下
break;
}
}
}
else if(p==2&&q==1)
{
ins(zlt-only[j-1]*2-only[j],num); // 连起来
}
else if(p==1&&q==2&&i==n&&j==m)
{
ans+=num; // 不得了了！
}
}
}
}
}
int main()
{
only[0]=1;
for(int i=1;i<=13;i++) // 初始化 only 数组
{
only[i]=only[i-1]<<2;
}
scanf("%d%d",&m,&n);
if(m==1||n==1) // 特判
{
puts("1");
return 0;
}
_dp();
write(ans*2); // 记得乘二
return 0;
}