一、为什么学卢卡斯定理？
Mermaid · 渲染中（下方为源码）
graph TD A[C(n,m) mod p] --> B[拆 n,m 为 p 进制] B --> C[逐位 C(n_i,m_i)] C --> D[乘积 mod p]
求大组合数模素数：C(n, m) mod p（p 为素数，n、m 可达 10^18）。直接阶乘会溢出且 n 太大无法预处理。
二、定理
若 n = n_k p^k + … + n_0，m = m_k p^k + … + m_0（p 进制），
则 C(n, m) ≡ Π C(n_i, m_i) (mod p)。
递归形式：C(n, m) ≡ C(⌊n/p⌋, ⌊m/p⌋) · C(n mod p, m mod p) (mod p)。
三、实现
int lucas(long n, long m, int p) {
if (m == 0) return 1;
return (int)((long) lucas(n / p, m / p, p) * comb((int)(n % p), (int)(m % p), p) % p);
}
int comb(int n, int m, int p) { // 小范围阶乘
if (m > n) return 0;
long r = 1;
for (int i = 1; i <= m; i++)
r = r * (n - m + i) % p * inv(i, p) % p;
return (int) r;
}