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

Автор LunaticPriest, история, 4 года назад, По-английски

Hello Codeforces community, I am trying to find the sum of XOR of all pairs in an array, where: n < 3*10^5 and A[i] < 2^60. My algorithm works as follows: For each bit 0 to 59, find how many 0s and 1s there are. Then add (zero_count*one_count*bit_value) to the answer, and finally, print the answer MOD 1e10+7. I know that the algorithm is correct, but I'm still getting wrong answers. In the beginning, I was getting an overflow because of the bit-shifting, but I fixed it. I am taking mods everywhere, and I can't find where the bug is. Here is the code. Thanks a lot for taking your time and helping me.

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +4 Проголосовать: не нравится

Still overflow if zc=oc=1e5 and 1<<I %mod is close to mod

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

https://atcoder.jp/contests/abc147/tasks/abc147_d

Isn't this the problem? In the future, you can just link to a problem instead of restating it (especially if it's from the same day).

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

Try to fix the mod operations.That part is giving you the wrong answer. Link

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    I really appreciate the fix!!! My last question is: what does the outside function change in the process?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Just rework this string:
sum = (sum + (zc*oc*((ll)1<<i)%MOD)%MOD)%MOD;
like this:
sum = (sum + ((zc * oc) % MOD * ((1ll << i) % MOD)) % MOD) % MOD;