https://codeforces.com/gym/101124
题意:
有 \(C\) 种颜色,每个颜色最多分配给两个人,有 \(M\) 个男士,\(F\) 个女士,求至少一对男士同色的概率
\(1\le C,M,F\le10^9;M+F\le 2C\)
思路:
不用考虑女士。可以算出所有男士都不同色的概率:
\[p = \frac {C_c^m\cdot 2^m}{C_{2c}^{m}} \]\(2^m\) 是因为每个男士选到的颜色可能是两个相同颜色中的一个
答案就是 \(1-p\) 。
直接算会超时,注意到 \(p\) 是递减的, \(m\) 很大时 \(p\) 很小,所以算到精度后退出就行了
#include <bits/stdc++.h>
using namespace std;
signed main()
{
int c, m, f; cin >> c >> m >> f;
double ans = 1;
for(int i = 0; i < m; i++)
{
ans *= 2; ans *= c-i; ans /= 2*c-i;
if(ans < 1e-11) break;
}
cout << fixed << setprecision(11) << 1-ans;
return 0;
}