记录编号	159402	评测结果	AAAAAAAAAA
题目名称	走道铺砖问题	最终得分	100
用户昵称	真呆菌	是否通过	通过
代码语言	C++	运行时间	0.806 s
提交时间	2015-04-21 12:19:48	内存使用	8.19 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int MaxS = 4096;
const int D = 10000;
int n,m,nn;
int Max(int x,int y){if(x>y) return x;return y;}
void Swap(int &x,int &y){x=x^y;y=x^y;x=x^y;}

struct Bign{
	int len,c[251];
	Bign(){len=0;memset(c,0,sizeof(c));}
	void Initial(){len=0;memset(c,0,sizeof(c));}
	Bign operator + (const Bign&a) const{
		Bign t;
		int lim=Max(len,a.len),x=0;
		for(int i=1;i<=lim;i++){
			t.c[i]=c[i]+a.c[i]+x;
			x=t.c[i]/D;
			t.c[i]%=D;
		}
		if(x) t.c[++lim]=x;
		t.len=lim;
		return t;
	}
	void Print(){
		printf("%d",c[len]);
		for(int i=len-1;i>=1;i--) printf("%04d",c[i]);
		return;
	}
}f[MaxS+10],pre[MaxS+10];

void F(int now,int pre_sta,int now_sta){
	if(now>n) return;
	if(now==n){
		//f[now_sta]+=pre[pre_sta];
		f[now_sta]=f[now_sta]+pre[pre_sta];
		return;
	}
	F(now+1,pre_sta<<1,now_sta<<1|1);
	F(now+1,pre_sta<<1|1,now_sta<<1);
	F(now+2,pre_sta<<2|3,now_sta<<2|3);
	return;
}

int main(){
	#define READ
	#ifdef READ
		freopen("floor.in","r",stdin);
		freopen("floor.out","w",stdout);
	#endif
	scanf("%d%d",&n,&m);
	if(n>m) Swap(n,m);
	nn=(1<<n)-1;
	pre[nn].len=1;pre[nn].c[1]=1;
	for(int i=1;i<=m;i++){
		F(0,0,0);
		for(int j=0;j<=nn;j++) pre[j]=f[j],f[j].Initial();
	}
	pre[nn].Print();
	return 0;
}