C++(g++ 7.5.0) 解法, 执行用时: 18ms, 内存消耗: 632K, 提交时间: 2023-05-31 15:09:04

#include <bits/stdc++.h>

#define ll long long 
#define int ll

using namespace std;

const int N = 20, M = (1 << 20), T = 60;
const int mod = 1e9 + 7;
int h, w, n, m;
char s[T];
int dp[N][M];   // 当第i行所有数状态为j时  0 1 0 1 0 0 
int d1[N][N];   // 当ij为奇数时候有多少种选择方案
int d2[N][N];
bool h1[N][N],h2[N][N];

signed main()
{
	scanf("%lld%lld%lld%lld", &h, &w, &n, &m);
	for(int i = 0; i < n; i ++ ) 
		for(int j = 0; j < m; j ++ ) d1[i][j] = d2[i][j] = 1;
	
	for(int i = 0; i < h; i ++ ) {
		scanf("%s", s);
		for(int j = 0; j < w; j ++ ) {
			if(s[j] == '.') {
				d1[i % n][j % m] = d1[i % n][j % m] * 5 % mod;
				d2[i % n][j % m] = d2[i % n][j % m] * 4 % mod;
			}
			else if((s[j] - '0') % 2) h1[i % n][j % m] = true;
			else h2[i % n][j % m] = true;
		}
	}
	
	for(int i = 0; i < n; i ++ )
		for(int j = 0; j < m; j ++ ) {
		if(h1[i][j] && h2[i][j]) {
			puts("0");
			return 0;
		}
	}
	dp[0][0] = 1;
	for(int i = 1; i <= n; i ++ ) {
		for(int j = 0; j <= (1 << m) - 1; j ++ ) {
			int sum = 1, tag = 0;
			bool flag = false;
			for(int k = 0; k < m; k ++ ) {
				if(j & (1 << k)) {  // 奇数
					tag ++ ;
					sum = sum * d1[i - 1][k] % mod;
					if(h2[i - 1][k]) {
						flag = true;
						break;
					}
				}
				else {   // 偶数
					sum = sum * d2[i - 1][k] % mod;
					if(h1[i - 1][k]) {
						flag = true;
						break;
					}
				}
			}
			
			if(flag || tag % 2 == 0) continue;
			for(int l = 0; l <= (1 << m) - 1; l ++ ) {
				dp[i][l ^ j] = (dp[i][l ^ j] + dp[i - 1][l] * sum) % mod;
			}
		}
	}
	
	printf("%lld\n", dp[n][(1 << m) - 1]);
	return 0;
}

C++ 解法, 执行用时: 48ms, 内存消耗: 820K, 提交时间: 2021-08-21 14:36:23

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
char st[100][100];
ll a[20][20],b[20][20],dp[20][1<<11],mod=1e9+7;
bool aa[20][20],bb[20][20];
int main() {
	int h,w,n,m,i,j,k,p;
	cin>>h>>w>>n>>m;
	char s[100];
	for(i=0;i<n;i++){
		for(j=0;j<m;j++)
		a[i][j]=b[i][j]=1; 
	}
	for(i=0;i<h;i++){
		scanf("%s",s);
		for(j=0;j<w;j++){
			if(s[j]=='.'){
				a[i%n][j%m]=a[i%n][j%m]*5%mod;
				b[i%n][j%m]=b[i%n][j%m]*4%mod;
			}
			else if((s[j]-'0')%2)
			aa[i%n][j%m]=1;
			else
			bb[i%n][j%m]=1;
		}
	}
	for(i=0;i<n;i++){
		for(j=0;j<m;j++){
			if(aa[i][j]&&bb[i][j]){
			puts("0");
			return 0;	
			}
		}
	}
	dp[0][0]=1;
	for(i=1;i<=n;i++){
		for(j=0;j<(1<<m);j++){
			ll sum=1,tag=0,f=0;
			for(k=0;k<m;k++){
				if((1<<k)&j){
					tag^=1;
					if(bb[i-1][k]){
					f=1;
					break;	
					}
					sum=(sum*a[i-1][k])%mod;
				}
				else{
					if(aa[i-1][k]){
					f=1;
					break;	
					}
					sum=(sum*b[i-1][k])%mod;
				}	
			}
			if(f==1||tag==0)
			continue;
				for(p=0;p<(1<<m);p++)
					dp[i][j^p]=(dp[i][j^p]+sum*dp[i-1][p])%mod;	
		}
	}
	cout<<dp[n][(1<<m)-1];
  return 0;
}