记录编号	223981	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	葳棠殇	是否通过	通过
代码语言	C++	运行时间	0.108 s
提交时间	2016-02-15 09:24:11	内存使用	1.65 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define W(i) ((i-1)<<1)
#define mod 100000000
#define LL long long
struct BIGNUM{
	int a[15];
	BIGNUM(){memset(a,0,sizeof(a));}
	friend BIGNUM operator +(BIGNUM a,BIGNUM b){
		BIGNUM c;
		int x=0;
		c.a[0]=max(a.a[0],b.a[0])+1;
		for(int i=1;i<=c.a[0];i++){
			c.a[i]=a.a[i]+b.a[i]+x;
			x=c.a[i]/mod;
			c.a[i]%=mod;
		}
		while(c.a[0]&&!c.a[c.a[0]]){
			c.a[0]--;
		}
		return c;
	}
	void out(){
		printf("%d",a[a[0]]);
		a[0]--;
		while(a[0]>0){
			printf("%08d",a[a[0]--]);
		}
		printf("\n");
	}
}ans,tmps;
BIGNUM sum[2][10007];
int hash[10007],tot[2];
LL state[2][10007];
int n,m,k=1;
void push(LL sta){
	int pos=sta%10007;
	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==10007){
			pos=0;
		}
	}
	tot[k^1]++;
	hash[pos]=tot[k^1];
	sum[k^1][tot[k^1]]=tmps;
	state[k^1][tot[k^1]]=sta;
}
int main(){
	freopen("postman.in","r",stdin);
	freopen("postman.out","w",stdout);
	scanf("%d%d",&m,&n);
	if(n==1||m==1){
		printf("1\n");
		return 0;
	}
	sum[0][1].a[1]=sum[0][1].a[0]=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&&!q){
					if(i==n||j==m){
						continue;
					}
					sta^=1<<W(j);
					sta^=(1<<W(j+1))*2;
					push(sta);
					continue;
				}
				if(p&&!q){
					if(i!=n){
						push(sta);
					}
					if(j==m){
						continue;
					}
					sta^=(1<<W(j))*p;
					sta^=(1<<W(j+1))*p;
					push(sta);
					continue;
				}
				if(!p&&q){
					if(j!=m){
						push(sta);
					}
					if(i==n){
						continue;
					}
					sta^=(1<<W(j+1))*q;
					sta^=(1<<W(j))*q;
					push(sta);
					continue;
				}
				if(p==1&&q==1){
					int bracket=1;
					for(int v=j+2;v<=m+1;v++){
						int t=(sta>>(W(v)))&3;
						if(t==1){
							bracket++;
						}
						if(t==2){
							bracket--;
						}
						if(bracket==0){
							sta^=(1<<W(v))*2;
							sta^=(1<<W(v));
							break;
						}
					}
					sta^=1<<W(j);
					sta^=1<<W(j+1);
					push(sta);
					continue;
				}
				if(p==2&&q==2){
					int bracket=1;
					for(int v=j-1;v;v--){
						int t=(sta>>(W(v)))&3;
						if(t==2){
							bracket++;
						}
						if(t==1){
							bracket--;
						}
						if(bracket==0){
							sta^=(1<<W(v));
							sta^=(1<<W(v))*2;
							break;
						}
					}
					sta^=(1<<W(j))*2;
					sta^=(1<<W(j+1))*2;
					push(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;
					push(sta);
					continue;
				}
			}
		}
		for(int j=1;j<=tot[k^1];j++){
			state[k^1][j]=state[k^1][j]<<2;
		}
	}
	ans=ans+ans;
	ans.out();
}