c - 高效计算 nCk mod p

Question

这个问题我已经遇到过很多次了，但是一直无法解决。在某些情况下会出现错误的答案，或者我编写的程序会太慢。正式地说，我正在谈论计算

nCk mod p 其中 p 是质数 n 是一个大数，且 1<=k<=n。

我尝试过什么:

我知道阶乘的递归公式，然后将其建模为动态规划问题，但我觉得它很慢。递归公式为(nCk) + (nCk-1) = (n+1Ck)。我在将值存储在数组中以避免溢出时处理了模数，但我不确定仅对结果执行 mod p 是否会避免所有溢出，因为可能需要删除。

Answer 1

要计算 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在罗塞塔代码上