struct hash_map { node s[SZ+10];int e,adj[SZ+10]; inline void init(){e=0;memset(adj,0,sizeof(adj));} inline void update(LL state,int val,int cnt) { RG int i,pos=(state%SZ+(LL)val*SZ)%SZ; for(i=adj[pos];i&&(s[i].state!=state||s[i].val!=val);i=s[i].next); if(!i)s[++e].state=state,s[e].val=val,s[e].cnt=cnt,s[e].next=adj[pos],adj[pos]=e; else s[i].cnt=(s[i].cnt+cnt)%mod; } inline void find(LL state,int val) { RG int i,pos=(state%SZ+(LL)val*SZ)%SZ; for(i=adj[pos];i&&(s[i].state!=state||s[i].val!=val);i=s[i].next); if(!i)printf("no such val "); else printf("cnt=%d ",s[i].cnt); } }f[2];
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1100000 #define mod 299989 #define P 8 #define N 100000000 ll n,m; inline ll find(ll state,ll id){ return (state>>((id-1)<<1))&3; }//看当前插头究竟是什么插头 //因为是四进制每两位代表一个状态 struct bignum { ll n[10],l; bignum(){l=1,memset(n,0,sizeof(n));} void clear(){while(l>1&&!n[l-1]) l--;} void print(){ printf("%lld",n[l-1]); for(ll i=l-2;i>=0;i--) printf("%0*lld",P,n[i]); printf(" "); } bignum operator +(bignum x)const{ bignum t=*this; if(t.l<x.l) t.l=x.l; t.l++; for(ll i=0;i<t.l;i++){ t.n[i]+=x.n[i]; if(t.n[i]>=N){ t.n[i+1]+=t.n[i]/N; t.n[i]%=N; } } t.clear(); return t; } bignum operator =(ll x){ l=0; while(x){ n[l++]=x%N; x/=N; } return *this; } inline void operator +=(bignum b){*this=*this+b;} }Ans; struct hash_map { bignum val[mod]; ll key[A],hash[mod],size; inline void init(){ memset(val,0,sizeof(val)); memset(key,-1,sizeof(key));size=0; memset(hash,0,sizeof(hash)); } inline void newhash(ll id,ll v){hash[id]=++size;key[size]=v;} bignum &operator [] (const ll &state){ for(ll i=state%mod;;i=(i+1==mod)?0:i+1) { if(!hash[i]) newhash(i,state); if(key[hash[i]]==state) return val[hash[i]]; } } }f[2]; inline void Set(ll &state,ll bit,ll val){ bit=(bit-1)<<1; state|=3<<bit; state^=3<<bit; //把state高位先赋成0再把它赋成别的 state|=val<<bit; //state表示状态 //因为插头的编号为0--m所以bit要-1 //因为是四进制,所以3<< //全都是4进制 //2<<bit //1<<bit //貌似还能理解 //每两位代表一个具体状态 } ll link(ll state,ll pos){ //找到对应的插头(用括号匹配的方式)然后 ll cnt=0,delta=(find(state,pos)==1)?1:-1; //如果是左括号应该向右寻找右括号 //如果是右括号应该向左寻找左括号 for(ll i=pos;i&&i<=m+1;i+=delta)//一共m+1个插头 { ll plug=find(state,i); if(plug==1) cnt++;//左括号数量++ else if(plug==2) cnt--;//右括号数量++ if(cnt==0)//当左括号数量与右括号数量相等时找到匹配 return i;//找到了与当前插头对应的插头 } return -1; //当前状态是非法的找不到与之对应的插头 } inline void education(ll x,ll y){ ll now=((x-1)*m+y)&1,last=now^1,tot=f[last].size; f[now].init(); for(ll i=1;i<=tot;i++){ // printf("i=%lld ",i); ll state=f[last].key[i];//key状态 bignum Val=f[last].val[i];//取出上一次权值（方案数） ll plug1=find(state,y),plug2=find(state,y+1); //0--m编号,寻找轮廓线上编号y-1,y对应的插头 //至于为什么是y y+1,因为在上面函数里进行了减1 //编号为y-1是左右插头,y代表上下插头 if(link(state,y)==-1||link(state,y+1)==-1) continue; //当前括号无法找到匹配无解 if(!plug1&&!plug2){ if(x!=n&&y!=m){ //如果没有插头,直接拽过来两个插头相连(此题保证必须连通) Set(state,y,1); //在轮廓线上位置为y-1添加一个左括号 Set(state,y+1,2); //y位置添加一个右括号 f[now][state]+=Val; } } else if(plug1&&!plug2){ //拥有左右插头没有上下插头 //两种转移方式,转弯向下走 //这样插头状态不变 if(x!=n) f[now][state]+=Val; //向右连接一个插头 //向右推进要发生改变 if(y!=m){ Set(state,y,0); Set(state,y+1,plug1); f[now][state]+=Val; } } else if(!plug1&&plug2){ //拥有上下插头而没有左右插头 //两种转移方式,向右转移 //这样插头状态不变 if(y!=m) f[now][state]+=Val; //向右连接一个插头 if(x!=n){ Set(state,y,plug2); Set(state,y+1,0); //plug2是左右插头让上下方向转弯 f[now][state]+=Val; } } else if(plug1==1&&plug2==1){ //两个左括号插头相连接,然后让最靠左的右括号插头变成左括号插头 Set(state,link(state,y+1),1); Set(state,y,0); Set(state,y+1,0); f[now][state]+=Val; } else if(plug1==1&&plug2==2){ //右插头是左括号插头,上插头是右括号插头,连在一起 //构成回路 if(x==n&&y==m) Ans+=Val; } else if(plug1==2&&plug2==1){ //无脑合并 Set(state,y,0); Set(state,y+1,0); f[now][state]+=Val; } else if(plug1==2&&plug2==2){ //当你有左右插头右括号插头,上下插头为右插头 //合并为1,将最靠右左插头变为右插头 Set(state,link(state,y),2); Set(state,y,0); Set(state,y+1,0); f[now][state]+=Val; } } } int main(){ scanf("%lld%lld",&n,&m); if(n==1||m==1){printf("1 ");return 0;} if(m>n) swap(n,m); f[0].init();f[0][0]=1; for(ll i=1;i<=n;i++) { for(ll j=1;j<=m;j++) education(i,j); if(i!=n){ ll now=(i*m)&1,tot=f[now].size; for(ll j=1;j<=tot;j++) f[now].key[j]<<=2; } } Ans+=Ans; Ans.print(); }