Невозможно правильно использовать операцию MODULO в C++ для SAFECRAC SPOJ?

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

Проверьте for петлю в main(). dp[n][i] всегда меньше MOD, но это не гарантируется для sum. Итак, попробуйте изменить sum += dp[n][i]; на sum = (sum + dp[n][i]) % MOD;.