记录编号	213359	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2015-12-11 20:13:54	内存使用	0.63 MiB

#include<cstdio>
#include<cstring>

#define JZ 100000000
#define HashSize 2557
#define W(i) ((i-1)<<1)

using namespace std;

typedef long long LL;

struct BigData{
	int a[15];
	friend BigData operator + (BigData a,BigData b){
		int *A=a.a,*B=b.a;
		int i;
		for(i=1;i<=A[0]||i<=B[0];i++){
			A[i]+=B[i],A[i+1]+=A[i]/JZ,A[i]%=JZ;
		}
		while(!A[i]) i--;
		A[0]=i;
		return a;
	}
	void print(){
		printf("%d",a[a[0]]);
		for(int i=a[0]-1;i>0;i--){
			printf("%08d",a[i]);
		}
	}
};BigData tmps,ans;

int n,m,tot[2],hash[HashSize+10],k=1;
LL state[2][HashSize+10];
BigData sum[2][HashSize+10];

void HashIn(LL sta)
{
	int pos=sta%HashSize;
	while(hash[pos]){
		if(state[k^1][hash[pos]]==sta){
			sum[k^1][hash[pos]]=sum[k^1][hash[pos]]+tmps;
			return;
		}
		pos++;
		if(pos==HashSize) pos=0;
	}
	tot[k^1]++;
	hash[pos]=tot[k^1];
	sum[k^1][tot[k^1]]=tmps;
	state[k^1][tot[k^1]]=sta;
}

void Work()
{
	sum[0][1].a[0]=sum[0][1].a[1]=1;
	tot[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			k^=1;
			tot[k^1]=0;
			memset(hash,0,sizeof(hash));
			memset(state[k^1],0,sizeof(state[k^1]));
			memset(sum[k^1],0,sizeof(sum[k^1]));
			for(int s=1;s<=tot[k];s++){
				LL sta=state[k][s];
				tmps=sum[k][s];
				int p=(sta>>W(j))&3;
				int q=(sta>>W(j+1))&3;
				if(p==0&&q==0){
					if(j==m||i==n) continue;
					sta^=1<<W(j);
					sta^=(1<<W(j+1))*2;
					HashIn(sta);
					continue;
				}
				if(p>0&&q==0){
					if(i!=n) HashIn(sta);
					if(j==m) continue;
					sta^=(1<<W(j))*p;
					sta^=(1<<W(j+1))*p;
					HashIn(sta);
					continue;
				}
				if(p==0&&q>0){
					if(j!=m) HashIn(sta);
					if(i==n) continue;
					sta^=(1<<W(j+1))*q;
					sta^=(1<<W(j))*q;
					HashIn(sta);
					continue;
				}
				if(p==1&&q==1){
					int brackets=1;
					for(int v=j+2;v<=m+1;v++){
						int t=(sta>>(W(v)))&3;
						if(t==1) brackets++;
						if(t==2) brackets--;
						if(brackets==0){
							sta^=(1<<W(v))*2;
							sta^=(1<<W(v));
							break;
						}
					}
					sta^=1<<W(j);
					sta^=1<<W(j+1);
					HashIn(sta);
					continue;
				}
				if(p==2&&q==2){
					int brackets=1;
					for(int v=j-1;v>0;v--){
						int t=(sta>>(W(v)))&3;
						if(t==2) brackets++;
						if(t==1) brackets--;
						if(brackets==0){
							sta^=(1<<W(v));
							sta^=(1<<W(v))*2;
							break;
						}
					}
					sta^=(1<<W(j))*2;
					sta^=(1<<W(j+1))*2;
					HashIn(sta);
					continue;
				}
				if(p==1&&q==2){
					if(i==n&&j==m){
						ans=ans+tmps;
					}
					continue;
				}
				if(p==2&&q==1){
					sta^=(1<<W(j))*p;
					sta^=(1<<W(j+1))*q;
					HashIn(sta);
					continue;
				}
			}
		}
		for(int j=1;j<=tot[k^1];j++){
			state[k^1][j]=state[k^1][j]<<2;
		}
	}
}

int main()
{
	freopen("postman.in","r",stdin);
	freopen("postman.out","w",stdout);
	scanf("%d%d",&m,&n);
	if(n==1||m==1){
		printf("1");
		return 0;	
	}
	Work();
	ans=ans+ans;
	ans.print();
	return 0;
}