简单状压WA on #8,9,10,求条
查看原帖
简单状压WA on #8,9,10,求条
416192
kbzcz楼主2023/11/17 20:16
bool _Start;
#include <bits/stdc++.h>
using namespace std;
#define _int __int128
#define LL long long
#define DB double
#define ull unsigned long long
#define PII pair<int,int>
#define Tp template<typename T>
#define Ts template<typename T,typename... _T>
Tp inline void read(T& x) {
	x=0;char c=getchar();bool f=0;
	for(;c<48||c>57;c=getchar()) f|=c=='-';
	for(;c>47&&c<58;c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	f&&(x=-x);
}Ts inline void read(T& x,_T&... y) {read(x),read(y...);}
const int INF=0x3f3f3f3f;
const LL LNF=1e18;
const int N=230,mod=1e4+7;
int n,m;
int a[N][N],cst[N][2];
int stu[N],cnt;
LL f[N][1<<15],ans;
bool _End;
signed main() {
	fprintf(stderr,"Memory: %.4lf Mib\n",abs(&_End-&_Start)/1048576.0);
	read(n,m);
	for(int i=1;i<=n;i++) {
		char s[N];scanf("%s",s+1);
		for(int j=1;j<=m;j++) {
			if(s[j]!='.') {
				if(n<m) cst[j][s[j]-'0']|=1<<(i-1);
				else cst[i][s[j]-'0']|=1<<(j-1);
			}
		}
	}
	if(n<m) swap(n,m);
	for(int i=0;i<(1<<m);i++) {
		if((i&(i<<1))||(i&(i>>1))) continue;
		stu[++cnt]=i;
	}
	f[0][0]=1;
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=cnt;j++) {
			int s=stu[j];
			if(((s&cst[i][1])!=cst[i][1])||(s&cst[i][0])) continue;
			for(int k=1;k<=cnt;k++) {
				int t=stu[k];
				if(s&t) continue;
				f[i][s]=(f[i][s]+f[i-1][t])%mod;
			}
		}
	}
	for(int i=0;i<(1<<m);i++) ans=(ans+f[n][i])%mod;
//	for(int i=1;i<=n;i++) printf("%d %d\n",cst[i][0],cst[i][1]);
//	for(int i=1;i<=n;i++) {
//		for(int j=0;j<(1<<m);j++) printf("%d ",f[i][j]);
//		puts("");
//	}
	printf("%lld",ans);
	return 0;
}

2023/11/17 20:16
加载中...