数据真没问题吗???求助
查看原帖
数据真没问题吗???求助
234783
conprour楼主2021/11/2 22:49

RT,调了一年,后来把数组开到10过了

这份代码为什么会错 2 个大数据点???难道有 5*8 的数据吗??

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f,N = 1<<8,mod = 12345678;
char s[5][8];
int n,m,px[31],py[31];
ll dp[N][31],ans;
bool vis[10][10];
int dx[9] = {0,1,0,-1,0,1,1,-1,-1};
int dy[9] = {0,0,1,0,-1,1,-1,1,-1};
inline ll read()
{
	ll ret=0;char ch=' ',c=getchar();
	while(!(c>='0'&&c<='9')) ch=c,c=getchar();
	while(c>='0'&&c<='9') ret=(ret<<1)+(ret<<3)+c-'0',c=getchar();
	return ch=='-'?-ret:ret;
}
void print_map()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++) printf("%c",s[i][j]);
		printf("\n");
	}
}
int calc()//按照当前状态算出方案数 
{
	int cnt=0; 
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=m;j++)	
			if(s[i][j]=='X') px[++cnt]=i,py[cnt]=j;
	//print_map();
	memset(dp,0,sizeof(dp));
	dp[0][0]=1;
	for(int mask=0;mask<(1<<cnt);mask++)//枚举状态 
	{
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=cnt;i++)//标记当前状态下哪些点不能选
			if(!(mask&(1<<(i-1))))//每个最小点周围的点都不能选 
				for(int j=0;j<=8;j++)
					vis[px[i]+dx[j]][py[i]+dy[j]]=1;
		int tot=0;
		for(int i=1;i<=n;i++)	 
			for(int j=1;j<=m;j++) tot+=!vis[i][j];//计算有多少个能选的点 
		//printf("tot=%d\n",tot);
		for(int i=0;i<=tot;i++)	//刷表法,i从0开始 
			if(dp[mask][i])
			{
				(dp[mask][i+1]+=dp[mask][i]*(tot-i))%=mod;//当前数字不放在最小点 
				for(int j=0;j<cnt;j++)	
					if(!(mask&(1<<j))) 
						(dp[mask|(1<<j)][i+1]+=dp[mask][i])%=mod;//当前数字放在最小点 
			}
	}
	//printf("dp:%d\n",dp[(1<<cnt)-1][n*m]); 
	return dp[(1<<cnt)-1][n*m];
}
void dfs(int x,int y,int op)//op是容斥的正负号 
{//dfs从左上向右下一个个填新的状态 
	if(x==n+1) {ans=(ans+op*calc()%mod+mod)%mod;return;}
	if(y==m+1) {dfs(x+1,1,op);return;}
	dfs(x,y+1,op);//不改当前这个点的类型 
	bool flag=1;
	for(int i=0;i<=8;i++)
	{//判断是否能改当前这个点的类型 
		int tx=x+dx[i],ty=y+dy[i];
		if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&s[tx][ty]=='X') flag=0;
	}	
	if(flag) 
	{
		s[x][y]='X';
		dfs(x,y+1,-op);//改当前这个点的类型 
		s[x][y]='.';
	}
		
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
	for(int i=1;i<=n;i++)	
		for(int j=1;j<=m;j++)	
			if(s[i][j]=='X')
				for(int k=1;k<=8;k++)
				{
					int x=i+dx[k],y=j+dy[k];
					if(x>=1&&x<=n&&y>=1&&y<=m&&s[x][y]=='X')
						return puts("0"),0;//特判初始状态不合法 
				}
	dfs(1,1,1);
	printf("%lld\n",(ans+mod)%mod);
	return 0;
}
2021/11/2 22:49
加载中...