c - 有效计算 nCk mod p

Question

我多次遇到这个问题，但我无法解决它。会发生一些情况或其他情况会错误答案，否则我编写的程序会太慢。正式地说，我在谈论计算

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

我尝试了什么：

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

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

这是rosettacode上modinv的一种实现

Answer 2

首先，让我们处理 p 相对较小的情况。取 n 和 k 的基数展开式：写 n = n_0 + n_1 p + n_2 p^2 + ... + n_m p^m 和 k = k_0 + k_1 p + ... + k_m p^m 其中每个n_i 且每个 k_i 至少为 0 但小于 p。一个定理（我认为这是由于 Edouard Lucas）指出 C(n,k) = C(n_0, k_0) * C(n_1, k_1) * ... * C(n_m, k_m)。这简化为在下面的“n 相对较小”的情况下取数字的 mod-p 乘积。

其次，如果 n 相对较小，您可以使用公式 C(n,k) = C(n-1,k-1) + C(n-1,k) 的动态规划计算二项式系数，减少 mod p在每一步。或者做一些更聪明的事情。

第三，如果 k 相对较小（并且小于 p），您应该能够通过计算 n!/(nk)! 来计算 n!/(k!(nk)!) mod p！作为 n * (n-1) * ... * (n-k+1)，在每个乘积后减少模 p，然后乘以 1 和 k 之间每个数字的模逆。

Answer 3

不确定“将值存储在数组中”是什么意思，但我假设它们数组在运行时用作查找表，以避免冗余计算以加快速度。这应该解决速度问题。关于溢出-您可以在计算的任何阶段执行模运算并根据需要重复它-结果将是正确的。