LunaticPriest's blog

Sum of XOR of All Pairs in an Array
By LunaticPriest, history, 5 years ago, In English

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.

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

Comments Comments (5)
| Write comment?
»
5 years ago, # |
← Rev. 4   Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

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).

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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;

→ Reply