我需要计算 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
不一定是素数!
最佳答案
由于 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) 算法,该算法非常可扩展。它使用的内存也非常少。
关于java - 有效计算大 n 的 nCr(n,m) mod k,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44830285/