Check your for
loop in the main()
. dp[n][i]
is always less than MOD
, but this is not guaranteed for sum
. So, try changing sum += dp[n][i];
to sum = (sum + dp[n][i]) % MOD;
.
Unable to use MODULO operation correctly in C++ for SAFECRAC SPOJ?
Question
I'm trying to solve problem http://www.spoj.com/problems/SAFECRAC.
I figured that it can easily be solved using dynamic programming but since the final answer is very large we have to output the answer MODULO 1000000007. It seems that I am unable to use the MODULO operation properly since I get correct output for length = 3 but for length = 25 output differs from sample.
Here is my code:
#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;
}
}
Solution
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow