1 条题解

  • 0
    @ 2025-8-24 22:39:13

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar 一念之间、、
    Have already AFOed.

    搬运于2025-08-24 22:39:13，当前版本为作者最后更新于2022-03-31 07:40:31，作者可能在搬运后再次修改，您可在原文处查看最新版

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

    以下是正文

    题意简述

    说：n≤500n \le 500，m≤500m\le 500，保证周围无雷的格子形成 d≤37d\le 37 个连通块，

    n×mn\times m 的网格，每个格子是 * 或者 . 。

    问：有多少种可能的最终状态，状态定义为扫雷点方块可达的状态，

    具体的，每个无雷格子有开/不开状态，雷格子有爆/不爆状态，雷如果爆一个，则所有都爆，若点击一个空格子且周围 8 个不存在雷，那么递归打开周围 8 个。

    solution

    注意，这篇题解没有严格的复杂度证明，是靠搜索得到的正确结果。

    首先一个显然的想法就是说，一个格子与相关的空地连通块放在一起考虑，即空地连通块打开，则相关的都会打开，只要相关有一个没打开，空地就不能打开。

    但是直接写 wa 了，考虑为什么，样例给了个很好的情况，就是说，一个格子可能与多个空地连通块相关，观察到与至多两个空地连通块相关，那么想到建边。

    然后点数量是 37 ，由于连通块类似平面表示，联想到平面图。

    本质是对于每个点填入 0/1 ，填 0/1 有不同方案，

    然后边填入 0/1 也分别有不同方案，要求点填 1 则周围边一定填 1，

    问：∑填数方案∏点/边方案\sum_{\text {填数方案}} \prod _{\text{点/边方案}}

    考虑决定每个点，发现决定了一个点可以删去周围一圈的边，对于两个独立的连通块实际上可以独立处理，由于是平面图，搜索不好卡。

    代码

    #include<bits/stdc++.h>
#define ll long long
#define LL __int128
#define dd double
using namespace std;
char gc(){static char buf[1<<16],*s,*t;if(s==t){t=(s=buf)+fread(buf,1,1<<16,stdin);if(s==t)return EOF;}return *s++;}
//#define getchar gc
ll read()
{
	char c;
	ll w=1;
	while((c=getchar())>'9'||c<'0')if(c=='-')w=-1;
	ll ans=c-'0';
	while((c=getchar())>='0'&&c<='9')ans=(ans<<1)+(ans<<3)+c-'0';
	return ans*w;
}
void pc(char c,int op)
{
	static char buf[1<<16],*s=buf,*t=buf+(1<<16);
	(op||((*s++=c)&&s==t))&&(fwrite(buf,1,s-buf,stdout),s=buf);
}
void wt(int x)
{
	if(x>9)wt(x/10);
	pc('0'+x%10,0);
}
void wts(int x,char op)
{
	if(x<0)pc('-',0),x=-x;
	wt(x);pc(op,0);
}
namespace ppprrr{const int xx=2,mod=2;ll ksm(ll a,ll b){ll ans=1;while(b){if(b&1)ans*=a,ans%=mod;a*=a,a%=mod,b>>=1;}return ans;}

ll jiec[xx],ni[xx];
ll C(ll n,ll m){return jiec[n]*ni[m]%mod*ni[n-m]%mod;}
void pre()
{
	jiec[0]=1;
	for(int i=1;i<xx;i++)jiec[i]=jiec[i-1]*i%mod;
	ni[xx-1]=ksm(jiec[xx-1],mod-2);
	for(int i=xx-2;i>=0;i--)ni[i]=ni[i+1]*(i+1)%mod;
}
	
int prim[xx],mn[xx],Cnt;
void pre(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(!mn[i])mn[i]=i,prim[++Cnt]=i;
		for(int j=1;j<=Cnt;j++)
		{
			if(prim[j]*i>n)break;
			mn[i*prim[j]]=prim[j];
			if(i%prim[j]==0)break;
		}
	}
}


