c++ - 无法在 C++ 中为 SAFECRAC SPOJ 正确使用 MODULO 运算？

Question

我正在尝试解决问题 http://www.spoj.com/problems/SAFECRAC .

我认为使用动态规划可以很容易地解决这个问题，但由于最终答案非常大，我们必须输出答案 MODULO 1000000007。似乎我无法正确使用 MODULO 运算，因为我得到了正确的长度输出= 3 但对于长度 = 25，输出与样本不同。

这是我的代码:

#include <iostream>

using namespace std;

#define MOD 1000000007
typedef long long int ll;

ll dp[100001][10];

int t, n;       

void precompute()
{
    for (int j = 0; j < 10; j++)
        dp[1][j] = 1;

    for (int i = 2; i <= 100000; i++) {
        for (int j = 0; j < 10; j++) {
            if (j == 0) dp[i][j] = dp[i-1][7] % MOD;
            if (j == 1) dp[i][j] = ( dp[i-1][2] + dp[i-1][4] ) % MOD;
            if (j == 2) dp[i][j] = ( dp[i-1][1] + ( dp[i-1][3] + dp[i-1][5] ) % MOD ) % MOD;
            if (j == 3) dp[i][j] = ( dp[i-1][2] + dp[i-1][6] ) % MOD;
            if (j == 4) dp[i][j] = ( dp[i-1][1] + ( dp[i-1][5] + dp[i-1][7] ) % MOD ) % MOD;
            if (j == 5) dp[i][j] = ( ( dp[i-1][2] + dp[i-1][4] ) % MOD + ( dp[i-1][6] + dp[i-1][8] ) % MOD ) % MOD;
            if (j == 6) dp[i][j] = ( dp[i-1][3] + ( dp[i-1][5] + dp[i-1][9] ) % MOD ) % MOD;
            if (j == 7) dp[i][j] = ( dp[i-1][4] + ( dp[i-1][8] + dp[i-1][0] ) % MOD ) % MOD;
            if (j == 8) dp[i][j] = ( dp[i-1][5] + ( dp[i-1][7] + dp[i-1][9] ) % MOD ) % MOD;
            if (j == 9) dp[i][j] = ( dp[i-1][6] + dp[i-1][8] ) % MOD;
        }
    }
}

int main()
{
    precompute();

    cin >> t;

    while (t--) {
        cin >> n;

        ll sum = 0;

        for (int i = 0; i < 10; i++) {
            sum += dp[n][i];
        }

        cout << sum << endl;
    }
}

Answer 1

检查 main() 中的 for 循环。 dp[n][i] 始终小于 MOD，但 sum 不能保证这一点。因此，尝试将 sum += dp[n][i]; 更改为 sum = (sum + dp[n][i]) % MOD;。