1 条题解
-
0
#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
- 上传者