题目
#include<cstdio> #include<algorithm> using namespace std; const int N=12+1,mod=1e8; int sta[N],dp[N][1<<(N-1)],A[1<<(N-1)+1]; int main(){ int n,m,t;scanf("%d%d",&n,&m),t=(1<<m); for(int i=1;i<=n;++i){ for(int j=1,x;j<=m;++j){ scanf("%d",&x); if(!x) sta[i]|=(1<<(j-1)); } } int tot=0; for(int i=0;i<t;++i){ if(!(i&(i>>1))&&!(i&(i<<1))){ A[++tot]=i; if(!(i&sta[1])) dp[1][tot]=1; } } for(int i=2;i<=n;++i){ for(int j=1;j<=tot;++j){ if(A[j]&sta[i]) continue; for(int k=1;k<=tot;++k){ if(A[k]&sta[i-1]) continue; if(!(A[j]&A[k])) dp[i][j]+=dp[i-1][k],dp[i][j]%=mod; } } } int ans=0; for(int i=1;i<=tot;++i) ans+=dp[n][i],ans%=mod; printf("%d\n",ans); }