记录编号	222317	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	阿狸	是否通过	通过
代码语言	C++	运行时间	0.100 s
提交时间	2016-01-30 17:38:33	内存使用	82.77 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const long long mod=10000000000000000ll;
const int MAXD=15;
const int HASH=13331;
const int STATE=1000010;
int n,m;
int code[MAXD];
int ch[MAXD];
struct node{
	int len;
	long long k[4];
};
node operator + (node a,node b){
	if(b.len>a.len)a.len=b.len;
	for(int i=1;i<=a.len;++i)a.k[i]+=b.k[i];
	for(int i=1;i<a.len;++i)
		if(a.k[i]>=mod){
			a.k[i]-=mod;
			a.k[i+1]++;
		}
	while(a.k[a.len]>=mod){
		a.k[a.len]-=mod;
		a.k[a.len+1]++;
		a.len++;
	}
	return a;
}
struct HASHMAP{
	int h[HASH],next[STATE],size;
	long long state[STATE];
	node f[STATE];
	void init(){
		size=0;
		memset(h,-1,sizeof(h));
	}
	void push(long long st,node ans){
		int v=st%HASH;
		for(int i=h[v];i!=-1;i=next[i])
			if(state[i]==st){
				f[i]=f[i]+ans;
				return;
			}
		state[size]=st;
		f[size]=ans;
		next[size]=h[v];
		h[v]=size++;
	}
}hm[2];
void decode(long long st){
	for(int i=m;i>=0;--i){
		code[i]=st&7;
		st>>=3;
	}
}
long long encode(){
	int cnt=1;
	memset(ch,-1,sizeof(ch));
	ch[0]=0;
	long long st=0;
	for(int i=0;i<=m;++i){
		if(ch[code[i]]==-1)ch[code[i]]=cnt++;
		code[i]=ch[code[i]];
		st<<=3;
		st|=code[i];
	}return st;
}
void shit(){
	for(int i=m;i;--i)code[i]=code[i-1];
	code[0]=0;
}
void dpblank(int i,int j,int cur){
	int k,left,up;
	for(k=0;k<hm[cur].size;++k){
		decode(hm[cur].state[k]);
		left=code[j-1];
		up=code[j];
		if(left&&up){
			if(left==up){
				if(i==n&&m==j){
					code[j-1]=code[j]=0;shit();
					hm[cur^1].push(encode(),hm[cur].f[k]);
				}
			}else{
				code[j-1]=code[j]=0;
				for(int t=0;t<=m;++t)
					if(code[t]==up)
						code[t]=left;
				if(j==m)shit();
				hm[cur^1].push(encode(),hm[cur].f[k]);
			}
		}else if(left||up){
			int t;
			if(left)t=left;else t=up;
			if(j+1<=m){
				code[j-1]=0;code[j]=t;
				hm[cur^1].push(encode(),hm[cur].f[k]);
			}
			if(i+1<=n){
				code[j-1]=t;code[j]=0;
				if(j==m)shit();
				hm[cur^1].push(encode(),hm[cur].f[k]);
			}
		}else{
			if(j+1<=m&&i+1<=n){
				code[j-1]=code[j]=13;
				hm[cur^1].push(encode(),hm[cur].f[k]);
			}
		}
	}
}
int main(){
	freopen("postman.in","r",stdin);
	freopen("postman.out","w",stdout);
	scanf("%d%d",&m,&n);
	if(m==1||n==1){
		printf("1");
		return 0;
	}
	int cur=0;
	hm[cur].init();
	node a;a.len=1;
	memset(a.k,0,sizeof(a.k));
	a.k[1]=1;
	hm[cur].push(0,a);
	for(int i=1;i<=n;++i)
		for(int j=1;j<=m;++j){
			hm[cur^1].init();
			dpblank(i,j,cur);
			cur^=1;
		}
	node ans;
	ans.len=1;
	memset(ans.k,0,sizeof(ans.k));
	for(int i=0;i<hm[cur].size;++i)
		ans=ans+hm[cur].f[i];
	ans=ans+ans;
	printf("%lld",ans.k[ans.len]);
	for(int i=ans.len-1;i;--i)printf("%16lld",ans.k[i]);
	return 0;
}