Блог пользователя qpalz

479E — mod the partial sum or not?
Автор qpalz, 10 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      10 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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

      → Ответить