记录编号	38162	评测结果	AAAAAAAAAA
题目名称	[USACO Nov06] 牧场的安排	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-04-14 13:32:07	内存使用	0.30 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#define MAXN 4097 //2^12+1
using namespace std;
int A,B,M=0,able[MAXN],Map[13],F[13][500];
int binary[13]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096};
const int MOD=100000000;
int main()
{
	freopen("cowfood.in","r",stdin);
	freopen("cowfood.out","w",stdout);
	scanf("%d %d\n",&A,&B);  
	memset(Map,0,sizeof(Map)); int m;
	for(int i=1;i<=A;i++) 
		for(int j=1;j<=B;j++)  {scanf("%d",&m);Map[i]=(Map[i]<<1)+m;}
	for(int k=0;k<=binary[B]-1;k++) 
		if((k&(k>>1))==0) able[++M]=k;
	memset(F,0,sizeof(F)); 
	for(int i=1;i<=M;i++) 
		if((Map[1]|able[i])==Map[1]) F[1][i]=1;
	for(int i=2;i<=A;i++)
		for(int j=1;j<=M;j++) 
			for(int k=1;k<=M;k++)
				if((able[j]&able[k])==0 && (able[j]|Map[i])==Map[i]) 
					F[i][j]=(F[i][j]+F[i-1][k])%MOD;
	for(int i=1;i<=M;i++) F[A][0]=(F[A][0]+F[A][i])%MOD;
	printf("%d\n",F[A][0]);				
	return 0;
}