记录编号	410139	评测结果	AAAAAAAAAA
题目名称	[USACO Nov06] 牧场的安排	最终得分	100
用户昵称	BaDBoY	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-05-31 09:10:57	内存使用	0.59 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
using namespace std;
#define mod 100000000
inline int read(){
  int s=0,f=1; char ch=getchar();
  while(ch>'9'||ch<'0'){if(f=='-')f=-1; ch=getchar();}
  while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+ch-'0'; ch=getchar();} 
  return s*f;
}
int m,n,x,tot=0,s[10001];
int ch[15],f[15][1<<12|1];
inline bool check(int x){
  if((x&(x<<1))||(x&(x>>1))) return 0;
  else return 1;       
}
inline void init(){
  for(int i=0;i<(1<<m);i++)
   if(check(i))
     s[tot++]=i; 
  return ;
}
int main(){
   freopen("cowfood.in","r",stdin);
   freopen("cowfood.out","w",stdout);
   n=read(); m=read();
   init();
   for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
     x=read();
     if(!x)
      ch[i]|=(1<<(j-1));
    }
   for(int i=0;i<tot;i++)
    if(!(ch[1]&s[i]))
     f[1][s[i]]=1;
   for(int i=1;i<n;i++)
    for(int j=0;j<tot;j++)
     if(f[i][s[j]])
      for(int k=0;k<tot;k++)
       if(!(s[k]&s[j])&&!(ch[i+1]&s[k]))
        f[i+1][s[k]]+=f[i][s[j]];
   int ans=0;
   for(int i=0;i<(1<<m);i++)
    ans+=f[n][i];
   printf("%d\n",ans%mod);
   //cout<<clock();
   //while(1);
   return 0;
}