题解 CF107B Basketball Team

XL4453 · 2021-11-07 16:16:20 · 题解

解题思路：

简单组合问题，式子和其他人推的不太一样。

正难则反，其实就是一个“抛硬币至少有一次正面”的类似问题。

将所有的人划分成几个集合，必选的那个人，和那个人一个系的其他学生，设为 a，不和那个人一个系的学生，设为 b。

把必选的那一个人抛开讨论，也就是要求从 a+b 个人中选择 k-1 个人使得不存在 a 中的人。

考虑求出全是 b 中人的概率，然互用 1 去减就得到了答案，也就是 1-\dfrac{\dbinom{b}{k-1}}{\dbinom{a+b}{k-1}}。由于没有取模，直接求然后做除法会炸。

所以化下来，得到：1-\dfrac{\dfrac{b!}{(k-1)!(b-k+1)!}}{\dfrac{(a+b)!}{(k-1)!(a+b-k+1)!}}。

然后约分，得到：1-\dfrac{\dfrac{b!}{(b-k+1)!}}{\dfrac{(a+b)!}{(a+b-k+1)!}}。

换下位置，写漂亮一点：1-\dfrac{\prod_{i_1=1}^{b}i_1\ \prod_{i_2=1}^{a+b-k+1}i_2}{\prod_{i_3=1}^{a+b}i_3\ \prod_{i_4=1}^{b-k+1}i_4}。

然后再化：1-\dfrac{\prod_{i_2=b-k+2}^{a+b-k+1}i_2}{\prod_{i_1=b+1}^{a+b}i_1}。

这个式子求起来就很方便啦。

好在这题不卡精度，不然后不知道要调多久。

代码：

#include<cstdio>
using namespace std;
int n,k,h,a,b,x;
double ans;
int main(){
    scanf("%d%d%d",&k,&n,&h);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        if(i==h)a=x;
        else b+=x;
    }
    if(k>a+b){
        printf("-1\n");
        return 0;
    }
    ans=1;a--;
    for(int i=1;i<=a;i++)
    ans=ans*(b-k+1+i)/(b+i);
    ans=1-ans;
    printf("%.8lf",ans);
    return 0;
}