比赛 20150421 评测结果 AAAAWWWWWW
题目名称 走道铺砖问题 最终得分 40
用户昵称 真呆菌 运行时间 0.060 s
代码语言 C++ 内存使用 0.38 MiB
提交时间 2015-04-21 11:28:50
显示代码纯文本
#include<cstdio>
#include<iostream>
using namespace std;
typedef unsigned long long ull;
const int MaxS = 4096;
int n,m,nn;
ull pre[MaxS+100],f[MaxS+100];
void Swap(int &x,int &y){x=x^y;y=x^y;x=x^y;}

void F(int now,int pre_sta,int now_sta){
	if(now>n) return;
	if(now==n){
		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]=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]=0;
	}
	printf("%llu\n",pre[nn]);
	return 0;
}