Lucas定理模板
如题= =自用模板

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
/* Cn下m上 p范围<1e5且需是素数 */  
class Lucas{
long quickmod(long a,long b,long p){
long res = 1;
while(b!=0){
if(b%2!=0) res = (res*a)%p;
a = (a*a)%p;
b /=2;
}
return res;
}
long Comb(long a,long b, long p){
if(a < b) return 0;
if(a == b) return 1;
if(b > a-b) b = a-b;
long ans = 1, ca = 1, cb = 1;
for(long i=0; i<b; ++i){
ca = (ca*(a-i))%p;
cb = (cb*(b-i))%p;
}
ans = (ca*quickmod(cb, p-2, p))%p;
return ans;
}
long Lucas(int n, int m, int p){
long ans = 1;
while(n!=0 && m!=0 && ans!=0){
ans = (ans * Comb(n%p, m%p, p))%p;
n /= p;
m /= p;
}
return ans;
}
}