無法在SAFECRAC SPOJ的C++中正確使用MODULO操作？

我正試圖解決問題http://www.spoj.com/problems/SAFECRAC。無法在SAFECRAC SPOJ的C++中正確使用MODULO操作？

我覺得它可以很容易地使用動態編程來解決，但由於最終答案非常大，我們必須輸出答案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; 
    } 
}

來源

2013-06-28 khirod

'while（t - ）'??? t--不是一個條件，它總是會評估爲真，並繼續下降。 – 0decimal0

@PHIfounder，不，因爲'--'是在變量之後，它會在減少T之前評估T的值。一旦T爲0，循環退出。 http://ideone.com/8gjBhF –

@DavidFreitag哦，聖，我怎麼錯過了？ – 0decimal0

檢查for循環中main()。 dp[n][i]始終小於MOD，但這不能保證sum。因此，請嘗試更改至sum = (sum + dp[n][i]) % MOD;。

來源

2013-06-28 17:33:13

非常感謝。得到AC :) – khirod

@khirod歡迎:) –

無法在SAFECRAC SPOJ的C++中正確使用MODULO操作？

回答

相關問題