BUPT2017 wintertraining(15) #4G
Gym - 101124 E.Dance Party
题意
有c种颜色，每个颜色最多分配给两个人，有M个男士，F个女士，求至少一对男士同色的概率。
\((1 \le C, M, F \le 10^9; M + F \le 2C)\)
题解
反面比较好求的，也就是不存在男男同色的概率。
假设每个男士依次选择剩下的颜色，第一个人有2C种选择，当前不同色的概率是1，第二个人有2C-1种选择，当前不同色的概率是(2C-2)/(2C-1)，第三个人有2C-2种选择，不同色的概率(2C-4)/(2C-2),...,于是得出公式
\[ans=1-\sum_{i=1}^{M-1}\frac {2C-2i}{2C-i}=1-\sum_{i=1}^{M-1}(1-\frac {i}{2C-i})
\]
\]
且当M很大的时候，C一定更大，那么此时ans趋于1，数学证明我也不会，但是可以直观地想象一下，男士足够多的情况下要保证没有男男同色就不太可能了。我们只要及时跳出循环即可。
另外我推得一个公式是
\[\frac{C_{c}^{m}\cdot 2^m}{C_{2c}^{m}}
\]
\]
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int c,m,f;
double ans=1;
int main() {
scanf("%d%d%d",&c,&m,&f);
for(int i=1;i<m;i++){
ans*=(1-i*1./(2*c-i));
if(ans<1e-10)break;
}
printf("%.10f",1-ans);
return 0;
}