这个问题我已经遇到过很多次了，但是一直无法解决。在某些情况下会出现错误的答案，或者我编写的程序会太慢。正式地说，我正在谈论计算
nCk mod p 其中 p 是质数 n 是一个大数，且 1<=k<=n。
我尝试过什么:
我知道阶乘的递归公式，然后将其建模为动态规划问题，但我觉得它很慢。递归公式为(nCk) + (nCk-1) = (n+1Ck)。我在将值存储在数组中以避免溢出时处理了模数，但我不确定仅对结果执行 mod p 是否会避免所有溢出，因为可能需要删除。
最佳答案
要计算 nCr，有一个基于规则 nCr = (n - 1)C(r - 1) * n/r 的简单算法:
def nCr(n,r):
if r == 0:
return 1
return n * nCr(n - 1, r - 1) // r
现在，在模算术中，我们不完全有除法，但我们有模逆(当用素数进行模运算时)同样好
def nCrModP(n, r, p):
if r == 0:
return 1
return n * nCrModP(n - 1, r - 1) * modinv(r, p) % p
这是一个implementation of modinv在罗塞塔代码上
关于c - 高效计算 nCk mod p，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13780137/