记录编号	477443	评测结果	AWWWWWWWWT
题目名称	[HNOI 2004] 邮递员	最终得分	10
用户昵称	Hzoi_Hugh	是否通过	未通过
代码语言	C++	运行时间	10.033 s
提交时间	2017-12-03 14:57:55	内存使用	0.45 MiB

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int Base=1000000000;
const int Max_Hash=2601;
inline int get(int s,int x){
  return (s>>((x-1)<<1))&3;
}
inline void change(int &s,int pos,int b){
  int w=(pos-1)<<1;
  s|=3<<w,s^=3<<w,s|=b<<w;
}
inline int Max(int x,int y){
  return x>y?x:y;
}
inline int find(int s,int p){
  for(int i=p,d=0,step=get(s,p)==1?1:-1;;i+=step){
    d+=get(s,i)==1?1:-1;
    d+=get(s,i)==0?1:0;
    if(!d)return i;
  }
  return -1;
}
int n,m;
struct bigint{
  int a[5];
  void clear(){memset(a,0,sizeof(a)),a[0]=1;}
  bigint(){clear();}
  void set(int x){
    clear();
    while(x)a[++a[0]]=x%Base,x/=Base;
  }
  void print(){
    printf("%d",a[a[0]]);
    for(int i=a[0]-1;i>0;i--)
      printf("%09d",a[i]);
    //puts("");
  }
  bigint operator + (bigint b){
    bigint c;c.clear();
    //puts("HHHHHHH");
    //print();
    //b.print();
    c.a[0]=Max(a[0],b.a[0])+1;
    for(int i=1;i<=c.a[0];i++)
      c.a[i]+=a[i]+b.a[i],c.a[i+1]+=c.a[i]/Base,c.a[i]%=Base;
    while(c.a[0]>1&&!c.a[c.a[0]])c.a[0]--;
    return c;
  }
  void operator += (bigint b){
    *this=(*this)+b;
  }
  void operator = (int x){
    set(x);
  }
}ans;
struct Hash_Table{
  int key[Max_Hash];
  int cnt,hash[Max_Hash];
  bigint val[Max_Hash];
  void clear(){
    memset(key,-1,sizeof(key));
    memset(hash,0,sizeof(hash));
    memset(val,0,sizeof(val));
    cnt=0;
  }
  void newnode(int i,int _key){
    hash[i]=++cnt;
    key[cnt]=_key;
  }
  bigint& operator [] (int _hash){
    int k;
    for(int i=_hash%Max_Hash;;i++){
      if(i==Max_Hash)i=0;
      if(!hash[i])newnode(i,_hash);
      if(key[hash[i]]==_hash){
        k=hash[i];break;
      }
    }
    return val[k];
  }
}f[2];
int now,last;
void dp(int i,int j){
  now^=1,last^=1;
  int tot=f[last].cnt;
  f[now].clear();
  for(int k=1,x,y;k<=tot;k++){
    int s=f[last].key[k];
    bigint val=f[last].val[k];
    x=get(s,j),y=get(s,j+1);
    if(x==0&&y==0){
      if(i!=n&&j!=m){
        change(s,j,1),
        change(s,j+1,2);
        f[now][s]+=val;
      }
    }else if(x==1&&y==1){
      change(s,find(s,j+1),1),change(s,j,0),change(s,j+1,0);
      f[now][s]+=val;
    }else if(x==2&&y==2){
      change(s,find(s,j),2),change(s,j,0),change(s,j+1,0);
      f[now][s]+=val;
    }else if(x==2&&y==1){
      change(s,j,0),change(s,j+1,0);
      f[now][s]+=val;
    }else if(x==1&&y==2){
      if(i==n&&j==m){
        ans+=val;
        return;
      }
    }else if(x){
      if(i!=n)f[now][s]+=val;
      if(j!=m)change(s,j,0),change(s,j+1,x),f[now][s]+=val;
    }else if(y){
      if(j!=m)f[now][s]+=val;
      if(i!=n)change(s,j+1,0),change(s,j,y),f[now][s]+=val;
    }
  }
}
int main(){
  freopen("postman.in","r",stdin);freopen("postman.out","w",stdout);
  scanf("%d%d",&n,&m);
  if(n==1||m==1){
    printf("1");
    return 0;
  }
  if(n<m)n^=m^=n^=m;
  f[0][0]=1;
  now=0,last=1;
  for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)dp(i,j);
    if(i!=n)
      for(int j=1,k=f[now].cnt;j<=k;j++)
        f[now].key[j]<<=2;
  }
  //ans.print();
  ans+=ans;
  ans.print();
  return 0;
}