玉米田Corn Fields

传送门

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
#define ll long long
#define re register
const int mod=1e8;
void read(int &a)
{a=0;int d=1;char ch;while(ch=getchar(),ch>'9'||ch<'0')if(ch=='-')d=-1;a=ch^48;while(ch=getchar(),ch>='0'&&ch<='9')a=(a<<3)+(a<<1)+(ch^48);a*=d;
}
int cnt,sta[505],f[15][1<<12+1],st[505];
inline bool solve(int x){return x&(x>>1);}
int main()
{int n,m;read(n);read(m);for(re int i=1;i<=n;i++)for(re int j=1;j<=m;j++){int x;read(x);if(!x)st[i]|=1<<(m-j);}int h=(1<<m)-1;for(re int i=0;i<=h;i++){if(solve(i))continue;sta[++cnt]=i;}for(re int i=1;i<=cnt;i++){if(st[1]&sta[i])continue;f[1][i]=1;}for(re int i=2;i<=n;i++)for(re int j=1;j<=cnt;j++){int last=sta[j];if(last&st[i-1])continue;for(re int k=1;k<=cnt;k++){int now=sta[k];if(now&st[i])continue;if(now&last)continue;(f[i][k]+=f[i-1][j])%=mod;}}int ans=0;for(re int i=1;i<=cnt;i++)(ans+=f[n][i])%=mod;printf("%d",ans);return 0;
}