398B

Description

We choose a grid in a $n\times n$ matrix with uniform probability. If the grid is already painted, we do nothing. Otherwise, we paint it. Repeat this operation until every row and every column has at least one painted grid. Output the expectation of the times to choose grid. ($1 \leq n \leq 2000$) In addition, there are some already painted grids are given in the input.

Tutorial

$f_{i,j}$ means the expectation to paint the empty sub-matrix of $i\times j$ (all other rows and columns have painted grids except these $i$ rows and $j$ columns) in a matrix of $n\times n$. Then $f_{i,j}$ can be calculated by its sub-problems according to which grid we choose as the next one to paint.

$f_{i,j}=1 +\frac{i\times j}{n\times n}f_{i-1,j-1} +\frac{i\times (n - j)}{n\times n}f_{i-1,j} +\frac{(n-i)\times j}{n\times n}f_{i,j-1} +\frac{(n-i)\times (n-j)}{n\times n}f_{i,j}$

Solve this equation, we can get another equation as follows, which is the status transition equation.

$f_{i,j}=\frac{1 +\frac{i\times j}{n\times n}f_{i-1,j-1} +\frac{i\times (n - j)}{n\times n}f_{i-1,j} +\frac{(n-i)\times j}{n\times n}f_{i,j-1}} {1-\frac{(n-i)\times (n-j)}{n\times n}}$

Use it to solve this problem.

From this problem, I learned that in dynamic programming, sometimes we need to solve a equation to get the status transition equation. In dynamic programming, the order of solving each sub-problem can be the same as it is in real life, however, it can also be reverse. For example, in this problem, the smallest sub-problem $f_{i,j} is the first to calculate in dynamic programming, but the last one to paint in real life.

Solution

#include <cstdio>
using namespace std;

const int MAX_N = 2 * int(1e3) + 10;
const int MAX_M = 2 * int(1e4) + 10;

int n, m;
bool row_occupied[MAX_N], col_occupied[MAX_N];
int row_occupied_num, col_occupied_num; 
double f[MAX_N][MAX_N];

void make(bool *occupied, int &occupied_num, int x)
{
    if (occupied[x])
    {
        return;
    }
    occupied[x] = true;
    occupied_num++;
}

int main()
{
    //input
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        make(row_occupied, row_occupied_num, a);
        make(col_occupied, col_occupied_num, b);
    }
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = f[i - 1][0] + 1.0 * n / i;
        f[0][i] = f[0][i - 1] + 1.0 * n / i;
    }
    for (int i = 1; i <= n - row_occupied_num; i++)
    {
        for (int j = 1; j <= n - col_occupied_num; j++)
        {
            f[i][j] = 1;
            f[i][j] += f[i - 1][j - 1] * i * j / n / n;
            f[i][j] += f[i - 1][j] * i * (n - j) / n / n;
            f[i][j] += f[i][j - 1] * (n - i) * j / n / n;
            f[i][j] /= 1 - 1.0 * (n - i) * (n - j) / n / n;
        }
    }
    printf("%.12f\n", f[n - row_occupied_num][n - col_occupied_num]);
    return 0;
}