TLE on #6 求助
查看原帖
TLE on #6 求助
671911
XHWxhw123楼主2023/12/25 13:44
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N=1e3+5,mod=998244353;

int qpow(int x,int n)
{
	int res=1;
	for(;n;n>>=1)
		(res*=(n&1)?x:1)%=mod,(x*=x)%=mod;
	return res;
}

int inv(int x){return qpow(x,mod-2);}

int n,m;
char a[N][N];
int c[N][N],cnt=0;
int sum=0,ans=0,red=0;
int mx[5]={0,0,0,-1,1};
int my[5]={0,-1,1,0,0};

bool check(int x,int y){return (x>=1)&&(x<=n)&&(y>=1)&&(y<=m);}

void bfs(int stx,int sty)
{
	queue<pair<int,int> > q;
	q.push(make_pair(stx,sty));
	++cnt;
	
	while(q.size())
	{
		auto [ux,uy]=q.front();
		c[ux][uy]=cnt;
		q.pop();
		
		for(int i=1;i<=4;i++)
		{
			int vx=ux+mx[i],vy=uy+my[i];
			if(check(vx,vy)&&a[stx][sty]==a[vx][vy]&&!c[vx][vy])
				q.push(make_pair(vx,vy));
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin>>a[i][j];
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(a[i][j]=='#'&&!c[i][j])
				bfs(i,j),++sum;
	
//	for(int i=1;i<=n;i++,cout<<'\n')
//		for(int j=1;j<=m;j++)
//			cout<<c[i][j]<<' ';
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]=='.')
			{
				set<int> s;
				int l=1;
				for(int k=1;k<=4;k++)
				{
					int x=i+mx[k],y=j+my[k];
//					cout<<x<<'&'<<y<<' ';
					if(check(x,y)&&a[x][y]=='#')
						s.insert(c[x][y]);
				}
//				cout<<sum<<' '<<s.size()<<'\n';
				(ans+=sum+1-s.size())%=mod;
				red++;
			}
		}
	}
	
//	cout<<ans<<' '<<red<<'\n';
	
//	cout<<inv(red)<<'\n';
	
	(ans*=inv(red))%=mod;
	
	cout<<ans<<'\n';
	
	return 0;
}

rt,AT测评记录。

2023/12/25 13:44
加载中...