Submission #50475571

---

Source Code Expand

// Source: https://usaco.guide/general/io

#include <algorithm>
#include <bits/stdc++.h>
#include <climits>
#include <iterator>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
#define inp(n, a) vector<ll> a;for(int i=0;i<n;i++){ll now;cin>>now;a.pb(now);}
#define all(a) a.begin(),a.end()
#define show(a) for(long long loppls=0;loppls<(long long)(a.size()-1);loppls++)cout<<a[loppls]<<' ';cout<<a[a.size()-1];

#ifdef reimufumo
#define owo(x) std::cerr << x;
#define ovo(a) for(long long loppls=0;loppls<(long long)(a.size()-1);loppls++)cerr<<a[loppls]<<' ';cerr<<a[a.size()-1];
#define ouo(a,x) for(long long loppls=0;loppls<x-1;loppls++)cerr<<a[loppls]<<'\t';cerr<<a[x-1];
#define dbg(x) std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << std::endl
#define dbgif(cond, x) ((cond) ? std::cerr << #x << " = " << (x) << " (L" << __LINE__ << ") " << __FILE__ << std::endl : std::cerr)
#else
#define owo(x) ((void)0)
#define ovo(a) ((void)0)
#define ouo(a,x) ((void)0)
#define dbg(x) ((void)0)
#define dbgif(cond, x) ((void)0)
#endif

long long binpow(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

long long inv(long long a, long long p){
    return binpow(a, p-2, p);
}

vector<ll> fact; // must be init if nCk needed

long long nCk(long long n, long long k, long long p){
    return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p;
}

ll sum2(ll a, ll l, ll n){return (n*(a+l))/2;}
ll ceil2(ll a, ll b){ll c=a/b;if(a%b!=0)c++;return c;}
ll floor2(ll x, ll m){ll r=(x%m+m)%m;return (x-r)/m;}

const ll INF=1e16,MAX=1020,MOD=998244353;

ll h,w;
vector<string> graph;
vector<vector<bool>> visited;
ll par[MAX],vsize[MAX];
vector<pll> dydx={{-1,0},{1,0},{0,-1},{0,1}};

void make_set(ll x){
    par[x]=x;
    vsize[x]=1;
}

ll find_set(ll x){
    if(par[x]==x)return par[x];
    return par[x]=find_set(par[x]);
}

void union_sets(ll a,ll b){
    a=find_set(a);
    b=find_set(b);
    if(a!=b){
        if(vsize[a]<vsize[b])swap(a,b);
        par[b]=a;
        vsize[a]+=vsize[b];
    }
}

bool legal(ll x,ll y){
    if(x<0)return 0;
    if(y<0)return 0;
    if(x>=h)return 0;
    if(y>=w)return 0;
    if(graph[x][y]=='.')return 0;
    return 1;
}

void dfs(ll x,ll y){
    if(visited[x][y])return;
    visited[x][y]=1;
    for(pll dd:dydx){
        ll nx=x+dd.fi,ny=y+dd.se;
        if(!legal(nx,ny))continue;
        union_sets(h*x+y,h*nx+ny);
        dfs(nx,ny);
    }
}

void solve() {
    cin>>h>>w;
    for(int i=0;i<h;i++){
        string snow;cin>>snow;
        graph.pb(snow);
    }

    for(int i=0;i<h;i++){
        visited.pb({});
        for(int j=0;j<w;j++){
            make_set(h*i+j);
            visited[i].pb(graph[i][j]=='.');
        }
    }

    ll totalcon=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(visited[i][j])continue;
            totalcon++;
            dfs(i,j);
        }
    }

    ll totaldots=0,probcon=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(graph[i][j]=='#')continue;
            totaldots++;
            set<ll> conn;
            for(pll dd:dydx){
                if(!legal(i+dd.fi,j+dd.se))continue;
                if(graph[i+dd.fi][j+dd.se]=='.')continue;
                conn.insert(find_set(h*(i+dd.fi)+j+dd.se));
            }
            probcon+=totalcon-(conn.size()-1);
        }
    }

    owo(probcon);owo(' ');owo(totaldots);
    cout<<(((probcon)%MOD)*binpow(totaldots,MOD-2,MOD))%MOD;
}

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

	solve();
}

Submission Info

Judge Result