记录编号	174700	评测结果	AAAAAAAAAA
题目名称	[USACO Nov06] 牧场的安排	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2015-08-02 17:04:20	内存使用	33.58 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=18;
const int maxs=1<<18;
int map[maxn][maxn],As[maxs],mp[maxn];
long long opt[maxn][maxs];
int n,m,cnt=0;

bool check(int x){
    if (x&(x<<1)) return 0;
    return 1;
}

void findAs(int n){
    for (int i=0;i<1<<n;++i)
       if (check(i))
          As[cnt++]=i;
}

int main()
{
	freopen("cowfood.in","r",stdin);
	freopen("cowfood.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
       for (int j=1;j<=m;++j){
           scanf("%d",&map[i][j]);
           if(map[i][j]==0) mp[i]|=(1<<j-1);
       }
    findAs(m); cnt--;
    for(int i=0;i<=cnt;i++)
        if(!(As[i]&mp[1]))
            opt[1][i]=1;
    for (int i=2;i<=n;++i)
       for (int j=0;j<=cnt;++j){
            if (As[j]&mp[i]) continue;
            for (int k=0;k<=cnt;++k){
                if (As[k]&As[j]) continue;
                opt[i][j]+=opt[i-1][k];
                opt[i][j]%=100000000;
            }
       }
    long long ans=0;
    for (int j=0;j<=cnt;++j)
           ans+=opt[n][j];
     printf("%lld",ans%100000000);
     return 0;
}