寂静的角落 星空在前,路在脚下
卢卡斯定理 Lucas' theorem
发布于: 2021-04-04 更新于: 2021-04-05 分类于: 算法 阅读次数: 

内容

对于质数 $p$ ,有:

$$\binom{n}{m}\bmod p = \binom{\left\lfloor n/p \right\rfloor}{\left\lfloor m/p\right\rfloor}\cdot\binom{n\bmod p}{m\bmod p}\bmod p$$

(占位行,不然 Hexo 渲染下面会 Bug)

(占位行)

(占位行)

(占位行)

(占位行)

(占位行)

$\color{Green}code$

1
2
3
4
5
template <typename T>
T lucas(T n, T m, T p) {
if (m == 0) return 1;
return C(n % p, m % p, p) * lucas(n / p, m / p, p) % p;
}
本文默认采用 署名-非商业性使用-相同方式共享 4.0 国际 许可证