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

Question

我需要计算 nCr(n,m) % k对于大 n ( n <= 10^7) 高效。

这是我的尝试:

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;
}

它计算一些组合 mod k:nCr(n,m) % k通过利用 pascals identity .

这对于大 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 的所有有效值都应为真。

希望这对您有所帮助:)

编辑

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