algorithm - 计算 nCr 模 p，一个素数

Question

我正在尝试计算 nCr 模 p，其中 p 是素数。

我尝试过的一种方法是计算 n!/(r! * (n-r)!) modulo p 使用乘法逆元，但是当 r 或 n - r 大于或等于 p 时，这会失败，因为那时阶乘为零模 p 并且逆元不存在。

哪种方法适用于所有情况，而不仅仅是存在乘法逆元时？

Answer 1

我会使用 Lucas's theorem

C(14,1), p=13
N = 14 = 1 * 13 + 1
K = 1  = 0 * 13 + 1
C(N,K) mod p = (C(1,0) mod 13 ) * (C(1,1) mod 13) = 1