CF398B Painting The Wall 题解

题意：

cxy 打算漆一堵墙。这个墙由 \(n^2\) 块瓷砖构成，它们构成 \(n \times n\) 的表。有些瓷砖是被涂上颜色的，还有些则没有。她想要将这堵墙漆得漂亮，她会按照以下四个步骤进行：

首先，cxy 会检查这堵墙，如果每行、每列均有涂上颜色的瓷砖，则停止刷墙，否则跳转到步骤 2。

cxy 从这 \(n^2\) 块瓷砖中均匀随机地选择一块瓷砖。

如果该瓷砖没有被涂色，则她将那块瓷砖涂色，否则，她什么都不用干。

然后，她休息 \(1\) 分钟，然后回到步骤 1。

cxy 觉得，她会花费太多时间在砌墙上。所以，她想知道，她按照上面的方法砌墙所需的时间的期望。你可以假设涂一块瓷砖不用花费任何时间。

输入格式：

第一行包含两个正整数 \(n, m~(1 \leq n \leq 2000,~0 \leq m \leq \min \{n^2, 20000\})\)，表示墙的大小和已经涂色的瓷砖的个数。

接下来的 \(m\) 行，每行包含两个正整数 \(r, c~(1 \leq r_i, c_i \leq n)\)，表示被涂色的瓷砖的位置。保证这些位置互异，且行列均为 \(1 \sim n\) 编号。

输出格式：

输出一行一个实数，表示砌墙的期望时间。答案被认为正确当且仅当相对或绝对误差不超过 \(10^{-4}\)。

考虑概率dp。设 \(f_{i,j}\) 表示还有 \(i\) 行 \(j\) 列没有涂颜色时剩下的时间的期望。

边界 \(f_{0,0} = 0\) ，最后的答案即为 \(f_{r,c}\) ，其中 \(r,c\) 分别表示初始未染色的行数和列数。

考虑 \(f_{i,j}\) 的转移。设 \(f_{i,j}\) 的这些未染色的行和列为 \(\mathcal{R}\) 和 \(\mathcal{C}\) ，则他们把整个网格图分成了四个子集

该行、该列均未上色的\(S_1 = \left\{ (x, y) \mid x \in \mathcal{R}, ~y \in \mathcal{C} \right\}\)
行上色列未上色的 \(S_2 = \left\{ (x, y) \mid x \notin \mathcal{R},~ y \in \mathcal{C} \right\}\)
列上色行未上色的 \(S_3 = \left\{ (x, y) \mid x \in \mathcal{R}, ~y \notin \mathcal{C} \right\}\)
行列均已上色的\(S_4 = \left\{ (x, y) \mid x \notin \mathcal{R}, ~y \notin \mathcal{C} \right\}\)

考虑下一步随机选的格子 \(k\) 。

首先有 \(\frac{\left|S_1\right|}{\left|S_1\right|+\left|S_2\right|+\left|S_3\right|+\left|S_4\right|}=\frac{i j}{n m}\) 的概率满足 \(k \in S_1\)

此时未上色的行数变为 \(i-1\) ，列数变为 \(j-1\) ，剩下的期望时间为 \(f_{i-1,j-1}\) 。
类似的，有 \(\frac{\left|S_2\right|}{\left|S_1\right|+\left|S_2\right|+\left|S_3\right|+\left|S_4\right|}=\frac{(n-i) j}{n m}\) 的概率满足 \(k \in S_2\)

此时未上色的行数变为 \(i\) ，列数变为 \(j-1\) ，剩下的期望时间为 \(f_{i,j-1}\) 。
......（其他两种情况类似）

则转移方程为 \[ f_{i, j}=1+\frac{1}{n m}\left[i j \times f_{i-1, j-1}+i(n-j) \times f_{i-1, j}+(n-i) j \times f_{i, j-1}+(n-i)(n-j) \times f_{i, j}\right] \] 然后解一下这个 \(f_{i,j}\) 的一元一次方程，就可以得到 \(f_{i,j}\) 的转移方程了。

时间复杂度 \(\mathcal{O}(n^2 + m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3+15))

double f[N][N];
int n,m,R,C,r[N],c[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(8);
    cin >> n >> m;
    for(int i=1,x,y; i<=m; i++)
    {
        cin >> x >> y;
        r[x] = c[y] = 1;
    }
    for(int i=1; i<=n; i++){ R += !r[i], C += !c[i]; }
    f[1][1] = 0; // 平移防止下标-1越界
    for(int i=0,x,y,z; i<=R; i++)
        for(int j=0; j<=C; j++)
        {
            if(!i && !j) continue;
            x = i * j; y = i * (n-j); z = (n-i) * j;
            f[i+1][j+1] = 
            (x*f[i][j] + y*f[i][j+1] + z*f[i+1][j] + (double)n*n) / (double)(x+y+z);
        }
    cout << f[R+1][C+1] << '\n';
    return 0;
}