Java计算大n/k值的模1e9+7二项式系数结果错误排查

作业要求编写程序计算满足1≤k≤n≤2000的任意n、k对应的二项式系数，小n、k值计算正常，但大值时结果不准确。已尝试递归法和阶乘法，均存在溢出问题；当前代码在每次迭代中取模以减少溢出风险，但精度仍下降。

原代码 #

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main
{
    public static double bCoeffModded(double nPar, double kPar, double mPar) {
        if ((nPar == kPar) || (kPar == 0)) {
            return 1;
        }
        
        double binomialCoefficient = nPar;
        
        for (int i = 2; i <= kPar; i++) {
            binomialCoefficient *= ((nPar + 1 - i) / i);
            binomialCoefficient %= mPar;
        }
        return binomialCoefficient;
    }
    
    public static void main(String[] args) {
        // Declarations
        double n, k;
        double m = (int) Math.pow(10,9) + 7; // modulus
        int c;
        
        // Input
        Scanner reader = new Scanner(new BufferedInputStream(System.in));
        n = reader.nextInt();
        k = reader.nextInt();
        
        // Calculations
        c = (int) bCoeffModded(n, k, m);
        
        // OutPut
        System.out.println(c);
    }
}

测试用例 #

• 输入6 4，预期输出15，实际输出15
• 输入100 50，预期输出538992043，实际输出309695578

问题根源 #

1. 浮点类型精度不足：double仅能精确表示53位以内的整数，当n、k增大时，二项式系数的数值远超这个范围，即使中途取模，除法操作也会引入浮点误差，导致后续计算偏离正确值。
2. 浮点模运算不可靠：浮点数的精度丢失会让取模结果出现偏差，无法保证整数运算的正确性。

解决方案 #

利用整数类型+杨辉三角递推，全程对1e9+7取模，既避免溢出，又保证计算精度。以下是两种实现方式：

方案1：二维数组动态规划

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner reader = new Scanner(new BufferedInputStream(System.in));
        int n = reader.nextInt();
        int k = reader.nextInt();
        k = Math.min(k, n - k); // 利用组合数对称性减少计算量

        // 构建杨辉三角表
        long[][] dp = new long[n + 1][k + 1];
        // 初始化边界条件
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
            if (i <= k) {
                dp[i][i] = 1;
            }
        }

        // 递推填充表
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < Math.min(i, k + 1); j++) {
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j]) % MOD;
            }
        }

        System.out.println(dp[n][k]);
    }
}

方案2：空间优化版（一维数组）

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {
    static final int MOD = 1000000007;

    public static void main(String[] args) {
        Scanner reader = new Scanner(new BufferedInputStream(System.in));
        int n = reader.nextInt();
        int k = reader.nextInt();
        k = Math.min(k, n - k); // 优化计算量

        long[] dp = new long[k + 1];
        dp[0] = 1;

        // 从后往前更新，避免覆盖上一行数据
        for (int i = 1; i <= n; i++) {
            for (int j = Math.min(i, k); j > 0; j--) {
                dp[j] = (dp[j] + dp[j - 1]) % MOD;
            }
        }

        System.out.println(dp[k]);
    }
}

方案说明 #

• 用long存储中间结果，避免int溢出（模1e9+7后的数值远小于long的最大值）
• 杨辉三角递推公式C(n,k)=C(n-1,k-1)+C(n-1,k)是纯整数运算，无浮点误差
• 每次递推后取模，确保数值始终在可控范围内
• 利用组合数对称性C(n,k)=C(n,n-k)，将计算量减半，提升效率

内容的提问来源于stack exchange，提问作者Eragonrider