Recently I am working on leetcode，here is one of question： enter link description here

And I worte code below：

class Solution {
public:
static constexpr int MOD = 1'000'000'007;
    int checkRecord(int n) {
        int dp[2][3];
        int dp2[2][3];
        memset(dp, 0, sizeof(dp));
        memset(dp2,0,sizeof(dp2));
        for (int j = 0; j <= 1; j  ) {
            for (int k = 0; k <= 2; k  ) {
                cout<<dp2[j][k]<<endl;
            }
        }
        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;
            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;
    }
};

One of case is "n = 10101".As far as I concened,after modding 1'000'000'007,one interger can not get integer overflow.But still overflow happens,here is the error.

Line 16: Char 51: runtime error: signed integer overflow: 1543295930   918080153 cannot be represented in type 'int' (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:25:51

This happens in:

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

So shouldn't equal happens after mod?Why does int overflow happens?

Thanks for reading,I know my English sucks.I would appriciate if there is any answer.

CodePudding user response：

Int is a 32-bit variable type so can take integers between approximately -2^32 and 2^32 which is arround 2,000,000,000.

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

Here you add up three integers, each can be up to 1,000,000,006, and the do % on them. So you have an int with value about 3,000,000,000 which int can not handle.

CodePudding user response：

In C , int range from -2147483648 to 2147483647 (-2^31 -> 2^31 - 1). In your line of code:

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

The dp2[1][0] dp[1][0] dp[1][1] dp[1][2] part is evaluated first, and since the MOD is 1e9 7, it can sum up to ~3e9 in the worst case and overflowing. To fix it, just do it one at a time:

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

More reading : https://www.tutorialspoint.com/cplusplus/cpp_data_types.htm