为何对1'000'000'007取模后仍出现int溢出？

嘿，这个问题我刷LeetCode的时候也踩过一模一样的坑！咱们来一步步拆解清楚原因：

问题根源：32位int的范围限制 #

你用的int类型在绝大多数系统里是32位的，它的最大值是2^31 - 1 = 2147483647。虽然你给每个单独的dp值都做了% MOD（MOD=1e9+7），保证了单个值不会超过1e9+6，但多个这样的值相加时，总和很容易突破int的上限。

比如错误日志里的1543295930 + 918080153 = 2461376083，这个数已经比2147483647大了，直接用int相加就会触发有符号整数溢出，属于C++里的未定义行为。

看你代码里出问题的这行：

dp2[1][0] = (dp2[1][0]+dp[1][0]+dp[1][1]+dp[1][2])%MOD;

这里dp2[1][0]已经是一个接近1e9的数，再加上另外三个接近1e9的数，总和最多能达到4*(1e9+6) = 4000000024，这远远超过了32位int的最大值，溢出是必然的。

解决办法：用64位整数做中间计算 #

把你的dp和dp2数组的类型从int改成long long，这样中间相加的时候就能用64位整数存储总和，避免溢出。64位long long的最大值是9e18，完全能容纳几个1e9级别的数相加。

修改后的代码示例：

class Solution {
public:
    static constexpr int MOD = 1'000'000'007;
    int checkRecord(int n) {
        long long dp[2][3]; // 改为long long类型
        long long dp2[2][3]; // 改为long long类型
        memset(dp, 0, sizeof(dp));
        memset(dp2,0,sizeof(dp2));
        dp[0][0] = 1;
        for(int i=1;i<n+1;i++){
            dp2[0][1] = dp[0][0]%MOD;
            dp2[1][1] = dp[1][0]%MOD;
            dp2[0][2] = dp[0][1]%MOD;
            dp2[1][2] = dp[1][1]%MOD;
            dp2[1][0] = (dp[0][0]+dp[0][1]+dp[0][2])%MOD;
            // 现在用long long相加，不会触发溢出
            dp2[1][0] = (dp2[1][0]+dp[1][0]+dp[1][1]+dp[1][2])%MOD;
            dp2[0][0] = (dp[0][0]+dp[0][1]+dp[0][2])%MOD;
            memcpy(dp, dp2, sizeof(dp));
        }
        int sum = 0;
        for (int j = 0; j <= 1; j++) {
            for (int k = 0; k <= 2; k++) {
                sum = (sum + dp[j][k]) % MOD;
            }
        }
        return sum;
    }
};

这样修改后，所有中间相加的操作都在long long的安全范围内进行，取模后再存储，就不会出现溢出问题了。

内容的提问来源于stack exchange，提问作者周宁音