原题链接
思路:
概率 dp
以 \(d(i,j,k)\) 表示已摆放 \(i\) 个棋子，这 \(i\) 个棋子占据 \(j\) 行 \(k\) 列的概率.
则有如下转移方程:
当 \(j=n \land
k=m\) 时去掉第一项 (意味着填满后不继续放棋子)
边界条件为 \(d(1,1,1)=1\),
答案为 \(\sum_{i=1}^{nm} i \times
d(i,n,m)\)
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
const int Mn(55),Mx(5050);
double dp[Mx][Mn][Mn];
int main() {
int T;
scanf("%d",&T);
while(T--) {
int n,m;
scanf("%d %d",&n,&m);
if(n>m) {
swap(n, m);
}
memset(dp,0,sizeof dp);
dp[1][1][1] = 1;
for(int i(2);i<=m*n;++i) {
for(int j(1);j<=n;++j) {
for(int k(1);k<=m;++k) {
if(j<n||k<m) {
dp[i][j][k] += dp[i - 1][j][k] * (j * k - i + 1) / (double) (n * m - i + 1);
}
dp[i][j][k] += dp[i-1][j-1][k]*((n-j+1)*k)/(double)(n*m-i+1);
dp[i][j][k] += dp[i-1][j][k-1]*(j*(m-k+1))/(double)(n*m-i+1);
dp[i][j][k] += dp[i-1][j-1][k-1]*((n-j+1)*(m-k+1))/(double)(n*m-i+1);
}
}
}
double ans(0);
for(int i(1);i<=m*n;++i) {
ans += dp[i][n][m]*i;
}
printf("%.8f\n",ans);
}
return 0;
}
|