题解 ABC334G【Christmas Color Grid 2】

先求出初始时绿连通块数量。

将一个绿色格子染成红色，会改变绿连通块数量，当且仅当这个绿色格子是孤点或割点。如果是孤点，会使得绿连通块数量减少一；如果是割点，会使得绿连通块数量增加它所在的点双数量减一。根据上述规则可以求出每个绿色格子染红后的绿连通块数量，求平均值即可。

时间复杂度 \(O(nm)\)。

// Problem: G - Christmas Color Grid 2
// Contest: AtCoder - UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
// URL: https://atcoder.jp/contests/abc334/tasks/abc334_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

typedef Modint<998244353> mint;

const int K = 1e3 + 5, N = 1e6 + 5;
const int nxt[4][2] = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}};

int n, m, k, vis[K][K];
string s[K];
int dfn[N], low[N], cut[N], cnt[N], tms;
vector<vector<int>> bcc;
stack<int> stk;
mint ans, tot;

inline int getId(int x, int y) {
    return (x - 1) * m + y;
}

void dfs(int x, int y, int u) {
    vis[x][y] = u;
    rep(d, 0, 3) {
        int nx = x + nxt[d][0], ny = y + nxt[d][1];
        if(s[nx][ny] == '#' && !vis[nx][ny]) dfs(nx, ny, u);
    }
}

struct Edge {
	int v, nxt;
	Edge(int a = 0, int b = 0) : v(a), nxt(b) {}
}e[N * 8];
int h[N], ne = 1;
inline void add(int u, int v) {
	e[++ne] = Edge(v, h[u]); h[u] = ne;
	e[++ne] = Edge(u, h[v]); h[v] = ne;
}

void tarjan(int u, int fa) {
	dfn[u] = low[u] = ++tms;
	stk.push(u);
	int deg = 0;
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].v;
		if(v == fa) continue;
		if(!dfn[v]) {
			++deg;
			tarjan(v, u);
			chkmin(low[u], low[v]);
			if(low[v] >= dfn[u]) {
			    cut[u] = 1;
				bcc.push_back({}); 
				while(true) {
					int w = stk.top(); stk.pop();
					bcc.back().push_back(w);
					++cnt[w];
					if(w == v) break;
				}
				bcc.back().push_back(u);
				++cnt[u];
			}
		}
		else chkmin(low[u], dfn[v]);
	}
	if(!fa && deg == 1) cut[u] = 0;
	if(!fa && !deg) {
	    bcc.push_back({u});
	    cut[u] = -1;
	}
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    s[0] = s[n + 1] = string(m + 2, ' ');
    rep(i, 1, n) {
        cin >> s[i];
        s[i] = ' ' + s[i] + ' ';
    }
    rep(i, 1, n) rep(j, 1, m) if(s[i][j] == '#' && !vis[i][j]) dfs(i, j, ++k);
    rep(i, 1, n) {
        rep(j, 1, m) {
            if(s[i][j] == '#') {
                rep(d, 0, 3) {
                    int nx = i + nxt[d][0], ny = j + nxt[d][1];
                    if(s[nx][ny] == '#') add(getId(i, j), getId(nx, ny));
                }
            }
        }
    }
    rep(i, 1, n) {
        rep(j, 1, m) {
            if(s[i][j] == '#' && !dfn[getId(i, j)]) {
                tarjan(getId(i, j), 0);
            }
        }
    }
    rep(i, 1, n) {
        rep(j, 1, m) {
            if(s[i][j] == '#') {
                ++tot;
                ans += k;
                if(cut[getId(i, j)] == 1) ans += cnt[getId(i, j)] - 1;
                else if(cut[getId(i, j)] == -1) --ans;
            }
        }
    }
    cout << ans / tot << endl;
    return 0;
}