提出 #48778652

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ThxDem=b;i<ThxDem;++i)
#define pb push_back
#define ALL(s) s.begin(),s.end()
#define FIN ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define SZ(s) int(s.size())
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;

const int MAXN=1e6+10, MOD=998244353;

int add(int a, int b){a+=b;if(a>=MOD)a-=MOD;return a;}
int sub(int a, int b){a-=b;if(a<0)a+=MOD;return a;}
int mul(ll a, ll b){return a*b%MOD;}
int fpow(int a, ll b){
	int r=1;
	while(b){if(b&1)r=mul(r,a); b>>=1; a=mul(a,a);}
	return r;
}

vector<int> g[MAXN];
struct edge {int u,v,comp;bool bridge;};
vector<edge> e;
void add_edge(int u, int v){
	g[u].pb(e.size());g[v].pb(e.size());
	e.pb((edge){u,v,-1,false});
}
int D[MAXN],B[MAXN],T;
int nbc;  // number of biconnected components
int art[MAXN];  // articulation point iff !=0
stack<int> st;  // only for biconnected
void dfs(int u,int pe){
	B[u]=D[u]=T++;
	for(int ne:g[u])if(ne!=pe){
		int v=e[ne].u^e[ne].v^u;
		if(D[v]<0){
			st.push(ne);dfs(v,ne);
			if(B[v]>D[u])e[ne].bridge = true; // bridge
			if(B[v]>=D[u]){
				art[u]++; // articulation
				int last; // start biconnected
				do {
					last=st.top();st.pop();
					e[last].comp=nbc;
				} while(last!=ne);
				nbc++;    // end biconnected
			}
			B[u]=min(B[u],B[v]);
		}
		else if(D[v]<D[u])st.push(ne),B[u]=min(B[u],D[v]);
	}
}
void doit(int n){
	memset(D,-1,sizeof(D));memset(art,0,sizeof(art));
	nbc=T=0;
	fore(i,0,n)if(D[i]<0)dfs(i,-1),art[i]--;
}

vector<ii> mov={{1,0},{0,1},{-1,0},{0,-1}};
string s[MAXN];

int p[MAXN];

int find(int x){return p[x]=p[x]==x?x:find(p[x]);}
void join(int x, int y){p[find(x)]=find(y);}

int main(){FIN;
	int n,m; cin>>n>>m;
	
	fore(i,0,n) cin>>s[i];
	
	fore(i,0,n*m) p[i]=i;
	
	fore(i,0,n) fore(j,0,m) if(s[i][j]=='#'){
		for(auto dir:mov){
			int x=i+dir.fst, y=j+dir.snd;
			if(x<0||y<0||x==n||y==m||s[x][y]!='#') continue;
			ii me={i,j};
			ii he={x,y};
			if(me<he) add_edge(m*i+j,m*x+y);
			join(m*i+j, m*x+y);
		}
	}
	
	doit(n*m);
	
	int all=0;
	fore(i,0,n) fore(j,0,m) if(s[i][j]=='#'&&find(m*i+j)==m*i+j) all++;
	
	int tot=0, sum=0;
	
	fore(i,0,n) fore(j,0,m) if(s[i][j]=='.'){
	
		set<int> ss;
		
		for(auto dir:mov){
			int x=i+dir.fst, y=j+dir.snd;
			if(x<0||y<0||x==n||y==m||s[x][y]!='#') continue;
			ss.insert(find(m*x+y));
		}
		
		tot++;
		int now=all+1;
		
		if(SZ(ss)){
			now=all-(SZ(ss)-1);
		}
		
		sum=add(sum, now);
	}
	
	int ans=mul(sum, fpow(tot,MOD-2));
	
	cout<<ans<<"\n";
}

提出情報

ジャッジ結果