使用动态规划求解二项式系数时触发SIGFPE错误的原因咨询

触发SIGFPE的原因 #

• 核心诱因是阶乘溢出导致除零错误
  long long为64位有符号整数，最大可存储值为9223372036854775807，仅能承载到20的阶乘（20! = 2432902008176640000）。当输入的n大于20时，阶乘计算会发生signed整数溢出，C++中该行为属于未定义行为，溢出后的值大概率会出现0。此时计算分母dp[n-r] * dp[r]时如果结果溢出为0，就会触发除零错误，这是SIGFPE信号产生的直接原因。
• 额外的结果错误问题
  你在模1000000007的场景下直接使用除法不符合模运算规则，模运算中不能直接执行除法操作，需要将除法转换为乘以分母的模逆元，即便溢出问题被修复，直接做除法也会得到错误结果。
• 语法规范问题
  代码中long long dp[n+1]属于变长数组(VLA)，不属于C++标准语法，仅为部分编译器的扩展实现，不具备可移植性，建议改用vector<long long>存储阶乘结果。

修复方案 #

如果继续使用阶乘计算的思路，可以做两点修改：

1. 阶乘计算过程中边乘边取模1000000007，避免溢出
2. 除法运算替换为乘以分母的模逆元，因为1000000007是质数，可以用费马小定理快速计算逆元
   参考修复代码：

class Solution{
    const int MOD = 1000000007;
    // 快速幂计算a^b % MOD
    long long qpow(long long a, long long b) {
        long long res = 1;
        while(b) {
            if(b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b >>= 1;
        }
        return res;
    }
public:
    int nCr(int n, int r){
        if(n < r) return 0;
        vector<long long> fact(n + 1, 0);
        fact[0] = 1;
        for(int i = 1; i <= n; i++) {
            fact[i] = fact[i - 1] * i % MOD;
        }
        long long inv_den = qpow(fact[r] * fact[n - r] % MOD, MOD - 2);
        return fact[n] * inv_den % MOD;
    }
};

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