gym101124 E. Dance Party(排列组合)

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;
}

上一篇:ThinkPHP框架设计与扩展总结


下一篇:cf1330 D. Dreamoon Likes Sequences(计数)