计算 nCr 模 p，一个素数

Question

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

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

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

Answer 1

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

Answer 2

计算nCr模p,p为质数

使用
预先计算 n 模 p 的阶乘 事实[n]=n*事实[n-1]%p
使用
预先计算 n 模 p 的阶乘的倒数 invfact[n] = modular_inverse(n)*infact[n-1]%p

modular_inverse可以很容易的用Fermat's little theorem or Extended Euclidean algorithm求出来。（因为p是质数，两个都可以用）
乘以fact[n]*infact[r]*infact[n-r]%p

[=42=得到nCr ]

另一种方法：也可以用帕斯卡法计算nCr

因为，对于任何 nCr，您都可以使用

row[0]=1;
for(i=1;i<n/2;i++)
{
   row[i]=row[i-1]*(n-i+1)/i
}

for(i=n/2;i<=n;i++)
{
   row[i]=row[n-i]
}

在此你必须使用上述任何一种方式（Fermat's little theorem or Extended Euclidean algorithm）

取（i）的modulo_inverse

Calculating nCr modulo p, a prime