自动搬运

查看原文

来自洛谷，原作者为

	real60t 3

搬运于2025-08-24 21:26:14，当前版本为作者最后更新于2021-09-16 20:59:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P1539题解

1.分析

数据范围: $n\times m\le225$。

则 $\min(m,n)\le15$。我们可以将较小值作为的列数，再对每一行进行状压，用 $c$ 数组储存每行方案，dp 求解。

我们算一下时间复杂度，由于相邻不能同时为 1，所以很多情况都被舍掉，所以当 $m=15$ 时，每一行只有 1597 种情况，不会超时。

但题目给出的矩阵有些数已经填好，无法改变，这怎么处理呢？

设 $s_i$ 为第 $i$ 行已填数字 1 的分布情况，$t_i$ 为第 $i$ 行已填数字 0 的分布情况。如果第 $i$ 行中方案 $c_k$ 满足 $(t_i\;and\;c_k)=t_i$ 且 $s_i\;and\;(not\;c_k)=s_i$，则方案 $k$ 不与已填数字冲突。

最后的 dp 就比较简单了，设 $f[i][j]$ 为第 $i$ 行使用第 $j$ 种方案的方法数，$d$ 每行合法方案种数。

状态转移方程：$f[i][j]=\sum\limits_{k=1}^df[i-1][k](c[j]\;and\;c[k]=0)$。

最终答案：$ans=\sum\limits_{i=1}^df[n][i]$。

初始化：$f[0][1]=0$。

时间复杂度：$\mathcal O(nd^2)$。

2.Code

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int mod=10007;
int n,m=15,ans,t[230],s[230],c[1600],f[230][1600];
char a[230][230],b[230][230];
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%s",a[i]+1);
	//如果n<m,将矩阵顺时针旋转90度,以保证列数m<=15 
	if(n<m) {
		swap(n,m);
		memcpy(b,a,sizeof(b));
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)a[i][j]=b[m-j+1][i];		
	}
	//预处理s,t数组 
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) {
			if(a[i][j]=='1')s[i]+=1<<m-j;
			if(a[i][j]=='0')t[i]+=1<<m-j;
		}
	}	
	//预处理每行方案,存入数组c 
	for(int i=0;i<1<<m;i++) 
		if(!(i>>1&i))c[++c[0]]=i;
	f[0][1]=1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=c[0];j++) {
			//判断方案是否合法 
			if((s[i]&c[j])!=s[i])continue;
			if((t[i]&(~c[j]))!=t[i])continue;
			for(int k=1;k<=c[0];k++) 
				if(!(c[j]&c[k]))f[i][j]=(f[i][j]+f[i-1][k])%mod;
		}
	}
	for(int i=1;i<=c[0];i++)ans=(ans+f[n][i])%mod;
	printf("%d",ans);
	return 0;
}