卢卡斯定理

A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]…a[0]，B=b[n]b[n-1]…b[0]。
则组合数C(A,B)与C(a[n],b[n])C(a[n-1],b[n-1])…C(a[0],b[0]) modp同余
即：Lucas(n,m,p)=c(n%p,m%p)Lucas(n/p,m/p,p)
注意这儿的p是素数是有必要的。
Lucas最大的数据处理能力是p在10^5左右，不能再大了，hdu 3037就是10^5级别的！
对于大组合数取模，n,m不大于10^5的话，用逆元的方法，可以解决。对于n,m大于10^5的话，那么要求p<10^5，这样就是Lucas定理了，将n,m转化到10^5以内解。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
#define ll long long
#define mod 110119
ll factorial[110200];    
ll mod_pow(ll a,ll n,ll p)  
{  
    ll ret=1,A=a;
    for(; n ; A=(A*A)%p,n>>=1) if(n & 1)ret=(ret*A)%p;  
    return ret;  
}  
void init_factorial(ll p)  
{  
    factorial[0] = 1;  
    for(ll i = 1;i <= p;i++)factorial[i] = factorial[i-1]*i%p;  
}  
  
ll C(ll a,ll k,ll p) //求C(n,m)%p p最大为10^5。a,b可以很大！  a个数中挑k个的组合数
{  
    ll re = 1;  
    for(; a && k ; a /= p , k /= p){
        ll aa = a%p;ll bb = k%p;  
        if(aa < bb) return 0; //这个是最后的改动！  
        re = re*factorial[aa]*mod_pow(factorial[bb]*factorial[aa-bb]%p,p-2,p)%p;//这儿的求逆不可先处理  
    }
    return re;  
}  
ll Lucas(ll a,ll k ,ll p){// 在 a个不同糖果里挑出来k个，取膜p
    if(a<0 || k<0 || a<k)return 0;
    else return C(a,k,p);
}
int main(){
    init_factorial(11);//11是mod
    cout<<"take 2 candies in box which has 5 and mod 5 ____"<<Lucas(5,2,11)<<endl;
    cout<<"take 3 candies in box which has 7 and mod 5 ____"<<Lucas(7,3,11)<<endl;
    cout<<"wrong input : "<<Lucas(-1,-2,11)<<endl;
    cout<<"wrong input : "<<Lucas(3,9,11)<<endl;
    cout<<"wrong input : "<<Lucas(3,-2,11)<<endl;
    return 0;
}