记录编号	224078	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	0.045 s
提交时间	2016-02-15 14:32:41	内存使用	0.72 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define W(i) ((i-1)<<1)
using namespace std;
struct udata
{
	int x[15];
	friend udata operator + (udata aa,udata bb)
	{
		int *A=aa.x,*B=bb.x;
		int h=0;
		if(A[0]<B[0])
		    A[0]=B[0];
		for(int i=1;i<=A[0];i++)
		{
			A[i]=A[i]+B[i];
			A[i]=A[i]+h;
			h=A[i]/100000000;
			A[i]%=100000000;
		}
		if(h)
		    A[++A[0]]=h;
		return aa;
	}
}qz[2][3020],zhi,ans;
long long q[2][3020];
int hash[3020];
int tp[2],now=1,n,m;
inline void ghashin(long long s)//s状态
{
	int p=s%3020;
	int o=p-1;
	while(hash[p]!=0)
	{
		if(s==q[now^1][hash[p]])
		{
			qz[now^1][hash[p]]=qz[now^1][hash[p]]+zhi;
			return;
		}
		p++;
		if(p==3020)
		    p=0;
	}
	++tp[now^1];
	hash[p]=tp[now^1];
	qz[now^1][tp[now^1]]=zhi;
	q[now^1][tp[now^1]]=s;
}
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;
	}
	qz[0][1].x[0]=qz[0][1].x[1]=1;
	tp[0]=1;
	for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=m;j++)
	    {
			now^=1;
			memset(hash,0,sizeof(hash));
			tp[now^1]=0;
			for(int s=1;s<=tp[now];++s)
			{
				zhi=qz[now][s];
				long long ztai=q[now][s];
				int p=(ztai>>W(j))&3,qq=(ztai>>W(j+1))&3;
				if(p==0&&qq==0)
				{
					if(i==n||j==m)
					    continue;
					ztai^=(1<<W(j));
					ztai^=(1<<W(j+1))*2;
					ghashin(ztai);
				}
				else if(p==1&&qq==1)
				{
					int d=1;
					for(int y=j+2;y<=m+1;y++)
					{
						int o=(ztai>>W(y))&3;
						if(o==1)
						    ++d;
						if(o==2)
						    --d;
						if(d==0)
						{
							ztai^=(1<<W(y))*2;//清除原有右括号标记
							ztai^=(1<<W(y));//添加左括号标记
							break;
						}
					}
					ztai^=1<<W(j);
					ztai^=1<<W(j+1);
					ghashin(ztai);
				}
				else if(p==2&&qq==2)
				{
					int d=-1;
					for(int y=j-1;y>=0;y--)
					{
						int o=(ztai>>W(y))&3;
						if(o==1)
						    ++d;
						if(o==2)
						    --d;
						if(d==0)
						{
							ztai^=(1<<W(y));
							ztai^=(1<<W(y))*2;
							break;
						}
					}
					ztai^=(1<<W(j))*2;
					ztai^=(1<<W(j+1))*2;
					ghashin(ztai);
				}
				else if(p==1&&qq==2)
				{
					if(i==n&&j==m)
					{
						//printf("%d %d\n",i,j);
						ans=ans+zhi;
					}
				}
				else if(p==2&&qq==1)
				{
					ztai^=(1<<W(j))*2;
					ztai^=(1<<W(j+1));
					ghashin(ztai);
				}
				else if(p>0&&qq==0)
				{
					if(i!=n)
					    ghashin(ztai);
					if(j==m)
					    continue;
					//printf("A%lld",ztai);
					ztai^=(1<<W(j))*p;
					ztai^=(1<<W(j+1))*p;
					ghashin(ztai);
					//printf("B");
				}
				else
				{
					if(j!=m)
					    ghashin(ztai);
					if(i==n)
					    continue;
					ztai^=(1<<W(j))*qq;
					ztai^=(1<<W(j+1))*qq;
					ghashin(ztai);
				}
			}
	    }
		for(int y=1;y<=tp[now^1];y++)
			q[now^1][y]=(q[now^1][y]<<2);
	}
	ans=ans+ans;
	printf("%d",ans.x[ans.x[0]]);
	for(int i=ans.x[0]-1;i>0;i--)
	    printf("%08d",ans.x[i]);
	getchar();
	getchar();
}