int lb(int x){return x&-x;}
ll sum[xx];
void Add(int x,int y){for(;x<xx;x+=lb(x))sum[x]+=y;}
ll ask(int x){ll ans=0;for(;x;x-=lb(x))ans+=sum[x];return ans;}

struct nod{int next,to;}e[xx<<1];
int cnt,h[xx];
void add(int x,int y){cnt++,e[cnt]={h[x],y},h[x]=cnt;}


}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
const int xx=1e6+5,mod=998244353;
void ad(int &a,int b){(a+=b)>=mod?a-=mod:0;}
ll ksm(ll a,ll b)
{
	ll ans=1;
	while(b)
	{
		if(b&1)ans*=a,ans%=mod;
		a*=a,a%=mod,b>>=1;
	}
	return ans;
}
struct pr{int x,y;bool operator<(const pr&w)const{return x==w.x?y<w.y:x<w.x;};};
int n,m,k,q,a[xx],b[xx];
char s[505][505];
char is[505][505];
char Is[505][505];
int dx[]={1,1,1,-1,-1,-1,0,0},dy[]={1,0,-1,1,0,-1,1,-1};
int bel[505][505],tt,sz;
vector<pr>v;
set<int> A[505][505];
void dfs(int x,int y)
{
	if(x<1||y<1||x>n||y>m)return;
//	cerr<<x<<" "<<y<<"%%\n";
	if(is[x][y])bel[x][y]=tt,A[x][y].insert(tt);
//	,cerr<<x<<" "<<y<<"%%\n";
	sz+=is[x][y];
	int cr=is[x][y];
	is[x][y]=-1;
	if(!cr)
	{
		for(int k=0;k<8;k++)
			if(is[x+dx[k]][y+dy[k]]!=-1)dfs(x+dx[k],y+dy[k]);
			else if(bel[x+dx[k]][y+dy[k]]!=tt&&Is[x+dx[k]][y+dy[k]]==1)
			{
				v.push_back({min(tt,bel[x+dx[k]][y+dy[k]]),max(tt,bel[x+dx[k]][y+dy[k]])});
//				v.push_back({x+dx[k],y+dy[k]});
				A[x+dx[k]][y+dy[k]].insert(tt);
			}
	}
}
bool operator==(const pr&a,const pr&b)
{
	return !(a<b)&&!(b<a);
}
namespace sou
{
	#define ull unsigned ll
	const int xx=305;
	struct nod{int next,to,v;}e[xx<<1];
	int cnt,h[xx];
	int d[xx];
	void add(int x,int y,int z){/*cerr<<x<<" "<<y<<"%%\n"*/d[y]++;cnt++,e[cnt]={h[x],y,z},h[x]=cnt;}
	mt19937 G(218);
	int is[xx];
	void D(ull &S,int x,vector<int>&v)
	{
		S|=(1ull<<x),v.push_back(x);
		for(int i=h[x];i;i=e[i].next)if(!is[e[i].to]&&!(S>>e[i].to&1))D(S,e[i].to,v);
	}
	ll sum[xx];
	int ct=0;
	ull dfs(ull S)
	{
		++ct;
		ull tt=0;
		int x=__builtin_ctzll(S&-S);
//		cerr<<x<<" "<<sum[x]<<"$%$\n";
		if(__builtin_popcountll(S)==1)
			return 1+ksm(2,sum[x]);
		
		vector<int>lin;
		D(tt,x,lin);
		if(tt!=S)return dfs(tt)*dfs(tt^S)%mod;
		
		int mx=0;
		for(auto it:lin)if(d[it]>mx)mx=d[it],x=it;
		
		if(d[x]<2)shuffle(lin.begin(),lin.end(),G),x=*lin.begin();
		
		ull ans=0;
		//填 1  
		
		is[x]=1;
		for(int i=h[x];i;i=e[i].next)
			if(!is[e[i].to])d[e[i].to]--;
		ans+=dfs(S^(1ull<<x));
		is[x]=0;
		for(int i=h[x];i;i=e[i].next)
			if(!is[e[i].to])d[e[i].to]++;
			
		//填 0  
		is[x]=1;
		for(int i=h[x];i;i=e[i].next)
			if(!is[e[i].to])d[e[i].to]--,sum[e[i].to]+=e[i].v;
			
		ans+=dfs(S^(1ull<<x))*ksm(2,sum[x])%mod;
		
		is[x]=0;
		for(int i=h[x];i;i=e[i].next)
			if(!is[e[i].to])d[e[i].to]++,sum[e[i].to]-=e[i].v;
//		cerr<<ans<<"qqweqe\n";
		return ans;
	}
	map<pair<int,int>,int>mp;
	void solve(int ct2)
	{
//		for(int i=1;i<=n;i++)
//			for(int j=1;j<=m;j++)
//			{
//				assert(A[i][j].size()<=2);
//				if(A[i][j].size())cerr<<A[i][j].size()<<"$$\n";
//			}
//		cerr<<n<<" "<<m<<"$$\n";
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=m;j++)
			{
				assert(A[i][j].size()<=2);
//				if(A[i][j].size())cerr<<A[i][j].size()<<"$$\n";
//				cerr<<i<<" "<<j<<"$%$%\n";
				if(A[i][j].size()==1)
				{
					sum[*A[i][j].begin() -1]++;
				}
				else if(A[i][j].size()==2)
				{
					mp[make_pair(*A[i][j].begin() -1,*--A[i][j].end() -1)]++;
				}
			}
		}
		for(auto it:mp)
		{
			add(it.first.first,it.first.second,it.second);
			add(it.first.second,it.first.first,it.second);
		}
		ll ans=dfs((1ull<<tt) -1);
