今晚ABC E求调
  • 板块学术版
  • 楼主Mr_Biantainne
  • 当前回复6
  • 已保存回复6
  • 发布时间2023/12/23 23:11
  • 上次更新2023/12/23 23:51:16
查看原帖
今晚ABC E求调
545601
Mr_Biantainne楼主2023/12/23 23:11

AC * 18
WA * 16

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll h, w, fa[1000005], num, ans, tot, cnt;
char c[1005][1005];
const ll mod = 998244353;
unordered_set <ll> s, v;
ll find(ll num)
{
	if (fa[num] == num) return fa[num];
	return fa[num] = find(fa[num]);
}
void Union(ll x, ll y)
{
	ll ta = find(x), tb = find(y);
	if (ta == tb) return;
	fa[tb] = ta;
}
ll qp(ll a, ll b)
{
	ll rec = 1;
	while (b)
	{
		if (b & 1)
		{
			rec *= a;
			rec %= mod;
		}
		a *= a;
		a %= mod;
		b >>= 1;
	}
	return rec;
}
inline ll t(ll x, ll y)
{
	return (x - 1) * w + y-1;
}
int main()
{
    cin >> h >> w;
    for (ll i = 1; i <= h * w; i++) fa[i] = i;
    for (ll i = 1; i <= h; i++) for (ll j = 1; j <= w; j++)
	{
		cin >> c[i][j];
		if (c[i][j] == '#')
		{
			if (c[i - 1][j] == '#') Union(t(i - 1, j), t(i, j));
			if (c[i][j - 1] == '#') Union(t(i, j - 1), t(i, j));
		}
	} 
	for (ll i = 1; i <= h; i++) for (ll j = 1; j <= w; j++) if (c[i][j] == '#') s.insert(find(t(i, j)));
	for (ll i = 1; i <= h; i++) for (ll j = 1; j <= w; j++) if (c[i][j] == '.')
	{
		v.clear();
		if (c[i - 1][j] == '#') v.insert(find(t(i - 1, j)));
		if (c[i + 1][j] == '#') v.insert(find(t(i + 1, j)));
		if (c[i][j - 1] == '#') v.insert(find(t(i, j - 1)));
		if (c[i][j + 1] == '#') v.insert(find(t(i, j + 1)));
		tot += s.size() - v.size() + 1;
		cnt++;
	}
	cout << tot * qp(cnt, mod - 2) % mod;
}
2023/12/23 23:11
加载中...