pypy3 解法, 执行用时: 98ms, 内存消耗: 25976K, 提交时间: 2023-04-08 15:59:42

mi = lambda :map(int,input().split())
li = lambda :list(mi())
ii = lambda :int(input())
m,n=li()
mat=[]
for _ in range(m):
    mat.append(li())
f=[0]*(1<<n)
mod=10**8
for i in range(m):
    nf=[0]*(1<<n)
    for tmp in range(1<<n):
        pre=-2
        for j in range(n):
            if tmp&(1<<j):
                if mat[i][j]==0:
                    break
                if j-pre==1:
                    break
                pre=j
        else:
            if i==0:
                nf[tmp]=1
            elif tmp==0:
                nf[tmp]=sum(f)
            else:
                s=(1<<n)-1
                for j in range(n):
                    if tmp&(1<<j):
                        s^=1<<j
                sub=s
                nf[tmp]=f[0]
                while sub:
                    nf[tmp]+=f[sub]
                    sub=(sub-1)&s
                nf[tmp]%=mod
    f=nf
print(sum(f)%mod)

C++(g++ 7.5.0) 解法, 执行用时: 3ms, 内存消耗: 412K, 提交时间: 2023-03-09 15:16:29

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e8;
int m,n;
int dp[13][401],a[13][13],s[13];
vector<int> v;
int main(){
	
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>m>>n;
	for(int i=1;i<=m;++i){
		for(int j=0;j<n;++j){
			cin>>a[i][j];
		}
	}
	for(int i=0;i<1<<n;++i){
		if((i&(i<<1))==0) v.push_back(i);
	}
	for(int i=1;i<=m;++i){
		for(int j=0;j<n;++j){
			s[i]=(s[i]<<1)+a[i][j];
		}
	}
	dp[0][0]=1;
	for(int i=1;i<=m;++i){
		for(int j=0;j<v.size();++j){
			if((s[i]&v[j])==v[j]){
			    for(int k=0;k<v.size();++k){
			    	if((v[j]&v[k])==0) {
			    		dp[i][j]+=dp[i-1][k];
			    		dp[i][j]%=mod;
					}
				}     
			}
		}
	}
	ll ans=0;
	for(int i=0;i<v.size();++i){
		ans=(ans+dp[m][i])%mod;
	}
	cout<<ans;
	
	return 0;
} 

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 624K, 提交时间: 2019-08-03 23:06:56

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,dp[13][401],a[13][13],s[13];
const int mod = pow(10,8);
vector<int> v;
int main()
{
	cin>>n>>m;
	for(int i = 0;i<1<<m;i++)
        if(((i<<1)&i)==0)
			v.push_back(i);
	for(int i = 1;i<=n;i++)
		for(int j = 0;j<m;j++)
			scanf("%d",&a[i][j]);
	for(int i = 1;i<=n;i++)
		for(int j=0;j<m;++j)
			s[i] = (s[i]<<1)+a[i][j];			
	dp[0][0] = 1;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 0;j<v.size();j++)
		{
			if((v[j]&s[i])==v[j])
			{
				for(int k = 0;k<v.size();k++)
				{
					if((v[k]&v[j])==0)
					{
						dp[i][j]+=dp[i-1][k];
                        dp[i][j]%=mod;
					}				
				}
			}			
		}
	}
	ll ans = 0;
	for(int i = 0;i<v.size();i++)
		ans = (ans+dp[n][i])%mod;
	cout<<ans;
	return 0;
} 

C++ 解法, 执行用时: 4ms, 内存消耗: 456K, 提交时间: 2022-07-08 13:27:20

#include<iostream>
#include<vector>
using namespace std;
const int mod=1e8;
int n,m;
vector<int>v;
int dp[12][1<<12],x[12],cnt[1<<12];
int main(){
	cin>>n>>m;
	for(int i=0;i<1<<m;i++){
		if((i&i>>1)==0) v.push_back(i); 
	} 
	for(int i=1;i<=n;i++){
		for(int j=0;j<m;j++){
			int xx;
			cin>>xx;
			if(xx==0) x[i]+=1<<j; 
		}
	}
	dp[0][0]=1; 
	for(int i=1;i<=n+1;i++){
		for(auto k:v){
			if(x[i]&k) continue;
			for(auto l:v){
				if(k&l||x[i-1]&l) continue;
				dp[i][k]=(dp[i][k]+dp[i-1][l])%mod;
			}
		}
	}
	cout<<dp[n+1][0];
	return 0;
}