记录编号	194443	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 邮递员	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.204 s
提交时间	2015-10-16 17:14:29	内存使用	1.08 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int SIZEN=10,SIZEM=20,BASE=200000,SIZEC=50,BA=100000;
typedef long long LL;
int N,M;//N是列
int H[BASE];
class poi
{
public:
	int n;
	int s[SIZEC];
	void operator = (int a)
	{
		n=1;
		memset(s,0,sizeof(s));
		s[0]=a;
	}
	void operator += (poi a)
	{
		n=max(n,a.n)+1;
		for(int i=0;i<=n;i++)
		{
			s[i]+=a.s[i];
			s[i+1]+=s[i]/BA;
			s[i]%=BA;
		}
		while(n>0&&s[n-1]==0) n--;
	}
	void operator *= (int a)
	{
		n++;
		for(int i=0;i<=n;i++) s[i]*=a;
		for(int i=0;i<=n;i++)
		{
			s[i+1]+=s[i]/BA;
			s[i]%=BA;
		}
		while(n>0&&s[n-1]==0) n--;
	}
	void print()
	{
		printf("%d",s[n-1]);
		for(int i=n-2;i>=0;i--) printf("%05d",s[i]);
	}
};
poi ans;
class miku
{
    public:
	poi sum;
	LL id;
	miku(){}
	miku(LL a,poi b)
	{
		id=a,sum=b;
	}
};
deque<miku> f[2];
void read()
{
	scanf("%d%d",&N,&M);
	if(N<M) swap(N,M);
}
int get(int x,int j)
{
	x>>=2*(j-1);
	x&=3;
	return x;
}
int change(int x,int j,int t)//把id的第j位改成t
{
	int tem=x>>(2*(j-1));
	x-=tem<<(j-1)*2;tem>>=2;x+=tem<<2*j;x+=t<<((j-1)*2);
	return x;
}
void check(int a)
{
	for(int i=1;i<=M+1;i++)
		cout<<get(a,i)<<" ";
	cout<<endl;
}
int find(int x,int j,int dat)
{
	int now=dat,k=j;
	while(k>=1&&k<=M+1)
	{
		k+=now;
		int tem=get(x,k);
		if(tem==1) dat++;
		if(tem==2) dat--;
		if(dat==0) return k;
	}
	cout<<"fuck"<<endl;
	return -1;
}
void push(int k,int id,poi sum)
{
	int now=id%BASE;
	//cout<<"k:"<<k<<" "<<id<<" "<<sum<<endl;
	//check(id);
	while(H[now])
	{
		if(f[k][H[now]].id==id)
		{
			f[k][H[now]].sum+=sum;
			return;
		}
		now++;
		if(now==BASE) now=0;
	}
	H[now]=f[k].size();
	f[k].push_back(miku(id,sum));
}
void work()
{
	int k=0;
	poi p;
	p=1;
	f[k].push_back(miku(0,p));
	for(int i=1;i<=N;i++)
	{
		for(int j=1;j<=M;j++)
		{
			k^=1;
			f[k].clear();
			memset(H,0,sizeof(H));
			for(int km=0;km<f[k^1].size();km++)
			{
				int id=f[k^1][km].id;
				poi date=f[k^1][km].sum;
				int L=get(id,j),U=get(id,j+1);
				//cout<<"i:"<<i<<" "<<"j:"<<j<<endl;
				//check(id);
				//cout<<date<<" "<<L<<" "<<U<<endl;
				int tem;
				if(!L&&!U)
				{
					if(i!=N&&j!=M)
					{
						tem=change(id,j,1);tem=change(tem,j+1,2);
						push(k,tem,date);
					}
				}
				else if(!L&&U)
				{
					if(j!=M) push(k,id,date);
					if(i!=N)
					{
						tem=change(id,j,U);tem=change(tem,j+1,0);
						push(k,tem,date);
					}
				}
				else if(L&&!U)
				{
					if(i!=N) push(k,id,date);
					if(j!=M)
					{
						tem=change(id,j,0),tem=change(tem,j+1,L);
						push(k,tem,date);
					}
				}
				else if(L==1&&U==1)
				{
					tem=change(id,find(id,j+1,1),1);
					tem=change(tem,j,0);tem=change(tem,j+1,0);
					push(k,tem,date);
				}
				else if(L==2&&U==2)
				{
					tem=change(id,find(id,j,-1),2);
					tem=change(tem,j,0);tem=change(tem,j+1,0);
					push(k,tem,date);
				}
				else if(L==2&&U==1)
				{
					tem=change(id,j,0);tem=change(tem,j+1,0);
					push(k,tem,date);
				}
				else if(L==1&&U==2)
				{
					if(i==N&&j==M) ans+=date;
				}
			}
		}
		for(int km=0;km<f[k].size();km++) f[k][km].id<<=2;
	}
	ans*=2;
	ans.print();
}
int main()
{
	freopen("postman.in","r",stdin);
	freopen("postman.out","w",stdout);
	read();
	if(M==1) {printf("1");return 0;}
	work();
	return 0;
}