思路概述

我们随机选择一个格子并染红。若选到原本红色的格子，连通块数保持不变；若选到白色格子，则会产生变化。关键是弄清白格染红后连通块数的改变量。

对于一个白格：

• 若它四周没有红色格子，则它会单独形成一个新的红块，连通块数增加 1；
• 若它四周接触到的红格属于 $k$ 个不同的红色连通块，则它会把这些块合并成 1 个，因此连通块总数减少 $k-1$。

总结：改变量 = 1 - 邻接的不同红块数。

于是我们可以把期望结果写成：

• 初始红色连通块数 $C_0$，
• 棋盘总格子数 $N = n \times m$，
• 白格数量 $W$，
• 所有白格邻接的不同红块总和 $\sum k$。

期望值公式为：

E = (N*C0 + W - Σk) / N

最终要输出 E 在模 1e9+7 下的结果。分母用乘法逆元处理。

算法步骤

1. 用并查集或 BFS 给所有红格编号，统计红块总数 $C_0$。
2. 遍历所有白格，查看上下左右 4 个邻居，统计不同红块编号个数 $k$，累加到 $\sum k$。
3. 计算分子 S = N*C0 + W - Σk。
4. 输出 (S * N⁻¹) mod 1e9+7。

复杂度

• 标记红块 + 遍历统计：O(nm)。
• 空间：O(nm)。

代码

Python

import sys
from collections import deque

MOD = 10**9 + 7

def main():
    input_data = sys.stdin.buffer.read().split()
    n, m = map(int, input_data[:2])
    g = [input_data[2+i].decode() for i in range(n)]
    N = n*m

    # BFS 给红格染色
    comp = [[-1]*m for _ in range(n)]
    cid = 0
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    for i in range(n):
        for j in range(m):
            if g[i][j]=='R' and comp[i][j]==-1:
                comp[i][j] = cid
                q = deque([(i,j)])
                while q:
                    x,y = q.popleft()
                    for dx,dy in dirs:
                        nx,ny = x+dx,y+dy
                        if 0<=nx<n and 0<=ny<m and g[nx][ny]=='R' and comp[nx][ny]==-1:
                            comp[nx][ny] = cid
                            q.append((nx,ny))
                cid += 1
    C0 = cid

    # 统计白格情况
    W, sumk = 0,0
    for i in range(n):
        for j in range(m):
            if g[i][j]=='W':
                W += 1
                neigh = set()
                for dx,dy in dirs:
                    nx,ny = i+dx,j+dy
                    if 0<=nx<n and 0<=ny<m and g[nx][ny]=='R':
                        neigh.add(comp[nx][ny])
                sumk += len(neigh)

    S = (C0*N + W - sumk) % MOD
    invN = pow(N, MOD-2, MOD)
    print(S * invN % MOD)

if __name__ == "__main__":
    main()

C++

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007LL;

