CF148D Bag of mice 题解

题目链接：CF148D Bag of mice

题意：

龙和公主在争论新年夜应该做什么。龙建议飞到山上观看在月光下跳舞的仙女，而公主认为他们应该早点睡觉。他们急于达成一个友好的协议，所以决定把这交给运气。

他们轮流从一个袋子里抽取老鼠，这个袋子里最初包含 \(w\) 只白鼠和 \(b\) 只黑鼠。第一个抽到白鼠的人获胜。在龙每次抽完老鼠后，袋子里的其余老鼠都会惊慌失措，其中一只会自己跳出袋子（公主抽老鼠时很小心，不会吓到其他老鼠）。公主先抽。公主获胜的概率是多少？

如果袋子里没有老鼠了，并且没有人抽到白鼠，则龙获胜。自己跳出袋子的老鼠不算作被抽出（不决定胜负）。一旦老鼠离开袋子，它就不会再返回。每只老鼠被抽出的概率是相同的，每只老鼠跳出袋子的概率也是相同的。

输入格式：

唯一一行输入数据包含两个整数 \(w\) 和 \(b\)（\(0 \leq w, b \leq 1000\)）。

输出格式：

输出公主获胜的概率。如果答案的绝对误差或相对误差不超过 \(10^{-9}\)，则认为答案是正确的。

不会翻译可以不翻译，有的人真是连 ChatGPT 都不如。

设 \(f(i,j)\) 表示有 \(i\) 只白老鼠和 \(j\) 只黑老鼠时先手获胜的概率。

边界 \(f(i,0)=1,~f(i,1)=\frac{i}{i+1}\) 。考虑转移，

• 先手抽到白鼠，获胜概率为 \(\frac{i}{i+j}\) 。

• 先手抽到黑鼠，后手抽到白鼠，获胜概率为 \(0\) 。

• 先手抽到黑鼠，后手抽到黑鼠，跑了一只白鼠，获胜概率为 \[ \frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{i}{i+j-2} \times f(i-1, j-2) \]

• 先手抽到黑鼠，后手抽到黑鼠，跑了一只黑鼠，获胜概率为 \[ \frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{j-2}{i+j-2} \times f(i, j-3) \]

因此 \[ \small f(i, j)=\frac{i}{i+j}+\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{i}{i+j-2} \times f(i-1, j-2)+\frac{j}{i+j} \times \frac{j-1}{i+j-1} \times \frac{j-2}{i+j-2} \times f(i,j-3) \] 最后答案就是 \(f(n,m)\) 。

时间复杂度 \(\mathcal{O}(nm)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e3 + 15))

double f[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n, m; cin >> n >> m;
    for(int i = 1; i <= n; i++) f[i][0] = 1, f[i][1] = (double)i / (i + 1);
    for(int i = 1; i <= n; i++)
        for(int j = 2; j <= m; j++)
        {
            f[i][j] = (double)i / (i + j);
            f[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * i / (i + j - 2) * f[i - 1][j - 2];
            if(j != 2) f[i][j] += (double)j / (i + j) * (j - 1) / (i + j - 1) * (j - 2) / (i + j - 2) * f[i][j - 3];
        }
    cout << fixed << setprecision(12) << f[n][m] << '\n';
    return 0;
}

---

参考文献：

[1] https://www.luogu.com.cn/article/169c3a75