记录编号	241958	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]画圈圈	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.206 s
提交时间	2016-03-26 11:43:08	内存使用	1.14 MiB

#include<cstdio>
#include<map>
#include<cstring>
#include<iostream>
using namespace std;
const int SIZEN=21,SIZEM=13,MOD=123456791;
typedef long long LL;
LL f[2][9000];
int c[20][9000];
int s[SIZEN][SIZEM];//1表示在内部，2表示在外部
int P;//状态的数量
int N,M;
void read()
{
	scanf("%d%d",&N,&M);
	P=1<<M<<1;
	for(int i=1;i<=N;i++)
	{
		char str[SIZEM];
		scanf("%s",str);
		for(int j=1;j<=M;j++)
		{
			if(str[j-1]=='.') s[i][j]=0;
			if(str[j-1]=='*') s[i][j]=1;
			if(str[j-1]=='#') s[i][j]=2;
		}
	}
}
int get(int x,int t)
{
	return (x>>t)&1;
}
void DP()
{
	int hx,hy;
	f[0][0]=1;
	hy=0;hx=1;
	for(int i=1;i<=N;i++)
	{
		swap(hx,hy);memset(f[hy],0,sizeof(f[hy]));
		for(int j=0;j<(P>>1);j++) f[hy][j<<1]=f[hx][j];
		for(int j=1;j<=M;j++)
		{
			swap(hx,hy);memset(f[hy],0,sizeof(f[hy]));
			for(int st=0;st<P;st++)
			{
				int p=1<<(j-1),q=1<<j;
				int x=get(st,j-1),y=get(st,j);
				if(s[i][j])
				{
					if(x||y) continue;
					int tem=0;
					if(j>1) tem=c[j-2][st];else tem=0;
					if(tem%2==s[i][j]%2) f[hy][st]=(f[hy][st]+f[hx][st])%MOD;
					continue;
				}
				f[hy][st^p^q]=(f[hy][st^p^q]+f[hx][st])%MOD;
				if(x!=y) f[hy][st]=(f[hy][st]+f[hx][st])%MOD;
			}
		}
	}
	printf("%lld",f[hy][0]);
}
void work()
{
	for(int st=0;st<P;st++)
	{
		c[0][st]=get(st,0);
		for(int i=1;i<=M;i++) c[i][st]=c[i-1][st]+get(st,i);
	}
	DP();
}
int main()
{
	freopen("nt2011_circle.in","r",stdin);
	freopen("nt2011_circle.out","w",stdout);
	read();
	work();
	return 0;
}