逆元应用求组合数

例题：here

(求C_{n}^{k}+C_{n}^{k+1}+cdots +C_{n}^{n})

(C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+C_{n}^{3}+cdots +C_{n}^{n}=2^{n})

(则C_{n}^{k}+C_{n}^{k+1}+cdots +C_{n}^{n}=2^{n}-left ( C_{n}^{0}+C_{n}^{1}+C_{n}^{2}+cdots +C_{n}^{k-1} ight ))

(2^{n}用快速幂算，C_{n}^{k}=frac{left ( n-k+1 ight )}{k}*C_{n}^{k-1}left ( 组合数递推公式 ight ))

(frac{left ( n-k+1 ight )}{k}除法改为乘法，所以求逆元)

模板：AC_Code:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 
 6 ll n,m,k;
 7 ll qpow(ll a, ll b){//快速幂
 8     ll res=1;
 9     while( b ){
10         if( b&1 ) res = res*a%mod;
11         a = a*a%mod;
12         b>>=1;
13     }
14     return res;
15 }
16 
17 ll inv(ll x){//求逆元
18     return qpow(x,mod-2);
19 }
20 
21 int main()
22 {
23     int t,cas=0;
24     scanf("%d",&t);
25     while( t-- ){
26         scanf("%lld%lld",&n,&k);
27         ll sum=1,pre=1;
28         for(ll i=1;i<k;i++){
29             pre=pre*(n-i+1)%mod*inv(i)%mod;//递推公式
30             sum=(sum+pre)%mod;
31         }
32         ll ans=qpow(2,n);
33         ans = (ans-sum+mod)%mod;
34         cas++;
35         printf("Case #%d: %lld
",cas,ans);
36     }
37     return 0;
38 }