---

題目傳送門

---

思路

狀態設計

設 $d{p}_{i,j}$ 表示袋中有 $i$ 個白鼠和 $j$ 個黑鼠時，$A$ 能贏的概率。

狀態轉移

現在考慮抓鼠情況：

1. $A$ 抓到白鼠：直接判 $A$ 贏，概率是 $\frac{i}{i+j}$；
2. $A,B$ 都抓到一只黑鼠，并且跑出來一只黑鼠：概率為 $\frac{j}{i+j}\times \frac{j?1}{i+j?1}\times \frac{j?2}{i+j?2}$，然后轉移到 $d{p}_{i,j?3}$，故此情況下 $A$ 獲勝的概率為 $\frac{j}{i+j}\times \frac{j?1}{i+j?1}\times \frac{j?2}{i+j?2}\times d{p}_{i,j?3}$；
3. $A,B$ 都抓到一只黑鼠，并且跑出來一只白鼠：概率為 $\frac{j}{i+j}\times \frac{j?1}{i+j?1}\times \frac{i}{i+j?2}$，然后轉移到 $d{p}_{i?1,j?2}$，故此情況下 $A$ 獲勝的概率為 $\frac{j}{i+j}\times \frac{j?1}{i+j?1}\times \frac{i}{i+j?2}\times d{p}_{i?1,j?2}$；
4. $B$ 抓到白鼠：此情況 $A$ 失敗，故不考慮。

所以總得轉移方程就是：
$$d{p}_{i,j}=\frac{i}{i+j}+\frac{j}{i+j}\times \frac{j?1}{i+j?1}\times \frac{j?2}{i+j?2}\times d{p}_{i,j?3}+\frac{j}{i+j}\times \frac{j?1}{i+j?1}\times \frac{i}{i+j?2}\times d{p}_{i?1,j?2}$$
當然轉移的時候得分別判斷【$j$ 是否大于等于 $3$】和【$i$ 是否大于等于 $1$ 且 $j$ 是否大于等于 $2$】。

邊界條件

1. 在沒有老鼠或全是黑鼠的情況下，$A$ 一定輸，即：$?i\in [0,m],d{p}_{0,i}=0$；
2. 在只有白鼠的情況下，$A$ 一定贏，即：$?i\in [1,n],d{p}_{i,0}=1$。

復雜度

• 時間復雜度：$O(n\times m)$；
• 空間復雜度：$O(n\times m)$。

---

代碼

#include <bits/stdc++.h>using namespace std;typedef long long ll;const int maxn = 1e3 + 7;int n, m;
double dp[maxn][maxn];
int main() {scanf("%d%d", &n, &m);for (int i = 0; i <= m; ++i) dp[0][i] = 0;  // 沒有老鼠或只有黑鼠, B 贏 for (int i = 1; i <= n; ++i) dp[i][0] = 1;  // 只有白鼠, A 贏for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {dp[i][j] += 1.0 * i / (i + j);if (j >= 3) {dp[i][j] += 1.0 * j / (i + j) * 1.0 * (j - 1) / (i + j - 1) *1.0 * (j - 2) / (i + j - 2) * dp[i][j - 3];}if (i >= 1 && j >= 2) {dp[i][j] += 1.0 * j / (i + j) * 1.0 * (j - 1) / (i + j - 1) * 1.0 * i / (i + j - 2) * dp[i - 1][j - 2];}}}printf("%.9lf\n", dp[n][m]);return 0;
}