记录编号	223978	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.050 s
提交时间	2016-02-15 09:21:52	内存使用	0.53 MiB

#include<stdio.h>
#include<string.h>
#define TP 1000000000
#define ll long long
#define HASH 3017
inline int W(int x){return (x-1)<<1;}
int n,m,k=1,tot[2],hash[HASH];
ll sta[2][HASH];
struct big_num{
	int a[8];
	inline friend big_num operator + (big_num a,big_num b){
		int *A=a.a,*B=b.a,i;
		for(i=1;i<=A[0]||i<=B[0];++i)
		    A[i]+=B[i],A[i+1]+=A[i]/TP,A[i]%=TP;
		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("%09d",a[i]);
	}
}tmp,ans,sum[2][HASH];
void add(ll x){
	int pos=x%HASH;
	while(hash[pos]){
		if(sta[k^1][hash[pos]]==x){
            sum[k^1][hash[pos]]=sum[k^1][hash[pos]]+tmp;
            return;
		}
		pos=(pos+1)%HASH;
	}
	++tot[k^1];
	hash[pos]=tot[k^1];
	sum[k^1][tot[k^1]]=tmp;
	sta[k^1][tot[k^1]]=x;
}
void work(){
	int p,q;
	sum[0][1].a[0]=sum[0][1].a[1]=tot[0]=1;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=m;++j){
			tot[k]=0;
			memset(hash,0,sizeof(hash));
			memset(sta[k],0,sizeof(sta[k]));
			memset(sum[k],0,sizeof(sum[k]));
			k^=1;
			for(int t=1;t<=tot[k];++t){//枚举上次所有状态，转态储存在hash表中，
				ll st=sta[k][t];//之所以用hash表存，是因为不同的状态可以
				tmp=sum[k][t];//转移到相同的状态上去，用hash能实现这一过程
				p=(st>>W(j))&3,q=(st>>W(j+1))&3;
				if(!p&&!q){
					if(j==m||i==n) continue;
					st^=1<<W(j);
					st^=(1<<W(j+1))<<1;
					add(st);
				}
				else if(p&&!q){
					if(i!=n) add(st);
					if(j==m) continue;
					st^=(1<<W(j))*p;
					st^=(1<<W(j+1))*p;
					add(st);
				}
				else if(!p&&q){
					if(j!=m) add(st);
					if(i==n) continue;
					st^=(1<<W(j))*q;
					st^=(1<<W(j+1))*q;
					add(st);
				}
				else if(p==1&&q==1){
					int tip=1;
					for(int l=j+2;l<=m+1;++l){
						int o=(st>>W(l))&3;
						if(o==1) ++tip;
						if(o==2) --tip;
						if(!tip){
							st^=(1<<W(l))<<1;
							st^=(1<<W(l));
							break;
						}
					}
					st^=1<<W(j);
					st^=1<<W(j+1);
					add(st);
				}
				else if(p==2&&q==2){
					int tip=1;
					for(int l=j-1;l;--l){
						int o=(st>>W(l))&3;
						if(o==2) ++tip;
						if(o==1) --tip;
						if(!tip){
							st^=(1<<W(l))<<1;
							st^=(1<<W(l));
							break;
						}
					}
					st^=1<<W(j)<<1;
					st^=1<<W(j+1)<<1;
					add(st);
				}
				else if(p==2&&q==1){
					st^=(1<<W(j))*p;
					st^=(1<<W(j+1))*q;
					add(st);
				}
				else if(i==n&&j==m) ans=ans+tmp;
			}
		}
		for(int j=1;j<=tot[k^1];++j) sta[k^1][j]=sta[k^1][j]<<2;
	}
	ans=ans+ans,ans.print();
}
int main(){
	freopen("postman.in","r",stdin);
	freopen("postman.out","w",stdout);
	scanf("%d%d",&m,&n);
	if(n==1||m==1) puts("1");
	else work();
}