题目描述

周末何老板到磁器口游玩。街边有小贩在组织一种打气球游戏,何老板很感兴趣。

店家立了一块布,布上画了N*N的方格,有的方格里挂上了气球,有的没有。

游戏规则如下:

第1步.观察。如果每一行都至少有一个方格没有气球,并且每一列都至少有一个方格没有气球,游戏结束。否则进行第2步。

第2步.抛骰子。店家拿出一个特制的骰子,该骰子有N个面,上面依次有1到N这N 个数字。玩家先后抛两次骰子,设第一次抛出的数字为x,设第二次抛出的数字为y (注:抛出的数字是随机的)。

第3步.打气球。若坐标为(x,y)的格子里有气球,玩家必须将其打爆。子弹1块钱一发。

如果该格子没有气球,忽略该格子,玩家不用开枪,但玩家也需要支付给店家1块钱。

第4步.继续。执行第1步。

何老板是个神枪手,他能做到百发百中。他想你帮他算算,对于当前给出的这局游戏,预计要花多少钱才能结束。

输入格式

第一行,两个整数N和M,N表示方格的尺寸,M表示游戏开始时,有M个格子里是没有气球的。

接下来M行,每行两个整数x,y,表示坐标为x,y的格子里没有气球。

输出格式

一行,一个实数,完成游戏预计花费,保留2个小数位。

样例输入1

5 2
2 3
4 1

样例输出1

11.77

样例输入2

2 2
1 1
1 2

样例输出2

2.00

样例输入3

1 1
1 1

样例输出3

0.00

样例输入4

5 5
3 4
3 2
3 5
3 1
3 3

样例输出4

10.42

数据范围

对于30%的数据,$1 ≤ N ≤ 10$

对于100%的数据,$1 ≤ N ≤ 2\times10^3\ 0≤M≤ min(N^2, 2\times10^4)\ 1≤x,y≤N$

菜鸡的咆哮

求没有完整行列时射击的期望次数。

定义$f[i][j]$表示完成一个$i$行$j$列靶子的期望次数。

边界$f[0][0]=0​$

在$f[i][j]​$的前一次射击可能有四种情况。

①射中了完整的一行但那一列不是完整的。

概率为$\cfrac{i}{n}\times\cfrac{n-j}{n}​$

②射中了完整的一列但那一行不是完整的。

概率为$\cfrac{n-i}{n}\times\cfrac{j}{n}$

③射中了完整的一行及完整的一列。

概率为$\cfrac{i}{n}\times\cfrac{j}{n}$

④既没有射中完整的一行也没有射中完整的一列。

概率为$\cfrac{n-i}{n}\times\cfrac{n-j}{n}​$

故DP方程为:

$f[i][j]$ $=(f[i-1][j]+1)\times\cfrac{i}{n}\times\cfrac{n-j}{n}\\+(f[i][j-1]+1)\times\cfrac{n-i}{n}\times\cfrac{j}{n}\\+(f[i-1][j-1]+1)\times\cfrac{i}{n}\times\cfrac{j}{n}\\+(f[i][j]+1)\times\cfrac{n-i}{n}\times\cfrac{n-j}{n}$

化简后得:

$f[i][j]=\cfrac{(f[i-1][j]+1)\times\cfrac{i}{n}\times\cfrac{n-j}{n}+(f[i][j-1]+1)\times\cfrac{n-i}{n}\times\cfrac{j}{n}+(f[i-1][j-1]+1)\times\cfrac{i}{n}\times\cfrac{j}{n}+\cfrac{n-i}{n}\times\cfrac{n-j}{n}}{1-\cfrac{n-i}{n}\times\cfrac{n-j}{n}}​$

注意边界的判断。

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
double n,m;
int vis[3][2000];
double f[2000][2000];
int main(){
    cin>>n>>m;
    int xx;
    int r[10];
    memset(r,0,sizeof(r));
    for(int i=1;i<=m;i++){
        for(int k=1;k<=2;k++){
            cin>>xx;
            if(vis[k][xx]==0){
                r[k]++;
                vis[k][xx]=1;
            }
        }
    }
    int rx=n-r[1],ry=n-r[2];
    for(int i=0;i<=rx;i++){
        for(int j=0;j<=ry;j++){
            if(i==0&&j==0) continue;
            if(i!=0)
            f[i][j]+=(f[i-1][j]+1)*i/n*(n-j)/n;
            if(j!=0)
            f[i][j]+=(f[i][j-1]+1)*j/n*(n-i)/n;
            if(i!=0&&j!=0)
            f[i][j]+=(f[i-1][j-1]+1)*i/n*j/n;
            f[i][j]+=(n-i)/n*(n-j)/n;
            f[i][j]/=(1-(n-i)/n*(n-j)/n);
        }
    }
    printf("%.2lf\n",f[rx][ry]);
    return 0;
}