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

Автор qpalz, 10 лет назад, По-английски

This solution is accepted: http://mirror.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