Lucas模板

 1 ///Lucas模板
 2 LL quick_mod(LL a, LL b)
 3 {
 4     LL ans = 1;
 5     a %= p;
 6     while(b)
 7     {
 8         if(b & 1)
 9         {
10             ans = ans * a % p;
11             b--;
12         }
13         b >>= 1;
14         a = a * a % p;
15     }
16     return ans;
17 }
18 
19 LL C(LL n, LL m)
20 {
21     if(m > n) return 0;
22     LL ans = 1;
23     for(int i=1; i<=m; i++)
24     {
25         LL a = (n + i - m) % p;
26         LL b = i % p;
27         ans = ans * (a * quick_mod(b, p-2) % p) % p;
28     }
29     return ans;
30 }
31 
32 LL Lucas(LL n, LL m)
33 {
34     if(m == 0) return 1;
35     return C(n % p, m % p) * Lucas(n / p, m / p) % p;
36 }