【BZOJ1210】[HNOI2004]邮递员

Description

Smith在P市的邮政局工作，他每天的工作是从邮局出发，到自己所管辖的所有邮筒取信件，然后带回邮局。他所管辖的邮筒非常巧地排成了一个m*n的点阵（点阵中的间距都是相等的）。左上角的邮筒恰好在邮局的门口。 Smith是一个非常标新立异的人，他希望每天都能走不同的路线，但是同时，他又不希望路线的长度增加，他想知道他有多少条不同的路线可走。【任务描述】你的程序需要根据给定的输入，给出符合题意的输出： 输入包括点阵的m和n的值； 你需要根据给出的输入，计算出Smith可选的不同路线的总条数；

Input

只有一行。包括两个整数m, n(1 <= m <= 10, 1 <= n <= 20)，表示了Smith管辖内的邮筒排成的点阵。

Output

只有一行，只有一个整数，表示Smith可选的不同路线的条数。

Sample Input

2 2
说明：该输入表示，Smith管辖了2*2的一个邮筒点阵。

Sample Output

题解：同1814，只不过需要高精度。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int limit=199917;

int hs[limit];	//队列，存编号

int n,m,k,tot[2];

char str[20];

int state[2][limit];	//state:编号存hash值 dp:编号存dp值

struct Cbig

{

	int v[20],len;

	Cbig() {memset(v,0,sizeof(v)),len=1;}

	inline Cbig operator + (const Cbig &b) const

	{

		Cbig c;

		c.len=max(len,b.len);

		for(int i=1;i<=c.len;i++)

		{

			c.v[i]+=v[i]+b.v[i];

			if(c.v[i]>100000000)	c.v[i]-=100000000,c.v[i+1]++;

		}

		if(c.v[c.len+1])	c.len++;

		return c;

	}

	inline void print()

	{

		printf("%d",v[len]);

		for(int i=len-1;i;i--)	printf("%08d",v[i]);

	}

}ans,dp[2][limit];

inline void upd(int S,Cbig tag)

{

	int pos=S%limit;

	while(hs[pos])

	{

		if(state[k][hs[pos]]==S)

		{

			dp[k][hs[pos]]=dp[k][hs[pos]]+tag;

			return ;

		}

		pos++;

		if(pos==limit)	pos=0;

	}

	hs[pos]=++tot[k];

	state[k][tot[k]]=S;

	dp[k][tot[k]]=tag;

}

int main()

{

	int i,j,t,u,tmp,p,q,x,y;

	int S,T;

	Cbig tag;

	scanf("%d%d",&m,&n);

	if(n==1||m==1)

	{

		puts("1");

		return 0;

	}

	tot[0]=1,state[0][1]=0,dp[0][1].len=dp[0][1].v[1]=1;

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=m;j++)

		{

			k^=1;

			memset(hs,0,sizeof(hs));

			memset(state[k],0,sizeof(state[k][0])*(tot[k]+1));

			memset(dp[k],0,sizeof(dp[k][0])*(tot[k]+1));

			tot[k]=0;

			for(t=1;t<=tot[k^1];t++)

			{

				S=state[k^1][t],tag=dp[k^1][t];

				y=j<<1,x=y-2,p=(S>>x)&3,q=(S>>y)&3,T=S^(p<<x)^(q<<y);

				if(p==0&&q==0&&j<m&&i<n)	upd(T|(1<<x)|(2<<y),tag);

				if((p==0&&q==1)||(p==1&&q==0))

				{

					if(i<n)	upd(T|(1<<x),tag);

					if(j<m)	upd(T|(1<<y),tag);

				}

				if((p==0&&q==2)||(p==2&&q==0))

				{

					if(i<n)	upd(T|(2<<x),tag);

					if(j<m)	upd(T|(2<<y),tag);

				}

				if(p==2&&q==1)	upd(T,tag);

				if(p==1&&q==2&&i==n&&j==m)	ans=ans+tag;

				if(p==1&&q==1)

				{

					for(tmp=0,u=y+2;u<=m+m&&tmp>=0;tmp+=((T>>u)&1)-((T>>(u+1))&1),u+=2);

					u-=2;

					upd(T^(3<<u),tag);

				}

				if(p==2&&q==2)

				{

					for(tmp=0,u=x-2;u>=0&&tmp>=0;tmp+=((T>>(u+1))&1)-((T>>u)&1),u-=2);

					u+=2;

					upd(T^(3<<u),tag);

				}

			}

		}

		for(t=1;t<=tot[k];t++)	state[k][t]<<=2;

	}

	ans=ans+ans;

	ans.print();

	return 0;

}

Smith