我想计算组合C(n, k)，其中n和k可能非常大。我尝试通过使用模块化逆来做到这一点，如下所示，但即使对于小数字，它也不会给出正确的输出。谁能告诉我哪里错了？
import java.math.BigInteger;
public class Test {
public static int[] factorials = new int[100001];
public static int mod = 1000000007;
public static BigInteger MOD = BigInteger.valueOf(1000000007);
public static void calculateFactorials() {
long f = 1;
for (int i = 1; i < factorials.length; i++) {
f = (f * i) % mod;
factorials[i] = (int) f;
}
}
// Choose(n, k) = n! / (k! * (n-k)!)
public static long nCk(int n, int k) {
if (n < k) {
return 0;
}
long a = BigInteger.valueOf(k).modInverse(MOD).longValue();
long b = BigInteger.valueOf(n - k).modInverse(MOD).longValue();
// Left to right associativity between * and %
return factorials[n] * a % mod * b % mod;
}
public static void main(String[] args) {
calculateFactorials();
System.out.println(nCk(5, 2));
}
}
最佳答案
线条
long a = BigInteger.valueOf(k).modInverse(MOD).longValue();
long b = BigInteger.valueOf(n - k).modInverse(MOD).longValue();
应该是
long a = BigInteger.valueOf(factorials[k]).modInverse(MOD).longValue();
long b = BigInteger.valueOf(factorials[n - k]).modInverse(MOD).longValue();
您可以考虑缓存逆阶乘和阶乘。
关于java - 使用 modInverse 计算大数的 C(n, k) 组合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25356014/