数论-朴素卢卡斯(Lucas)模板

montgomery() 函数计算 t1^t2 % p 的值.

 1 typedef long long LL;
 2 
 3 LL mont(LL t1, LL t2)
 4 {
 5     LL ans = 1;
 6     t1 %= _P;
 7     while (t2) {
 8         if (t2 & 1) ans = ans*t1%_P;
 9         t2 >>= 1, t1 = t1*t1%_P;
10     }
11     return ans;
12 }
13 
14 LL C(LL dn, LL up)
15 {
16     if (!up || up == dn) return 1;
17     if (dn-up < up) up = dn-up;
18     LL t1 = 1, t2 = 1;
19     for (LL i = 1; i <= up; ++i) {
20         t1 = t1 * i % _P;
21         t2 = t2 * (dn-i+1) % _P;
22     }
23     return t2 * mont(t1, _P-2) % _P;
24 }
25 
26 LL Lucas(LL dn, LL up)
27 {
28     if (!up) return 1;
29     return C(dn%_P, up%_P) * Lucas(dn/_P, up/_P) % _P;
30 }