题意

1. 给我们一个 n*m 的棋盘，每天我们会在棋盘上放一个棋子，问使每一行每一列至少有一个棋子所需要的期望天数是多少？

思路

1. 直接求期望，不太好 dp
2. 但是我们可以通过期望求解公式：E (X) = X1p(X1） + X2p (X2） + …… + Xn*p (Xn) 来求解。
3. 我们设状态转移方程：dp [i][j][k] 表示棋子 i 行 j 列已经有棋子占领了，在摆放 k 个棋子的时候的概率。
4. 初始状态：dp [1][1][1] = 1.0
5. 我们通过递推进行状态转移对于 dp [i][j][k] 可以递推出：dp [i][j][k+1]、dp [i+1][j][k+1]、dp [i][j+1][k+1]、dp [i+1][j+1][k]
6. 那么期望就是：E (X) = 1 * dp [n][m][1]+2 * dp [n][m][2] + …… + k*dp [n][m][k]…

代码

#include <bits/stdc++.h>
using namespace std;const int N = 55;
int n, m;
double dp[N][N][N * N];int main()
{int T; scanf("%d", &T);while (T --){scanf("%d %d", &n, &m);memset(dp, 0, sizeof dp);dp[1][1][1] = 1;for (int i = 1; i <= n; i ++)for (int j = 1; j <= m; j ++)for (int k = 1; k <= i * j; k ++) {if (i < n || j < m)   				//这个特判必须要加dp[i][j][k + 1] += dp[i][j][k] * (i * j - k) / (n * m - k);dp[i + 1][j][k + 1] += dp[i][j][k] * (n - i) * j / (n * m - k);dp[i][j + 1][k + 1] += dp[i][j][k] * i * (m - j) / (n * m - k);dp[i + 1][j + 1][k + 1] += dp[i][j][k] * (n - i) * (m - j) / (n * m - k);}double ans = 0;for (int i = 1; i <= n * m; i ++) {ans += dp[n][m][i] * i;}   printf("%.12f\n", ans);}return 0;
}