Lucas定理及其扩展原理及应用
Lucas定理（Lucas’s theorem）
内容
对于非负整数m和n和素数p，有
\mathrm{C}_n^m \equiv \prod_{i=0}^k \mathrm{C}_{n_i}^{m_i} \pmod{p}
其中，m = m_kp^k + m_{k-1}p^{k-1} + \cdots + m_1p + m_0且n = n_kp^k + n_{k-1}p^{k-1} + \cdots + n_1p + n_0。
也就是说，这个是m和n的p进制展开。
当m < n时，\mathrm{C}_n^m = 0。
求组合数的值
既然我们可以把m和n以p进制展开求值，那么我们可以设计递归来解决这个问题。
我们知道\mathrm{C}_n^0 = 1，那么以m=0为递归终点即可。代码如下。
inline LL lucas(LL n, LL m, LL p) {
if(!m) return 1;
return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
其中C就是直接求组合数值的函数，这个可以预处理杨辉三角或者预处理阶乘及阶乘逆元。
例题：【P3807】【模板】卢卡斯定理 – 洛谷
直接应用上述方法即可。代码如下。
// Code by KSkun, 2018/3
#include <cstdio>
#include <algorithm>
typedef long long LL;
inline char fgc() {
static char buf[100000], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}
inline LL readint() {
register LL res = 0, neg = 1;
char c = fgc();
while(c < '0' || c > '9') {
if(c == '-') neg = -1;
c = fgc();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = fgc();
}
return res * neg;
}
const int MAXN = 100005;
LL T, n, m, p, inv[MAXN], mul[MAXN];
inline LL C(LL n, LL m, LL p) {
if(m > n) return 0;
return mul[n] * inv[n - m] % p * inv[m] % p;
}
inline LL lucas(LL n, LL m, LL p) {
if(!m) return 1;
return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
inline void init() {
mul[0] = inv[0] = mul[1] = inv[1] = 1;
for(int i = 2; i <= std::min(n, p); i++) {
inv[i] = -(p / i) * inv[p % i] % p;
}
for(int i = 2; i <= std::min(n, p); i++) {
inv[i] = inv[i] * inv[i - 1] % p;
mul[i] = mul[i - 1] * i % p;
}
}
int main() {
T = readint();
while(T--) {
n = readint(); m = readint(); p = readint(); n += m;
init();
printf("%lld\n", (lucas(n, m, p) + p) % p);
}
return 0;
}
扩展Lucas定理（exLucas）
内容
扩展Lucas定理与Lucas定理的区别是模数非质数，此时，我们考虑将模数质因数分解如下。
P = p_1^{k_1} \cdot p_2^{k_2} \cdots p_n^{k_n}
只要我们能求出组合数对于每个p_i^{k_i}的余数，我们就可以利用中国剩余定理（中国剩余定理及其扩展原理及应用 | KSkun’s Blog）解决这个问题。也就是说，我们将问题变为了这个：
\begin{cases} \mathrm{C}_n^m \equiv a_1 \pmod{p_1^{k_1}} \\ \mathrm{C}_n^m \equiv a_2 \pmod{p_2^{k_2}} \\ \vdots \\ \mathrm{C}_n^m \equiv a_n \pmod{p_n^{k_n}} \end{cases}
现在的问题是，上面每个式子的余数怎么求出。
如果我们使用组合数的定义，我们可以分别求出n! \bmod p_i^{k_i}, m! \bmod p_i^{k_i}, (n-m)! \bmod p_i^{k_i}。
首先，我们知道阶乘中存在一些p_i因子，对于这些因子我们可以处理出来单独运算。对于提取一个因子后的阶乘，我们观察它们的规律。假如p=3，要求10!，提取后就变成了：
1 \times 2 \times 1 \times 4 \times 5 \times 2 \times 7 \times 8 \times 3 \times 10 \times 3^3
p_i的倍数组成了一个新的阶乘，这一部分我们递归下去处理。考虑剩下的部分，即1 \times 2 \times \cdots \times (p_i^{k_i}-1) \times (p_i^{k_i}+1) \times \cdots \times (2p_i^{k_i}-1) \times \cdots。我们发现\prod_{i=1, i \bmod p_i \neq 0}^{p_i^{k_i}-1} i \equiv \prod_{i=p_i^{k_i}+1, i \bmod p_i \neq 0}^{2p_i^{k_i}-1} i \pmod{p_i^{k_i}}，也就是说，只需要求一个长为p_i^{k_i}的阶乘，并且计算有多少完整的一段，使用快速幂即可求出。至于多出去的那段，直接暴力乘进去即可。
例题：[国家集训队]礼物 题解 | KSkun’s Blog
代码参见该题题解文章。代码内有注释，可以对照上述内容理解。
