记录编号	477626	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	Hzoi_Ivan	是否通过	通过
代码语言	C++	运行时间	0.220 s
提交时间	2017-12-05 16:42:11	内存使用	34.77 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct bignum{
	int a[55],len;
	bignum(){
		memset(a,0,sizeof a);
		len=0;
	}
	void clear(){
		memset(a,0,sizeof a);
		len=0;
	}
	void print(){
		if(len==0){puts("0");return ;}
		for(int i=len;i;i--)
			printf("%d",a[i]);
		puts("");
	}
	bignum operator +=(bignum b){
		len=max(len,b.len);
		for(int i=1;i<=len;i++){
			a[i]+=b.a[i];
			a[i+1]+=a[i]/10;
			a[i]%=10;
		}
		while(a[len+1])len++;
		return *this;
	}
}ans;
struct hash_table{
	static const int P=76543;
	int key[P+10],head[P+10],nxt[P+10],tot;
	bignum val[P+10];
	void clear(){
		tot=0;
		memset(head,0,sizeof head);
	}
	void newnode(int x){
		nxt[++tot]=head[x%P];
		head[x%P]=tot;
		key[tot]=x;
		val[tot].clear();
	}
	bignum & operator [] (int x){
		for(int i=head[x%P];i;i=nxt[i])
			if(key[i]==x)return val[i];
		newnode(x);
		return val[tot];
	}
}f[2];
int now,last;
int n,m;
int get(int s,int x){
	return (s>>((x-1)*2))&3;
}
int find(int s,int x){
	for(int i=x,pos=(get(s,x)==1?1:-1),num=0;;i+=pos){
		int t=get(s,i);
		if(t==1)num++;
		if(t==2)num--;
		if(!num)return i;
	}
}
void change(int &s,int x,int y){
	s^=get(s,x)<<((x-1)*2);
	s^=y<<((x-1)*2);
}
void dp(int i,int j){
	now^=1;last^=1;
	f[now].clear();
	for(int k=1;k<=f[last].tot;k++){
		int s=f[last].key[k];
		bignum v=f[last].val[k];
		int x=get(s,j),y=get(s,j+1);
		if(!x&&!y){
			change(s,j,1);
			change(s,j+1,2);
			if(i!=n&&j!=m)f[now][s]+=v;
		}
		else if(!x&&y){
			if(j!=m)f[now][s]+=v;
			change(s,j,y);
			change(s,j+1,x);
			if(i!=n)f[now][s]+=v;
		}
		else if(x&&!y){
			if(i!=n)f[now][s]+=v;
			change(s,j,y);
			change(s,j+1,x);
			if(j!=m)f[now][s]+=v;
		}
		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]+=v;
		}
		else if(x==2&&y==2){
			change(s,find(s,j),2);
			change(s,j,0);
			change(s,j+1,0);
			f[now][s]+=v;
		}
		else if(x==2&&y==1){
			change(s,j,0);
			change(s,j+1,0);
			f[now][s]+=v;
		}
		else if(x==1&&y==2){
			change(s,j,0);
			change(s,j+1,0);
			if(i==n&&j==m)ans+=v;
		}
	}
}
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;}
	f[0][0].a[1]=1;f[0][0].len=1;
	now=0;last=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			dp(i,j);
		for(int j=1;j<=f[now].tot;j++)
			f[now].key[j]<<=2;
	}
	ans+=ans;
	ans.print();
	return 0;
}