高效计算大数n的组合数nCr(n,m)对k取模的值

Question

3

我需要高效地计算 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;
}

它利用帕斯卡恒等式计算模k的一些组合数量：nCr(n,m) % k。

对于较大的n，这太低效了（尝试choose(100, 12, 223092870)），我不确定是否可以通过记忆化来加速，或者是否需要一些完全不同的数论方法。

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

注意：k不必是质数！

- PlsWork

你不是几分钟前刚发布了这个完全相同的问题吗？ - Kon

之前的问题不够准确，明确要求使用记忆化技术，而这并不是本例的情况。相反，我正在寻求解决更一般的问题，即高效地计算 nPr(n,m) % k 的输入（不一定是记忆化，很可能不是）。 - PlsWork

有一件事可能会在内存使用方面节省一些空间，那就是将k外部化，因为它在递归过程中不会改变。这样做可以节省内存，因为在你的情况下，你无法利用尾递归优化。所以，每次它递归，它都会保留所有持有3个新的整数的栈帧，直到它返回。因此，有效地将k外部化将删除约1/3的内存使用。 - CraigR8806

@CraigR8806 好观点，不过我更关心运行时间。 - PlsWork

运行时可能会受到内存使用的影响。如果堆栈帧不断增加，它会拖慢系统。 - CraigR8806

1

http://fishi.devtail.io/weblog/2015/06/25/computing-large-binomial-coefficients-modulo-prime-non-prime/ - DAle

2个回答

0

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

- PlsWork

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Simon Sirak · Accepted Answer

由于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）之后计算模数，以避免冗余的模数操作。

如果有帮助，您可以尝试制定一个循环不变量，这基本上是一个对于所有有效值n和m都应为真的语句。

希望这有所帮助：）

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