比赛 20150421 评测结果 AAAAWWWWWW
题目名称 走道铺砖问题 最终得分 40
用户昵称 ztx 运行时间 0.031 s
代码语言 C++ 内存使用 0.35 MiB
提交时间 2015-04-21 11:20:43
显示代码纯文本
/****************************************\
* Author : ztx
* Title  : [cogs] 1943. 走道铺砖问题
* ALG    : 状态压缩 (dp)?
* CMT    :
* Time   :
\****************************************/

#include <cstdio>
#define Rep(i,l,r) for(i=(l);i<=(r);i++)
#define rep(i,l,r) for(i=(l);i< (r);i++)
#define Rev(i,r,l) for(i=(r);i>=(l);i--)
#define rev(i,r,l) for(i=(r);i> (l);i--)
unsigned typedef long long ll ;
int CH , NEG ;
template <typename TP>inline void read(TP& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}
template <typename TP>inline void readc(TP& ret) {
	while (ret=getchar() , ret<'!') ;
	while (CH=getchar() , CH>'!') ;
}
template <typename TP>inline void reads(TP *ret) {
	ret[0]=0;while (CH=getchar() , CH<'!') ;
	while (ret[++ret[0]]=CH,CH=getchar(),CH>'!') ;
}

#include <cstring>

ll bits[20] = {0ULL,1ULL,2ULL,4ULL,8ULL,16ULL,32ULL,64ULL,128ULL,256ULL,512ULL,1024ULL,2048ULL,4096ULL} ;
ll cnt[2][4096]={0ULL};
/* 记录当前行到达某状态的方案总数,和到达下一行某状态的方案总数 */
int m , n ;

ll sta1 , sta2 ;
bool now,next;

void dfs(int 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) ;
}

int main() {
int i;
	#define READ
	#ifdef  READ
		freopen("floor.in" ,"r",stdin ) ;
		freopen("floor.out","w",stdout) ;
	#endif
	read(n) , read(m) ;
	if (n<m) { n^=m,m^=n,n^=m; }
	cnt[1][0] = 1ULL ;
	Rep (i,1,n) {
		now=i&1,next=now^1;
		rep(sta1,0,bits[m+1]) cnt[next][sta1] = 0ULL ;
		rep (sta1,0,bits[m+1])
			if (cnt[now][sta1])
				sta2 = 0 , dfs(1) ;
	}
	printf("%llu\n", cnt[next][0]) ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}