http://cogs.pro:8080/cogs/problem/problem.php?pid=vNQJJVUVj
再写个数学水题，其实lucas适用于m,n比较大而p比较小的情况。
题意：给出两个数n,m，求出C(n,m) mod 1000000007的值 (n <= 2 *1e5)
思路：先预处理出组合数，其中逆元用快速幂求，因为如果p是质数，a^p = a (mod p)，a的逆元就是a^(p-2)。然后直接lucas就完了。
1 #include<bits/stdc++.h> 2 #define fo(x) freopen(x".in","r",stdin); freopen(x".out","w",stdout); 3 using namespace std; 4 typedef long long ll; 5 6 ll pow_mod(ll a,ll x,ll p){ 7 ll ret = 1; 8 while(x){ 9 if(x&1) ret = ret*a%p; 10 a = a*a%p; 11 x >>= 1; 12 } 13 return ret; 14 } 15 16 ll C(ll n,ll m, ll p){ 17 if(m==0) return 1; 18 if(m>n-m) m = n-m; 19 ll up = 1,down = 1; 20 for(int i=1;i<=m;i++){ 21 up = (up*(n-i+1))%p; 22 down = down*i%p; 23 } 24 return up*pow_mod(down,p-2,p)%p; 25 } 26 27 ll lucas(ll a,ll b,ll p){ 28 if(b==0) return 1; 29 return C(a%p,b%p,p)*lucas(a/p,b/p,p); 30 } 31 32 int main(){ 33 fo("combination"); 34 ll n,m,p=1000000007; 35 cin>>n>>m; 36 cout<<lucas(n,m,p)<<endl; 37 return 0; 38 }