有效计算大 n 的 nCr(n,m) mod k

Question

我需要为大 n（n <= 10^7) 有效地计算 nCr(n,m) % k。

这是我的尝试：

int choose(int n, int m, int k) {
  if (n==m || m==0)
    return 1 % k;

  return (choose(n-1, m-1, k) + choose(n-1, m , k)) % k;
}

它通过利用 pascals identity.

来计算一些组合 mod k: nCr(n,m) % k

这对于大型 n（尝试 choose(100, 12, 223092870)）而言效率太低，我不确定是否可以通过 memoization 或一些完全不同的数论方法来加快速度是必要的。

我需要立即对大量数据高效执行，这就是为什么我不确定记忆是否是解决方案的原因。

注意：k不一定是素数！

Answer 1

因为 nPr 有一个明确的公式 nPr(n, m) = n!/((n-m)!) 你绝对应该尝试使用它。我的建议是：

记住n！ = n*(n-1)*...*2*1
注意 while 循环（是的，循环，不是递归 ^^）可以极大地优化计算（除法抵消了很多因素，留下乘法 nPr(n, m) = n*(n-1)*...*(n-m+2)*(n-m+1))

最后，你应该在计算nPr(n, m)之后计算模数，以避免冗余的模数运算。

如果有帮助，您可以尝试制定一个 loop invariant，这几乎是一个对 n 和 m.[=17 的所有有效值都应该成立的陈述=]
希望这对您有所帮助:)

编辑

我写完答案后才发现你说的是nCr。对于 nCr，您可以在计算 nPr 之后添加另一个 while 循环，它只计算 m!，将 nPr 除以 m!，然后取模那个答案。总而言之，这将产生一个 O(n) 算法，该算法非常可扩展。它使用的内存也很少。

Answer 2

这在编程竞赛中时常出现，解决这个问题的一种常见方法是使用卢卡斯和中国剩余定理。

@DAle 发布了一个有用的资源，其中包含详细信息：http://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/

有效计算大 n 的 nCr(n,m) mod k

Calculate nCr(n,m) mod k for large n efficiently

java

performance

dynamic-programming

number-theory

编辑