lucas定理计算组合数

C(n,k)有多种解法，1，dp递推；2，直接计算；3，lucas定理

lucas定理适合组合数取余数的计算，n和k的范围可到10^18

注意p必须为素数

如果p(mod)较小还可以预处理1到p的阶乘，下面是用乘法逆元计算C(n%p,k%p)，关于乘法逆元，参考这篇博客：http://www.cnblogs.com/tiankonguse/archive/2012/08/14/2638949.html

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<algorithm>
 6 
 7 using namespace std;
 8 
 9 const int maxn=1000100;
10 const int INF=(1<<29);
11 const int p=10007;
12 
13 typedef unsigned long long ll;
14 
15 ll n,m;
16 
17 ll qpow(ll n,ll k)
18 {
19     ll res=1;
20     while(k){
21         if(k&1) res=(res%p)*(n%p)%p;
22         n=(n%p)*(n%p)%p;
23         k>>=1;
24     }
25     return res;
26 }
27 
28 ll C(ll n,ll k)
29 {
30     if(n<k) return 0;
31     ll res=1;
32     for(int i=1;i<=k;i++){
33         ll a=(n-k+i)%p;
34         ll b=i%p;
35         res=res*(a*qpow(b,p-2)%p)%p;
36     }
37     return res%p;
38 }
39 
40 ll lucas(ll n,ll k)
41 {
42     if(k==0) return 1;
43     return (C(n%p,k%p)%p)*(lucas(n/p,k/p)%p)%p;
44 }
45 
46 int main()
47 {
48     while(cin>>n>>m){
49         cout<<lucas(m,n)<<endl;
50     }
51     return 0;
52 }

View Code

下面是kuangbin大神的模版

long long F[100010];
void init(long long p)
{
    F[0] = 1;
    for(int i = 1;i <= p;i++)
        F[i] = F[i-1]*i%p;
}
long long inv(long long a,long long m)
{
    if(a == 1)return 1;
    return inv(m%a,m)*(m-m/a)%m;
}
long long Lucas(long long n,long long m,long long p)
{
    long long ans = 1;
    while(n&&m)
    {
        long long a = n%p;
        long long b = m%p;
        if(a < b)return 0;
        ans = ans*F[a]%p*inv(F[b]*F[a-b]%p,p)%p;
        n /= p;
        m /= p;
    }
    return ans;
}

View Code

没有AC不了的题，只有不努力的ACMER！