扔硬币

题解：

1.如果(left ( m+k ight )> n)，那么就很明显答案为0；

2.根据条件概率：则题目就是求，在至少有(m)枚硬币是反面的情况下，恰好有(k)枚硬币是正面的概率。那么就可以设(A)为至少有(m)枚硬币是反面，(B)为恰好有(k)枚硬币是正面，答案即为(frac{Pleft ( AB ight )}{Pleft ( A ight )})；恰好(k)枚硬币是正面，则(Pleft ( AB ight )=C_{n}^{k})，至少(m)枚硬币是反面，则(Pleft ( A ight )=left ( C_{n}^{0}+C_{n}^{1}+cdots +C_{n}^{n} ight )-left ( C_{n}^{0}+C_{n}^{1}+cdots +C_{n}^{m-1} ight )=2^{n}-sum_{i=0}^{m-1}C_{n}^{i})，所以答案即为：(C_{n}^{k}/left ( 2^{n}-sum_{i=0}^{m-1}C_{n}^{i} ight )(除法又可以转为求逆元))

AC_Code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e5+10;
 5 const ll mod=1e9+7;
 6 
 7 ll n,m,k;
 8 ll F[maxn];
 9 ll qpow(ll a, ll b){//快速幂
10     ll res=1;
11     while( b ){
12         if( b&1 ) res = res*a%mod;
13         a = a*a%mod;
14         b>>=1;
15     }
16     return res;
17 }
18 
19 ll inv(ll x){//求逆元
20     return qpow(x,mod-2);
21 }
22 
23 void init(){
24     F[0]=1;
25     for(int i=1;i<=100000;i++){
26         F[i]=F[i-1]*i%mod;
27     }
28 }
29 
30 int main()
31 {
32     int t;
33     scanf("%d",&t);
34     init();
35     while( t-- ){
36         scanf("%lld%lld%lld",&n,&m,&k);
37         if( m+k>n ){
38             printf("0
");
39             continue;
40         }
41         ///C(n,k):n!/(k!*(n-k)!)
42         ll up=F[n]*inv(F[k])%mod*inv(F[n-k])%mod;
43         //2^n-sum(C(n,0)~C(n,m-1));
44         ll down=qpow(2,n);
45         ll sum=1,pre=1;
46         for(ll i=1;i<m;i++){
47             pre=pre*(n-i+1)%mod*inv(i)%mod;
48             sum = (sum+pre)%mod;
49         }
50         down = (down-sum+mod)%mod;
51         down = inv(down);
52         ll ans=up*down%mod;
53         printf("%lld
",ans);
54     }
55     return 0;
56 }

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int maxn = 1e5+10;
 5 const ll mod=1e9+7;
 6 
 7 ll n,m,k;
 8 ll F[maxn];//F[i]:1~i的阶乘
 9 ll Inv[maxn];//Inv[i]:i的逆元
10 ll Finv[maxn];//Finv[i]:F[i]的逆元
11 
12 ll qpow(ll a, ll b){//快速幂
13     ll res=1;
14     while( b ){
15         if( b&1 ) res = res*a%mod;
16         a = a*a%mod;
17         b>>=1;
18     }
19     return res;
20 }
21 
22 ll inv(ll x){//求逆元
23     return qpow(x,mod-2);
24 }
25 
26 void init(){
27     F[0]=F[1]=1;
28     Finv[0]=Finv[1]=1;
29     Inv[0]=Inv[1]=1;
30     for(int i=2;i<=100000;i++){
31         F[i]=1ll*F[i-1]*i%mod;
32         Inv[i]=1ll*(mod-mod/i)*Inv[mod%i]%mod;
33         Finv[i]=1ll*Finv[i-1]*Inv[i]%mod;
34     }
35 }
36 
37 ll C(ll a,ll b){//求C(a,b)
38     if( b>a || b<0 ) return 0ll;
39     return 1ll*F[a]*Finv[b]%mod*Finv[a-b]%mod;
40 }
41 
42 int main()
43 {
44     int t;
45     scanf("%d",&t);
46     init();
47     while( t-- ){
48         scanf("%lld%lld%lld",&n,&m,&k);
49         if( m+k>n ){
50             printf("0
");
51             continue;
52         }
53         ll up=C(n,k);//分母
54         ll down=qpow(2,n);
55         ll sum=1;
56         for(int i=1;i<m;i++){
57             sum=(sum+C(n,i))%mod;
58         }
59         down=(down-sum+mod)%mod;//分子
60         ll ans=up*inv(down)%mod;
61         printf("%lld
",ans);
62 
63     }
64     return 0;
65 }