题解：CF398B Painting The Wall

· · 题解

都九年级了，还没法搞定马尔科夫链就有问题了，这就是中学生现状。

题意

在 n \times n(1 \le n \le 2000) 的网格图上，进行所有格子等概率打标记，问期望几次后每行每列都有标记格。

多一手

由于每个格子都是等概率的，我们不妨在里面掺一步：每次标记后将标记格子通过行交换和列交换移到左下角，这样不仅不会改变分析的正确性，还能将有标记格的行和列都移到一边，便于分析。

马尔科夫链和动态规划

由于题目是一道求期望的题，考虑使用马尔科夫链作为接下来的分析方式。

作为初中高等数学，马尔科夫链并不困难，其原理是：

  1. 设状态，及一种状态到一类结束状态的期望或概率；
  2. 根据下一步的状态情况得出求此状态的方程式；
  3. 若通过转方程得到的转移关系图为有向无环图则用动规，否则上高斯消元。

接下来，我们走一遍流程。

设 dp_{i,j} 表示已经有 i 行 j 列存在标记格，问标记到每行每列都被标记的期望次数。

接下来分析下一个标记的可能情况：

  1. 标记落入红区，对应行对应列都已有标记格，(i,j) \to (i,j)，概率为 \frac{ij}{n ^ 2}。
  2. 标记落入黄区，对应行已被标记，对应列在这次标记后有标记格，(i,j) \to (i,j + 1)，概率为 \frac{i(n - j)}{n ^ 2}。
  3. 标记落入蓝区，对应列已被标记，对应行在这次标记后有标记格，(i,j) \to (i + 1,j)，概率为 \frac{(n - i)j}{n ^ 2}。
  4. 标记落入绿区，对应列、对应行在这次标记后有标记格，(i,j) \to (i + 1,j + 1)，概率为 \frac{(n - i)(n - j)}{n ^ 2}。

得到转移方程：

dp_{i,j} = \begin{cases} 0 & i = n\land j = n \\ 1 + \frac{ij}{n ^ 2}dp_{i,j} + \frac{j(n - i)}{n ^ 2}dp_{i + 1,j} + \frac{i(n - j)}{n ^ 2}dp_{i,j + 1} + \frac{(n - i)(n - j)}{n ^ 2}dp_{i + 1,j + 1} & i \neq j \lor j \neq n \\ \end{cases}

对 (i,j) \neq (n,n) 的情况，有：

dp_{i,j} = 1 + \frac{ij}{n ^ 2}dp_{i,j} + \frac{j(n - i)}{n ^ 2}dp_{i + 1,j} + \frac{i(n - j)}{n ^ 2}dp_{i,j + 1} + \frac{(n - i)(n - j)}{n ^ 2}dp_{i + 1,j + 1}

即

(1 - \frac{ij}{n ^ 2})dp_{i,j} = 1 + \frac{j(n - i)}{n ^ 2}dp_{i + 1,j} + \frac{i(n - j)}{n ^ 2}dp_{i,j + 1} + \frac{(n - i)(n - j)}{n ^ 2}dp_{i + 1,j + 1}

成功处理掉自环，接下来由于转移关系为有向无环图，可以用 \operatorname{O}(n ^ 2) 动态规划解决。

最后对于部分格子已涂的情况，根据这些格子影响的行列数定位状态即可。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,cntx,cnty;
bool vis1[2009],vis2[2009];
double dp[2009][2009];
int main(){
    scanf("%d %d",&n,&m);
    for(int i = 1; i <= m; i ++){
        scanf("%d %d",&x,&y);
        if(!vis1[x])
            vis1[x] = true,cntx++;
        if(!vis2[y])
            vis2[y] = true,cnty++;
    }
    dp[n][n] = 0;
    for(int i = n; i >= cntx; i --){
        for(int j = n; j >= cnty; j --){
            if(i == n && j == n)
                continue;
            dp[i][j] = 1;
            if(i < n)
                dp[i][j] += dp[i + 1][j] * (n - i) * j / (n * n);
            if(j < n)
                dp[i][j] += dp[i][j + 1] * (n - j) * i / (n * n);
            if(i < n && j < n)
                dp[i][j] += dp[i + 1][j + 1] * (n - i) * (n - j) / (n * n);
            dp[i][j] = dp[i][j] * (n * n) / (n * n - i * j); 
        }
    }
    printf("%.7lf\n",dp[cntx][cnty]);
}

2025/7/23:修正转移方程。