链接:https://ac.nowcoder.com/acm/contest/5758/D
来源:牛客网
题目描述
有n枚硬币,每枚硬币扔出来是正面和反面的概率各占50%。小明同时扔下了n枚硬币后,已知至少有m枚硬币是反面。请问恰好有k枚硬币是正面的概率是多少。
输入描述:
输入t,代表有t组数据。每组数据输入一个数n,m,k,代表有n枚硬币,抛出以后至少有m枚是反面的情况下,恰好有k个正面的概率。
(t<=1000,n<1e5,m<=1000,k<=n)
输出描述:
对于结果是p/q,输出分数取模1e9+7后的结果。
示例1
输出
复制797520667
#include<bits/stdc++.h> using namespace std; typedef long long ll; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } #define pi 3.14159265358979323846 const int INF=0x3f3f3f3f; const int mod=1e9+7; const int maxn=1e6+100; const int maxa=1e9+10; ll n,m,p,t; ll f[maxn]; ll qpow(ll a,ll b){ ll ans=1; while(b){ if(b&1){ ans=(ans*a)%mod; } b>>=1; a=(a*a)%mod; } return ans; } ll cal(int m,int n){ if(m<n){ return 0; } return f[m]*qpow(f[m-n],mod-2)%mod*qpow(f[n],mod-2)%mod; } int main(){ cin>>t; f[0]=1; for(int i=1;i<=1e5;i++){ f[i]=(1ll*f[i-1]*i)%mod; } while(t--){ cin>>n>>m>>p; if(m+p>n){ printf("0 "); } else{ ll ans=0; for(int i=0;i<m;i++){ ans=(ans+cal(n,i))%mod; } ans=(qpow(2,n)-ans+mod)%mod; ans=qpow(ans,mod-2); printf("%lld ",(ans*cal(n,p))%mod); } } return 0; }