C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-08-18 22:20:11

#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define turn_on_clock clock_t start,end;start=clock();
#define turn_off_clock end=clock();printf("\nTime eclipse:%.5lfms\n",(double)(end-start)/CLOCKS_PER_SEC*1000);
using namespace std;
const int mod=100000000;
int n,m,opt,valid[13];
int dp[2][1<<13];
int main(){
	Fox;
	cin>>n>>m;
	for(int i=0;i<n;i++)
		for(int j=0,x;j<m;j++){
			cin>>x;
			valid[i]|=(1<<j)*x;
		}
	for(int i=0;i<(1<<m);i++)
		if(((i>>1)&i)==0 && (i|valid[0])==valid[0])dp[0][i]=1;
	for(int i=1;i<n;i++){
		opt=(i%2);
		memset(dp[opt],0,sizeof(dp[opt]));
		for(int j=0;j<(1<<m);j++){
			if((j|valid[i])!=valid[i])continue;
			if((j>>1)&j)continue;
			for(int k=0;k<(1<<m);k++){
				if(j&k)continue;
				dp[opt][j]=(dp[!opt][k]+dp[opt][j])%mod;
			}
		}
	}
	opt=(n-1)%2;
	int ans=0;
	for(int i=0;i<(1<<m);i++)ans=(ans+dp[opt][i])%mod;
	cout<<ans;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 3ms, 内存消耗: 400K, 提交时间: 2020-08-07 12:43:11

#include <cstdio>
#include <iostream>
using namespace std;
const int P = 100000000;
int m, n, a, x[13], f[13][1<<12], M, ans = 0;
bool v[1<<12];

int main() {
	cin >> m >> n;
	M = (1 << n);
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++) {
			cin >> a;
			(x[i] <<= 1) += a;
		}
	for (int i = 0; i < M; i++) v[i] = !(i & (i << 1)) && !(i & (i >> 1));
	f[0][0] = 1;
	for (int i = 1; i <= m; i++)
		for (int j = 0; j < M; j++)
			if (v[j] && ((j & x[i]) == j))
				for (int k = 0; k < M; k++)
					if (!(k & j)) f[i][j] = (f[i][j] + f[i-1][k]) % P;
	for (int i = 0; i < M; i++) (ans += f[m][i]) %= P;
	cout << ans << endl;
	return 0;
}