扔硬币（组合数数学+分数取模）

链接：https://ac.nowcoder.com/acm/contest/5758/D
来源：牛客网

题意：

有n枚硬币，正反概率相同，已知至少有m枚硬币是反面，问恰好有k枚硬币是正面的概率是多少。

分析：

首先很容易，当正面硬币数+反面硬币数大于总硬币，即m+k>n时，结果不存在，概率为0。
接下来考虑一下其他合法情况，先设A为至少有m枚硬币是反面，B为恰好有k枚硬币是正面，A为已知条件，所以由高中的概率可得，P（B∣A）=P（AB）/P(A)，因为 P（AB）和 P(A) 分母均为n，所以可以转化为方案数。

P（AB）：使A，B同时成立的条件为 C（n,k）或者 C（n,m）。
P(A) ：直接求不太好弄，逆向思维转化成总方案数减去不合法的情况d，d就是有x枚硬币是反面而且x<m的所有情况，总的方案数是2^n。

所以公式为：

当然这公式涉及到两个问题

1：求组合数：传统的递推方法由于数据大可能会超时，也可能因为除法mod会超范围，所以我们可以先预处理出所有阶乘取模的余数fact[N]，以及所有阶乘取模的逆元infact[N]
如果取模的数是质数，可以用费马小定理求逆元。
费马小定理：
2：分数取模：处理p/q%mod，这就是相当于p*q的逆元%mod；

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100010,mod=1e9+7;
LL fact[N],infact[N];//阶乘，逆元
LL quickpow(LL a,LL b)//a为底数，b为指数
{
    LL res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
LL C(LL a,LL b)
{
    return fact[a]*quickpow(fact[b]*fact[a-b]%mod,mod-2)%mod;
}

int main()
{
    int t;
    cin>>t;
    fact[0]=1;
    infact[0]=1;
    for(int i=1;i<=100005;i++){//打表
        fact[i]=fact[i-1]*i%mod;//阶乘
        infact[i]=quickpow(fact[i],mod-2);//逆元
    }
    while(t--)
    {
        LL n,m,k;
        cin>>n>>m>>k;
        if(k+m>n) cout<<0<<endl;
        else{
            LL a=C(n,k);
            LL b=quickpow(2,n);
            for(int i=0;i<m;i++)    b-=C(n,i);
            b=((b%mod)+mod)%mod;
            cout<<a*quickpow(b,mod-2)%mod<<endl;//p*q的逆元%mod 分数取模
        }
    }
    return 0;
}