ural1519 Formula 1（插头dp）

ural1519 Formula 1（插头dp）

一个n*m的棋盘，有些格子是障碍，问存在多少条哈密顿回路。(n,m<=12)
基于连通性的状态压缩动态规划。cdq论文。
这题逐格递推，括号表示法，滚动数组+Hash表优化空间。
复杂度 O(S∗n) O ( S ∗ n ) $O(S*n)$
2017.5.21第一次写这道题。
2018.6.13把这题整理到blog上。
这一年来，水平究竟有没有长进呢…
当时就能写出Hash表+括号表示法的插头dp了呢。
现在却写不出了呢…

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 20010
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,m,ex,ey,pp,c[]={0,-1,1,0};
char mp[15][15];
struct Hash_table{int key,next;;ll val;
};
struct Icefox{int h[N],num;Hash_table data[N];inline void init(){num=0;memset(h,0,sizeof(h));}inline void ins(int key,ll val){int x=key%N;for(int i=h[x];i;i=data[i].next)if(data[i].key==key){data[i].val+=val;return;}data[++num].key=key;data[num].val=val;data[num].next=h[x];h[x]=num;}inline ll hs(int key){int x=key%N;for(int i=h[x];i;i=data[i].next)if(data[i].key==key) return data[i].val;return 0;}
}dp[2];
inline int get1(int st,int x){x<<=1;return (st>>x)&3;}
inline int set1(int st,int x,int v){x<<=1;return (st& ~(3<<x))|(v<<x);}
inline int getr(int st,int x){int r=x,cnt=-1;while(cnt) cnt+=c[get1(st,++r)];return r;
}
inline int getl(int st,int x){int l=x,cnt=1;while(cnt) cnt+=c[get1(st,--l)];return l;
}
void update(int x,int y,int st,ll val){int p=get1(st,y),q=get1(st,y+1);if(mp[x][y]=='*'){if(!p&&!q) dp[pp^1].ins(st,val);return;}if(!p&&!q){//没有插头进来，只好再放一个新插头 if(y==m-1||x==n-1) return;//注意特判 int newst=set1(st,y,1);newst=set1(newst,y+1,2);dp[pp^1].ins(newst,val);return;}if(!p||!q){//可以向右或向下延伸 if(y<m-1){//注意特判 int newst=set1(st,y,0);newst=set1(newst,y+1,p+q);dp[pp^1].ins(newst,val);}if(x<n-1){int newst=set1(st,y,p+q);newst=set1(newst,y+1,0);dp[pp^1].ins(newst,val);}return;}int newst=set1(st,y,0);newst=set1(newst,y+1,0);if(p==1&&q==1) newst=set1(newst,getr(st,y+1),1);if(p==2&&q==2) newst=set1(newst,getl(st,y),2);if(p==1&&q==2&&(x!=ex||y!=ey)) return;//不是最后一个不能闭合 dp[pp^1].ins(newst,val);
}
int main(){
//  freopen("a.in","r",stdin);n=read();m=read();for(int i=0;i<n;++i) scanf("%s",&mp[i]);for(int i=0;i<n;++i)for(int j=0;j<m;++j)if(mp[i][j]=='.') ex=i,ey=j;pp=0;dp[pp].init();dp[pp].ins(0,1);for(int i=0;i<n;++i){//每行第一个格要特殊处理一下，相当于把上次状态左移一位 for(int j=1;j<=dp[pp].num;++j) dp[pp].data[j].key<<=2;for(int j=0;j<m;++j){dp[pp^1].init();for(int k=1;k<=dp[pp].num;++k)update(i,j,dp[pp].data[k].key,dp[pp].data[k].val);pp^=1;}}printf("%lldn",dp[pp].hs(0));return 0;
}