仅AC 7求助

#include <bits/stdc++.h>

using namespace std;

#define ll long long
const ll mod = 998244353;
const int maxn = 1e3 + 5;
const int maxm = 1e6 + 5;
ll son[maxm];
int dfn[maxm], low[maxm], head[maxm], siz[maxm];
int t = 0, n, m, tot, col[maxn], c;
int sx[4] = {0, 0, 1, -1};
int sy[4] = {1, -1, 0, 0};
bool cut[maxm];
char e[maxn][maxn];
struct edge {
    int to, next;
} g[maxm << 1];

int id(int x, int y) {
	return (x - 1) * m + y;
} 
stack<int> s;
void add(int u, int v) {
    g[++tot].to = v;
    g[tot].next = head[u];
    head[u] = tot;
}

void tarjan(int u, int fa, int father) {
    dfn[u] = ++t;
    low[u] = t;
    col[u] = c;
    ++siz[c];
    s.push(u);
    int child = 0;
    for (int i = head[u]; i; i = g[i].next) {
        int v = g[i].to;
        if (v == father) {
        	continue;
		}
        if (!dfn[v]) {
            tarjan(v, fa, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && u != fa) {
                cut[u] = true;
            }
            if (low[v] >= dfn[u]) {
                int x;
                do {
                    x = s.top();
                    s.pop();
                    ++son[x];
                } while (!s.empty() && x != v);
                ++son[u]; 
            }
            if (u == fa) {
                ++child;
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (child >= 2 && u == fa) {
        cut[u] = true;
    }
}

ll binpow(ll x, ll y) {
	ll res = 1;
	while (y) {
		if (y & 1) {
			res = res * x % mod;
		}
		x = x * x % mod;
		y >>= 1;
	}
	return res;
}

void solve() {
	cin >> n >> m;
	ll cnt = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			cin >> e[i][j];
			if (e[i][j] == '#') {
				++cnt;
			}
		}
	}
	
    for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (e[i][j] == '#') {
				for (int k = 0; k < 4; ++k) {
					int si = i + sx[k];
					int sj = j + sy[k];
					if (si >= 1 && si <= n && sj >= 1 && sj <= m && e[si][sj] == '#') {
						int u = id(i, j);
						int v = id(si, sj);
						add(u, v);
					}
				}
			}
		}
	}
    for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (e[i][j] == '#') {
				int u = id(i, j);
				if (!dfn[u]) {
					++c;
					tarjan(u, u, 0);
				}
			}
		}
	}
    ll ans = 0;
    for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) {
			if (e[i][j] == '#') {
				int u = id(i, j);
				if (cut[u]) {
					ans += c + son[u] - 1;
				} else {
					if (siz[col[u]] == 1) {
						ans += c - 1;
					} else {
						ans += c;
					}
				}
				ans %= mod; 
			}
		}
	}
    cout << ans * binpow(cnt, mod - 2) % mod;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}