qpalz's blog

479E — mod the partial sum or not?
By qpalz, 10 years ago, In English

This solution is accepted: http://codeforces.com/contest/479/submission/8546349

However, if I change line 29 from

ps[j] = ps[j - 1] + dp[pidx][j];

to

ps[j] = (ps[j - 1] + dp[pidx][j]) % MOD;

The outputs of test 6 and many other test cases of my program are wrong. I have two questions:

  1. I think that the two versions are mathematically equivelent, aren't they?
  2. Why overflow error does not happen for the first version? Unsigned long long is really large enough?

Thanks for your help.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If you write ps[j] = (ps[j — 1] + dp[pidx][j]) % MOD;

some of ps[j] can be less than ps[i], when j > i.

So, if you add ps[j] — ps[i] to your dp[][], it can be less than 0.

If you will write ps[j] = (ps[j — 1] + dp[pidx][j] + mod) % MOD; instead of ps[j] = (ps[j — 1] + dp[pidx][j]) % MOD, it must be right.

Unsigned long long can keep number < 2^64. All cell of your dp[][] less 10^9+7, so, max ps[] = 5000 * (10^9 + 6) < 2^64

→ Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    I previously did not understand why some people write ps[j] = (ps[j — 1] + dp[pidx][j] + MOD) % MOD when I read others code, but I understand it now. Thanks a lot for your explanation.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      You don't need add MOD here (it's sum), only when you write (x — y) % mod:

      (x + y + MOD) % MOD == (x + y) % MOD;

      (x — y) % MOD == (x — y + MOD) % MOD, when x > y

      (x — y) % MOD != (x — y + MOD) % MOD, when x < y

      → Reply