C++14(g++5.4) 解法, 执行用时: 7ms, 内存消耗: 760K, 提交时间: 2020-06-19 22:38:44

#include<bits/stdc++.h>
#define Fox ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
const int N=1e5+10;
const int mod=100000000;
int n,m,x;
int dp[13][(1<<13)],mp[13];
int main(){
	Fox;
	while(cin>>n>>m){
		memset(mp,0,sizeof(mp));
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
			for(int j=0;j<m;j++){
				cin>>x;
				mp[i]=(mp[i]<<1)+x;
			}
		dp[0][0]=1;
		for(int i=1;i<=n;i++)
			for(int j=0;j<(1<<m);j++){
				if((j&mp[i])!=j)continue;
				if(j&(j>>1))continue;
				for(int k=0;k<(1<<m);k++){
					if(j&k)continue;
					dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
				}
			}
		int ans=0;
		for(int i=0;i<(1<<m);i++)ans=(ans+dp[n][i])%mod;
		cout<<ans<<"\n";	
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 11ms, 内存消耗: 840K, 提交时间: 2020-06-02 15:49:45

#include<bits/stdc++.h>
using namespace std;

const int mod=1e8;
int DP[15][1<<13],V[15];
int main()
{
    int i,j,k,n,m,ans;
	while(~scanf("%d%d",&n,&m))
	{
		memset(DP,0,sizeof(DP)),memset(V,0,sizeof(V));
		for(i=1;i<=n;i++)
	        for(j=0;j<m;j++)scanf("%d",&k),V[i]|=(k<<j);
	    for(DP[0][0]=i=1;i<=n;i++)
	    {
	    	for(j=0;j<(1<<m);j++)
	    	{
	    		if((j&(j>>1))||((V[i]|j)!=V[i]))continue;
				for(k=0;k<(1<<m);k++)
	    		{
	    			if(k&j)continue;
	    			DP[i][j]=(DP[i][j]+DP[i-1][k])%mod;
				}
			}
		}
		for(ans=i=0;i<(1<<m);i++)ans=(ans+DP[n][i])%mod;
		printf("%d\n",ans);
	}
    return 0;
}

Python3 解法, 执行用时: 147ms, 内存消耗: 2852K, 提交时间: 2021-06-08 22:58:24

MOD = 100000000

while True:
	try:
		n, m = map(int, input().split())
		a = [list(map(int, input().split())) for _ in range(n)]
		f = [0] * (1 << m)
		f[0] = 1
		for i in range(n):
			g, b = [0] * (1 << m), []
			for j in range(m):
				if a[i][j] == 1: b.append(j)
			for j in range(1 << len(b)):
				t = 0
				for k in range(len(b)):
					if (j & (1 << k)) != 0: t |= 1 << b[k]
				if (t & (t >> 1)) != 0: continue
				for k in range(1 << m):
					if f[k] != 0 and (k & t) == 0:
						g[t] = (g[t] + f[k]) % MOD
			f = g
		print(sum(f) % MOD)
	except:
		break