long long modpow(long long a, long long e){
    long long r = 1 % MOD; a %= MOD;
    while(e){
        if(e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; 
    cin >> n >> m ;
    vector<string> g(n);
    for(int i=0;i<n;i++) cin >> g[i];
    long long N = 1LL * n * m;

    // comp 为每个格子的红块编号；-1 表示未染色或白格
    vector<int> comp(n*m, -1);
    auto id = [&](int x,int y){ return x*m + y; };
    const int dx[4] = {1,-1,0,0};
    const int dy[4] = {0,0,1,-1};

    // BFS 给红格编号
    int cid = 0;
    queue<pair<int,int>> q;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='R' && comp[id(i,j)]==-1){
                comp[id(i,j)] = cid;
                q.push({i,j});
                while(!q.empty()){
                    auto [x,y] = q.front(); q.pop();
                    for(int k=0;k<4;k++){
                        int nx = x + dx[k], ny = y + dy[k];
                        if(0<=nx && nx<n && 0<=ny && ny<m && g[nx][ny]=='R'){
                            int v = id(nx,ny);
                            if(comp[v]==-1){
                                comp[v] = cid;
                                q.push({nx,ny});
                            }
                        }
                    }
                }
                ++cid;
            }
        }
    }
    long long C0 = cid;

    // 统计白格总数 W 与 sumk（每个白格相邻不同红块数之和）
    long long W = 0, sumk = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(g[i][j]=='W'){
                ++W;
                int uniq[4], cnt=0;
                auto push = [&](int t){
                    for(int u=0; u<cnt; ++u) if(uniq[u]==t) return;
                    uniq[cnt++] = t;
                };
                if(i>0   && g[i-1][j]=='R') push(comp[id(i-1,j)]);
                if(i+1<n && g[i+1][j]=='R') push(comp[id(i+1,j)]);
                if(j>0   && g[i][j-1]=='R') push(comp[id(i,j-1)]);
                if(j+1<m && g[i][j+1]=='R') push(comp[id(i,j+1)]);
                sumk += cnt;
            }
        }
    }

    long long S = ( (C0 % MOD) * (N % MOD) + (W - sumk) ) % MOD;
    if(S < 0) S += MOD;
    long long invN = modpow(N % MOD, MOD - 2);
    cout << (S * invN) % MOD << "\n";
    return 0;
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static final long MOD = 1_000_000_007L;

    static long modpow(long a, long e){
        long r = 1 % MOD; a %= MOD;
        while(e>0){
            if((e&1)==1) r = (r * a) % MOD;
            a = (a * a) % MOD;
            e >>= 1;
        }
        return r;
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        char[][] g = new char[n][];
        for(int i=0;i<n;i++) g[i] = br.readLine().trim().toCharArray();
        long N = 1L * n * m;

        // comp 为每个格子的红块编号；-1 表示未染色或白格
        int[] comp = new int[n*m];
        Arrays.fill(comp, -1);
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        int cid = 0;

        // BFS 给红格编号
        ArrayDeque<int[]> q = new ArrayDeque<>();
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(g[i][j]=='R' && comp[i*m + j]==-1){
                    comp[i*m + j] = cid;
                    q.add(new int[]{i,j});
                    while(!q.isEmpty()){
                        int[] cur = q.poll();
                        int x = cur[0], y = cur[1];
                        for(int[] d: dirs){
                            int nx = x + d[0], ny = y + d[1];
                            if(0<=nx && nx<n && 0<=ny && ny<m && g[nx][ny]=='R'){
                                int v = nx*m + ny;
                                if(comp[v]==-1){
                                    comp[v] = cid;
                                    q.add(new int[]{nx,ny});
                                }
                            }
                        }
                    }
                    cid++;
                }
            }
        }
        long C0 = cid;

        // 统计白格 W 与 sumk
        long W = 0, sumk = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(g[i][j]=='W'){
                    W++;
                    int[] uniq = new int[4];
                    int cnt = 0;

                    // 将相邻红块编号去重收集
                    if(i>0 && g[i-1][j]=='R'){
                        int r = comp[(i-1)*m + j];
                        boolean ok = true; for(int t=0;t<cnt;t++) if(uniq[t]==r){ ok=false; break; }
                        if(ok) uniq[cnt++] = r;
                    }
                    if(i+1<n && g[i+1][j]=='R'){
                        int r = comp[(i+1)*m + j];
                        boolean ok = true; for(int t=0;t<cnt;t++) if(uniq[t]==r){ ok=false; break; }
                        if(ok) uniq[cnt++] = r;
                    }
                    if(j>0 && g[i][j-1]=='R'){
                        int r = comp[i*m + (j-1)];
                        boolean ok = true; for(int t=0;t<cnt;t++) if(uniq[t]==r){ ok=false; break; }
                        if(ok) uniq[cnt++] = r;
                    }
                    if(j+1<m && g[i][j+1]=='R'){
                        int r = comp[i*m + (j+1)];
                        boolean ok = true; for(int t=0;t<cnt;t++) if(uniq[t]==r){ ok=false; break; }
                        if(ok) uniq[cnt++] = r;
                    }
                    sumk += cnt;
                }
            }
        }

        long S = ((C0 % MOD) * (N % MOD) + (W - sumk)) % MOD;
        if(S < 0) S += MOD;
        long invN = modpow(N % MOD, MOD - 2);
        long ans = (S * invN) % MOD;
        System.out.println(ans);
    }
}

题目内容

小红有一个 $n$ 行 $m$ 列的矩阵，其中有一些格子已经被染成了红色。

小红将进行一次操作：随机选择一个格子，将其染成红色(如果该格子本身为红色，那么不进行任何改变)。

小红想知道，进行了一次操作以后，红色连通块数量的期望是多少?

我们定义两个红色格子连通，当且仅当它们共用同一条边。

可以证明，最终的期望 $E$ 是个有理数。你需要输出 $E$ 对 $10^9+7$ 取模的值。

分数取模的定义: $\frac{a}{b}$%$p=x$ (%代表取模) 等价于在 $[0,p-1]$ 找到一个 $x$ 满足 $x*b$%$p=a$ 。例如,$\frac{1}{2}$ 对 $5$ 取模的答案是 $3$ 。

输入描述

第一行输入两个正整数 $n$ 和 $m$ ，用空格隔开。

接下来的 $n$ 行，每行输入一个长度为 $m$ 的、仅由"$R$'和"$W$"组成的字符串。"$R$"代表该格子染成红色，"$W$"代表该格子为初始的白色。

$1 ≤n,m ≤ 10^3$

输出描述

一个整数，代表最终的期望对 $10^9+7$ 取模的值。

样例1

输入

3 3
WRW
RWR
WRW

输出

222222227

说明

最终红色连通块数量的期望是 $29/9$ ，再对 $10^9+7$ 取模，结果为 $222222227$ 。