记录编号	173909	评测结果	AAAAAAAAAA
题目名称	[USACO Nov06] 牧场的安排	最终得分	100
用户昵称	0	是否通过	通过
代码语言	C++	运行时间	0.006 s
提交时间	2015-07-30 16:42:29	内存使用	0.53 MiB

# include <cstdio>
# include <iostream>
# include <cstring>

# define MAXN 15
# define MAXC (1 << 12) +1
//							一共有 2^12 种状态 

using namespace std;

const int Mod = 100000000;

int m,n,tot;
int able[MAXC];
int f[13][MAXC];													
int sta[13];                                                
int map[13];													 

int main() {
	freopen("cowfood.in","r",stdin);
	freopen("cowfood.out","w",stdout);
	int i,j,pos,k;
	sta[0] = 1;
	for(i = 1; i < 13; i++)	sta[i] = 1 << i;
	scanf("%d %d",&m,&n);
	for(i = 1;i <= m; ++i)
		for(j = 1;j <= n; ++j){
			scanf("%d",&pos);
			map[i] = (map[i] << 1) + pos;
//			printf("pos = %d map[%d] = %d\n",pos,i,map[i]);//一个数字表示出了状态 ，就来说，map[1] = 7; 1 1 1 11 11 11 111
															// map[2] = 2 ;    1 0  
		}
	for(k = 0;k <= sta[n] - 1 ;++k){
//		printf("k = %d k >> 1 = %d k & (k >> 1) = %d\n",k,k >> 1,k & (k >> 1));
		if((k & (k >> 1)) == 0)	able[++tot] = k;
	}
//	printf("%d\n",tot);
	for(i = 1; i <= tot;++i){
//		printf("map[1] = %d able[%d] = %d map[1] | able[%d] = %d\n",map[1],i,able[i],i,map[1] | able[i]);
		if((map[1] | able[i]) == map[1]) f[1][i] = 1;
	}
	for(i = 2;i <= m;++i)
		for(j = 1;j <= tot;++j)
			for(k = 1;k <= tot;++k){
//				printf("able[j]=%d,able[k]=%d,able[j]&able[k]=%d,able[j]=%d,map[i]=%d,able[j]|map[i]=%d\n",able[j],able[k],able[j]&able[k],able[j],map[i],able[j] | map[i]);
				if((able[j] & able[k]) == 0 && (able[j] | map[i]) == map[i]){
					f[i][j] = (f[i][j] + f[i - 1][k]) % Mod;
//					printf("f[i][j] = %d\n",f[i][j]);
				}
			}	
	for(i = 1;i <= tot;i++)	f[m][0] = (f[m][0] + f[m][i]) % Mod;
	printf("%d",f[m][0]);	
}