1 条题解

  • 0
    @ 2026-2-2 10:43:00
    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int N=1e6+10,M=1e3+10,P=998244353;
    vector<int>G[N];int cut[N],root,siz[N];
    int tsp,cnt,dfn[N],low[N];int n,m;
    stack<int>stk;bool instk[N];
    void tarjan(int x,int f)
    {
    	dfn[x]=low[x]=++tsp;
    	if(G[x].size()==0){return ;}
    	stk.push(x);instk[x]=1;
    	int child=0;
    	for(int y:G[x])if(y!=f)
    	{
    		if(dfn[y]==0)
    		{
    			tarjan(y,x);
    			low[x]=min(low[x],low[y]);
    			if(dfn[x]<=low[y])
    			{
    				child++;
    				if(x!=root || child>1)cut[x]=1;
    				for(int z=-1;z!=y;)
    				{
    					z=stk.top();stk.pop();instk[z]=0;
    					siz[z]++;
    				};
    				siz[x]++; 
    			}
    		}
    		else if(instk[y]==1)low[x]=min(low[x],dfn[y]);
    	}
    }
    int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};map<pair<int,int>,int>mp;
    #define nx x+dx[i]
    #define ny y+dy[i]
    int v[M][M],a[M][M];
    int qpow(int a,int b){int res=1;for(;b;b>>=1,a=a*a%P)if(b&1)res=res*a%P;return res;}
    int getid(int x,int y){return (x-1)*m+y;}
    void bfs(int xx,int yy)
    {
    	deque<pair<int,int>>q;q.push_back({xx,yy});
    	a[xx][yy]=cnt;
    	while(!q.empty())
    	{
    		int x=q.front().first,y=q.front().second;q.pop_front();
    		for(int i=0;i<4;i++)if(nx>0&&nx<=n&&ny>0&&ny<=m&&v[nx][ny]&&!a[nx][ny])
    			q.push_back({nx,ny}),a[nx][ny]=cnt;
    	}
    }
    signed main()
    {
    	cin>>n>>m;int ttsp=0;
    	for(int i=1;i<=n;i++)
    	{
    		string st;cin>>st;
    		for(int j=0;j<m;j++)v[i][j+1]=st[j]=='#';
    	}
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)
    		if(v[i][j]&&!a[i][j])
    			cnt++,bfs(i,j);
    	for(int k=1;k<=n;k++)for(int j=1;j<=m;j++)if(v[k][j])
    	{
    		int x=k,y=j;
    		for(int i=0;i<3;i++)if(v[nx][ny])
    		{
    			int xx=getid(k,j),yy=getid(nx,ny);
    			if(mp[{xx,yy}])continue;
    			G[xx].push_back(yy);G[yy].push_back(xx);
    			mp[{xx,yy}]=mp[{yy,xx}]=1;
    		}
    	}
    	for(int i=1;i<=n*m;i++)if(!dfn[i])root=i,tarjan(i,0);
    	int sum=0,ans=0;
    	for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(v[i][j])
    	{
    		int id=getid(i,j);
    		ans+=cnt+siz[id]-1;sum++;
    	}
    	int d=__gcd(sum,ans);sum/=d,ans/=d;ans%=P;
    	int anss=ans*qpow(sum,P-2)%P;
    	cout<<anss;
    	return 0;
    }
    • 1

    信息

    ID
    8275
    时间
    2000ms
    内存
    1024MiB
    难度
    9
    标签
    递交数
    9
    已通过
    6
    上传者