我需要高效地计算 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
不必是质数!
nPr(n,m) % k
的输入(不一定是记忆化,很可能不是)。 - PlsWorkk
外部化,因为它在递归过程中不会改变。这样做可以节省内存,因为在你的情况下,你无法利用尾递归优化。所以,每次它递归,它都会保留所有持有3个新的整数的栈帧,直到它返回。因此,有效地将k
外部化将删除约1/3的内存使用。 - CraigR8806