输入：

12 12
0 0 1 1 1 1 0 0 0 0 1 0
0 0 1 0 0 0 0 1 0 0 0 1
0 1 0 0 1 0 1 0 1 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 1 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 1 0
1 1 0 1 0 1 0 0 0 0 0 1
0 1 0 0 0 0 0 0 0 1 0 1
1 0 0 0 1 1 0 0 0 0 1 1
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0

期望输出：

13416960

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 100000000
ll n,m,op[1005][1005],rep[1005][1005],tot[1000000],f[1005][1005];
ll er[1000000];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		er[i]=(1<<(i-1));
	}
	ll sum=(1<<m)-1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>op[i][j];
		}
		for(int j=0;j<=sum;j++){
			ll opp=1;
			for(int k=0;k<m;k++){
				if(((j>>k)&1)&&((j>>(k+1))&1)){
					opp=0;
					break;
				}
				if((j&er[k+1])&&op[i][k+1]==0){
					opp=0;
					break;
				}
				if(((j&er[k+2]))&&op[i][k+2]==0){
					opp=0;
					break;
				}
			}
			if(opp){
				rep[i][++tot[i]]=j;
			}
		}
	}
	for(int i=1;i<=tot[1];i++){
		f[1][rep[1][i]]=1;
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=tot[i];j++){
			ll x=rep[i][j];
			for(int k=1;k<=tot[i-1];k++){
				ll y=rep[i-1][k],opp=1;
				for(int o=1;o<=m;o++){
					if((x&er[o])&&(y&er[o])){
						opp=0;
					}
				}
				if(opp){
					//cout<<i<<":"<<x<<" "<<y<<endl;
					f[i][x]=(f[i-1][y]+f[i][x])%mod;
				}
			}
		}
	}
	ll ans=0;
	for(int i=0;i<=sum;i++){
		ans=(f[n][i]+ans)%mod;
	}
	cout<<ans%mod;
}