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\n");
else printf("cnt=%d\n",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("\n");
}
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\n",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\n");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();
}

最新文章

  1. yii2 实战教程之如何安装
  2. 第一二九天上课 PHP 自制简单开发模板
  3. nanoTime对volatile 测试的一种写法
  4. LVS + Keepalived + Nginx安装及配置
  5. css 父层 透明 子层不透明Alpha
  6. .net 设置导航的当前状态
  7. vs2013专业版密钥
  8. 【转】APNs消息推送完整讲解
  9. cotangent Laplacian
  10. iOS 犄角旮旯的知识
  11. linux下别名alias的设置
  12. poj2192
  13. Android 透明Button
  14. [Redux] Store Methods: getState(), dispatch(), and subscribe()
  15. deepin 2014 静态IP无法保存,临时方法
  16. mongoDB入门必读(概念与实战并重)
  17. Yii 2.0 ActiveForm生成表单 ,控制表单label和filed样式,filed一旦报错,前面lable颜色跟着变,看图,帮你解决
  18. Bluetooth A2DP --Audio payload type
  19. 补习系列(5)-springboot- restful应用
  20. 4.翻译系列:EF 6 Code-First默认约定(EF 6 Code-First系列)

热门文章

  1. COM组件对象模型基础
  2. Java安全之FastJson JdbcRowSetImpl 链分析
  3. python 键盘中断子线程及graceful exiting方案
  4. JDBC核心技术(获取数据库链接、数据库事务、数据库链接池)
  5. [刷题] PTA 7-32 说反话-加强版
  6. 【转载】认识SSD的SATA、mSATA 、PCIe和M.2四种主流接口
  7. Linux性能监控与分析之--- CPU
  8. 攻防世界-WEB-新手练习区
  9. power delivery功率输出
  10. Centos 7常见问题——SMBus Host Controller not enabled!