ABC 赛场上调不出来的E求调
  • 板块学术版
  • 楼主A2_Zenith
  • 当前回复9
  • 已保存回复9
  • 发布时间2023/12/23 21:50
  • 上次更新2023/12/24 08:57:57
查看原帖
ABC 赛场上调不出来的E求调
906856
A2_Zenith楼主2023/12/23 21:50

不会C不会E,输麻了。

#include<bits/stdc++.h>
#define int long long
#define ctz __builtin_ctz 
using namespace std;
const int maxn=1e3+7;
const int mod=998244353;
char mp[maxn][maxn];
int fa[maxn*maxn+7];
int hs(int x,int y){
	return x*maxn+y;
}
int findfa(int h){
	return fa[h]==h?h:fa[h]=findfa(fa[h]);
}
void mg(int h1,int h2){
	int f1=findfa(h1),f2=findfa(h2);
	fa[f1]=f2;
}
int h,w;
int cntr;
int cntcc;
int p;
const int dx[5]={0,-1,0,1,0};
const int dy[5]={0,0,1,0,-1};
inline int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
inline int inv(int x){return qpow(x,mod-2);}
signed main(){
	cin>>h>>w;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			fa[hs(i,j)]=hs(i,j);
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			char t;
			cin>>t;
			mp[i][j]=t;
			if(t=='.')cntr++;
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(mp[i][j]=='.')continue;
			for(int k=1;k<=4;k++){
				int di=i+dx[k];
				int dj=j+dy[k];
				if(mp[di][dj]=='#')mg(hs(di,dj),hs(i,j));
			}
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(mp[i][j]=='.')continue;
			if(findfa(hs(i,j))==hs(i,j))cntcc++;
		}
	}
//	cout<<cntcc<<endl;
	vector<int> nw;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			while(!nw.empty())nw.pop_back();
			if(mp[i][j]=='#')continue;
			int ansij=cntcc+1;
			for(int k=1;k<=4;k++){
				int di=i+dx[k];
				int dj=j+dy[k];
				if(mp[di][dj]!='#')continue;
				int h=findfa(hs(di,dj));
				bool f=false;
				for(int l=0;l<nw.size();l++){
					if(nw[l]==h){
						f=true;
						break;
					}
				}
				if(!f){
					nw.push_back(h);
					ansij--;
				}
			}
//			cout<<ansij<<" "<<i<<" "<<j<<endl;
			p+=ansij;
		}
	}
//	cout<<p<<" "<<cntr<<endl;
	cout<<p*inv(cntr)%mod;
}
2023/12/23 21:50
加载中...