记录编号	158765	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[CQOI2015]标识设计	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	5.302 s
提交时间	2015-04-17 17:12:44	内存使用	240.98 MiB

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <ctime>
#include <cctype>
#include <algorithm>
#include <cmath>
using namespace std;
#define USEFREAD
#ifdef USEFREAD
#define InputLen 1000
char CHARPOOL[InputLen], *ptr=CHARPOOL;
#define getc() (*(ptr++))
#else
#define getc() (getchar())
#endif
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout))
template<class T>inline void getd(T &x){
    char ch = getc();bool neg = false;
    while(!isdigit(ch) && ch != '-')ch = getc();
    if(ch == '-')ch = getc(), neg = true;
    x = ch - '0';
    while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
    if(neg)x = -x;
}
/***********************************************************************/
typedef long long LL;
LL f[4][4095][2][31][31], Ans;//f[放了几个][列覆盖状态][是否要向右延伸][x][y] = 方案数
int N, M, ST[4096], trv[4096][31], Scnt = 1;
#define id(x) (lower_bound(ST, ST + Scnt, x) - ST)
#define bin(x) (1 << x)
bool G[31][31];

inline void init(){
	getd(N), getd(M);
	memset(f, -1, sizeof(f));
	int i, j, k, t;
	for(i = 0;i < N;++i){
		while((k = getc()) != '.' && k != '#');
		for(j = 0;j < M;++j){
			G[i][j] = (k == '#');
			k = getc();
		}
	}
	for(i = 0;i+1 < M;++i){
		ST[Scnt++] = bin(i);
		for(j = 0;j < i;++j){
			ST[Scnt++] = bin(i) | bin(j);
			for(k = 0;k < j;++k)ST[Scnt++] = bin(i) | bin(j) | bin(k);
		}
	}
	for(i = 0;i < Scnt;++i)for(j = 0,t = 1;j+1 < M;++j, t <<= 1)if(ST[i] & t)
		trv[trv[i][j] = id(ST[i] ^ t)][j] = i;
}
LL dp(bool lk, int cnt, int i, int j, int St){
	LL &ans = f[cnt][St][lk][i][j];
	if(~ans)return ans;
	ans = 0;
	if(i == N)return ans = (!lk && !St && !cnt);
	if(j == M){if(!lk)ans = dp(0,cnt,i+1,0,St);return ans;}
	register int b = bin(j), st = ST[St];
	if(lk && (b & st))return 0;
	if(lk){//from left
		if(G[i][j])return 0;
		return ans = dp(0,cnt,i,j+1,St) + dp(1,cnt,i,j+1,St);
	}
	if(b & st){//from above
		if(G[i][j])return 0;
		return ans = dp(1,cnt,i,j+1,trv[St][j]) + dp(0,cnt,i,j+1,St);
	}
	ans = dp(0,cnt,i,j+1,St);//skip 
	if(!G[i][j] && cnt && j+1 < M)ans += dp(0,cnt-1,i,j+1,trv[St][j]);// new
	return ans;
}

int main(){
	#ifdef DEBUG
	freopen("test.txt", "r", stdin);
	#else
	SetFile(cqoi15_logo);
	#endif
	#ifdef USEFREAD
	fread(ptr,1,InputLen,stdin);
	#endif
	init();
	printf("%lld\n", dp(0,3,0,0,0));
	
#ifdef DEBUG
    printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
    return 0;
}