比赛 20150421 评测结果 AAAAWWWWWW
题目名称 走道铺砖问题 最终得分 40
用户昵称 new ioer 运行时间 0.074 s
代码语言 C++ 内存使用 0.35 MiB
提交时间 2015-04-21 11:25:07
显示代码纯文本
#include<cstdio>
#include<cstring>
typedef unsigned long long lnt;

lnt bits[20] = {0,1,2,4,8,16,32,64,128,256,512,1024,2048,4096} ;
lnt cnt[2][4096]= {0};
lnt m , n ,i , sta1 , sta2 ;
bool now,next;

void dfs(lnt o) {
	while (sta1&bits[o]) o ++ ;
	if (o > m) {
		cnt[next][sta2]+=cnt[now][sta1] ;
		return ;
	}
	sta2 += bits[o] ;
	dfs(o+1) ;
	sta2 -= bits[o] ;
	if (o<m && !(sta1&bits[o+1])) dfs(o+2) ;
}

main() {
	freopen("floor.in" ,"r",stdin ) ;
	freopen("floor.out","w",stdout) ;
	scanf("%d%d",&n,&m);
	if (n<m) {
		n^=m,m^=n,n^=m;
	}
	cnt[1][0] = 1 ;
	for(i=1; i<=n; i++) {
		now=i&1,next=now^1;
		memset(cnt[next],0,sizeof cnt[next]) ;
		for(sta1=0; sta1<bits[m+1]; sta1++)
			if (cnt[now][sta1])
				sta2 = 0 , dfs(1) ;
	}
	printf("%llu\n", cnt[next][0]) ;
	return 0 ;
}