//		for(int i=0;i<tt;i++)cout<<i<<" "<<d[i]<<" "<<sum[i]<<"##\n";
//		cerr<<ans<<"$$\n";
		cout<<ans*ksm(2,ct2)%mod<<"\n";
	}
}
int main(){
	read();
	n=read(),m=read();
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			char c;
			while((c=getchar())!='.'&&c!='*');
			s[i][j]=c;
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(s[i][j]=='*')
			{
				for(int k=0;k<8;k++)
					is[i+dx[k]][j+dy[k]]=Is[i+dx[k]][j+dy[k]]=1;
			}
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)if(s[i][j]=='*')is[i][j]=Is[i][j]=2;
	ll ans=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!is[i][j])
			{
				++tt,sz=0;
				dfs(i,j);
				ans*=(ksm(2,sz)+1);
				ans%=mod;
			}
		}
	}
	sort(v.begin(),v.end());
	ll mx=0,cE=0;
	pr lst={0,0};
	for(auto it:v)
	{
		if(it==lst)++cE;
		else cE=1;
		lst=it;
		mx=max(mx,cE);
	}
//	for(auto it:v)cout<<it
	int te=v.size();
	v.resize(unique(v.begin(),v.end(),[&](pr a,pr b){return !(a<b)&&!(b<a);})-v.begin());
	
//	assert(te==v.size());
//	if(v.size())assert(0);
//	assert(cE<=2);
//	assert(v.size()<=70);
	
		int ct2=0;//是否有雷 
		for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(is[i][j]==2)ct2=1;
		
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)
				if(is[i][j]==1)++ct2;
		
	if(!v.size())
	{
		cout<<ans*ksm(2,ct2)%mod<<"\n";
		exit(0);
	}
	else 
//	if(v.size()<=60)
	{
		
		sou::solve(ct2);
		exit(0);
	}
	
	pc('1',1);
	return 0;
}
    • 1

    「SWTR-8」扫雷计数

    信息

    ID
    5804
    时间
    3000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 21ms