java - 使用 modInverse 计算大数的 C(n, k) 组合

Question

我想计算组合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));

    }

}

Answer 1

线条

    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();

您可能会考虑缓存逆阶乘以及阶乘。