插头dp_插头dp noi

引入：赛道

一个$n\times m$的棋盘，有些格子是正常的，有些格子有障碍。求经过每个正常的格子恰好一次的哈密顿回路的个数。$2\le n,m\le 12$

如果直接爆搜，那么复杂度是$O((nm)!)$的，显然会超时。

因此这题需要dp。

考虑按从上到下，从左到右的顺序转移，则状态中需要维护一条轮廓线，如图所示：

考虑把路径画出来，那么轮廓线上有些线段有插头，有些线段没有插头。

那么可以把轮廓线上每个位置是否有插头以及插头的连通性表示出来。

例如图中状态可以表示为(1,2,2,0,1)，其中0表示该位置没有插头，1和2表示该位置插头所属连通块。

然而这样状态数可能很多。可以发现，每个数恰好有两个，而且插头构成的这些路径两两不相交。

两个…两两不相交…你想到了什么？没错，括号序列！

把上述状态转化为括号序列，0变成#，一对插头分别变成(和)。例如上述状态可以表示成(()#)。

这样我们就把状态变成了一个3进制数。

（实际操作中，可以把进制数变成2的次幂，例如4进制，再用哈希表存下，这样会更快一些）

转移并不难。

1. 当格子左、上边没有插头时，

   (###) -> (()#)

2. 当格子左、上边有一个插头时，

   (()#) -> (()#)

   (()#) -> ((#))

3. 当格子左、上边都有插头时，

   1. 当左、上插头均为(时，

      #(()) -> ###()

      当左、上插头均为)时同理。

   2. 当左、上插头为)(时，

      (#)() -> (###)

   3. 当左、上插头为()时，

      考虑到连通性，当且仅当转移到最后一个正常的格子的时候，转移有效。

开始愉快地贴代码！

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define R register int
const int N=1594323,L=14;
int n,m,n3=1,e[L],F[N][L],a[L][L],cnt,st[L],pa[L],now;
int t,o,f1,f2,e1,e2;
ll dp[2][N],ans,tdp;
char c[L];
int main(){
   
    scanf("%d%d",&m,&n);
    for(R i=1;i<=m;i++){
   
        scanf("%s",c+1);
        for(int j=1;j<=n;j++)if(c[j]=='*')a[i][j]=1;
        else ++cnt;
    }
    for(R i=1;i<=n+1;i++){
   
        e[i]=n3;
        n3+=n3<<1;
    }
    for(R i=0;i<n3;i++){
   
        t=i;
        for(R j=1;j<=n+1;j++){
   
            F[i][j]=t%3;
            t/=3;
        }
    }
    dp[0][0]=1;
    for(R i=1;i<=m;i++){
   
        for(R j=1;j<=n;j++){
   
			if(!a[i][j])--cnt;
			now^=1;
			memset(dp[now],0,sizeof(dp[now]));
			e1=e[j];e2=e[j+1];
			for(R k=0;k<n3;k++)if(dp[now^1][k]){
   
				f1=F[k][j];f2=F[k][j+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44