emalgorithm's blog

By emalgorithm, 9 years ago, In English

I have found the correct solution for this problem(407B - Long Path), but I'm having problems with the modulo. It's behaving strangely: it gives me negative value. Do you have a guess of why that? Here's my code and my submission(10170884).

#include <stdio.h>
#include <math.h>
#include <iostream>
#include <string.h>


#define INF 1000000005
#define MAX_N 3000005
#define MOD int(1e9)+7

using namespace std;

long long memo[MAX_N], p[MAX_N], n;

int main(){
    ios_base::sync_with_stdio(false);

    cin>>n;

    for(int i=0;i<n;i++){
        cin>>p[i];
        p[i]--;
    }

    for(int i=1;i<=n;i++){
        memo[i] = 2*memo[i-1] - memo[p[i-1]] + 2;
        memo[i] %= MOD;
    }
    cout<<memo[n];
    return 0;
}
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Because you have subtraction by modulo.
Add this after taking by modulo:

if (memo[i] < 0)  
  memo[i] += MOD;

You should add this because (a - b) % mod = (a % mod - b % mod + mod) % mod;

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, right. Thanks !

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I faced the same problem with this problem and got AC by adding this line. I chose to ignore the problem but now I am glad I stumbled upon this post.

    bool isAwesome = true