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;
}