Appearance
若无特殊说明,本章涉及的变量皆为正整数。
简介
Lucas 定理用于求解大组合数对质数
证明
我不想证。
解法
对于
cpp
/* fac[x]: x!
* inv[x]: x! 关于模 p 的乘法逆元(注意有阶乘)
* 以上需要预处理
*/
LL C(LL n, LL m) {
if (n < m)
return 0;
return fac[n] * inv[m] % P * inv[n - m] % P;
}
对于更大的组合数,套用 Lucas 定理。
其中
cpp
LL lucas(LL n, LL m) {
if (m == 0)
return 1;
return C(n % P, m % P) * lucas(n / P, m / P) % P;
}
预处理
,线性递推: ,参考 线性求逆元:
此处的
cpp
void init() {
fac[0] = fac[1] = 1;
for (LL i = 2; i <= P; i ++)
fac[i] = fac[i - 1] * i % P;
inv[0] = inv[1] = 1;
for (LL i = 2; i <= P; i ++)
inv[i] = (P - P / i) * inv[P % i] % P;
for (LL i = 2; i <= P; i ++)
inv[i] = inv[i - 1] * inv[i] % P;
}
模板
总时间复杂度:
cpp
typedef long long LL;
const int N = 1e6 + 1, P = 10007;
LL fac[N], inv[N];
void init() {
fac[0] = fac[1] = 1;
for (LL i = 2; i <= P; i ++)
fac[i] = fac[i - 1] * i % P;
inv[0] = inv[1] = 1;
for (LL i = 2; i <= P; i ++)
inv[i] = (P - P / i) * inv[P % i] % P;
for (LL i = 2; i <= P; i ++)
inv[i] = inv[i - 1] * inv[i] % P;
}
LL C(LL n, LL m) {
if (n < m)
return 0;
return fac[n] * inv[m] % P * inv[n - m] % P;
}
LL lucas(LL n, LL m) {
if (m == 0)
return 1;
return C(n % P, m % P) * lucas(n / P, m / P) % P;
}