题解：P3807 【模板】卢卡斯定理/Lucas 定理
BlackHoles
·
·
题解
注：大部分题解都有证明过程，但本片题解提供了数学和信息竞赛常用的两种卢卡斯定理形式，并附有简洁的表达与美观的公式，方便学习。
前置知识
逆元，组合数学，二项式定理。
部分过程摘自算法竞赛。
定理背景
常用的逆元求组合数 C_{n}^{r}\bmod m 具有局限性：当 m<n 时，不能保证 n 和 n-r 的逆元存在。用公式递推计算，复杂度为 O(n^2)，比较低效。
正解：卢卡斯定理
对于非负整数 n，r 和素数 m，有：
在信息学竞赛中，常用卢卡斯定理的另一种表达：（以下除法均表示向下取整）
$C_{n}^{r}\equiv C_{n\bmod m}^{r\bmod m}\times C_{\frac{n}{m}}^{\frac{r}{m}}\bmod m$。
证明略，需要用到二项式定理。
### 实现过程
对于 $C_{n\bmod m}^{r\bmod m}$，因为 $r\bmod m$ 和 $n\bmod m$ 都比 $m$ 小，可以使用逆元求解组合数。
对于 $C_{\frac{n}{m}}^{\frac{r}{m}}$，继续用卢卡斯定理展开，运用递归求解。
### 细节全讲
读者对照代码看。
求组合数的 $C$ 函数中，若 $r>n$，应返回 $0$。
核心的卢卡斯函数中，边界条件是 $r=0$。
需要在卢卡斯函数前预处理阶乘数组。
### 代码
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100005;
int T;
ll n, m, p;
ll fac[N];
ll fastPow(ll base, ll power, ll mod) { // 快速幂
ll res = 1;
base %= mod;
while (power) {
if (power & 1)
res = res * base % mod;
base = base * base % mod;
power >>= 1;
}
return res;
}
ll inverse(ll a, ll p) { // 求解逆元
ll res = fastPow(a, p-2, p);
return res;
}
ll C(ll n, ll r, ll p) {
if (r > n)
return 0;
ll res = (fac[n] * inverse(fac[r], p) % p) * inverse(fac[n-r], p) % p;
return res;
}
ll Lucas(ll n, ll r, ll p) {
if (r == 0) // 注意边界条件
return 1;
ll res = C(n % p, r % p, p) * Lucas(n / p, r / p, p) % p; // 核心递归式子
return res;
}
int main(void) {
cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
cin >> n >> m >> p;
fac[0] = 1; // 预处理阶乘数组
for (int i = 1; i <= p; ++i)
fac[i] = fac[i-1] * i % p;
cout << Lucas(n + m, n, p) << '\n';
}
return 0;
}
```