- Thoughts.
- Do not calculate in square orders.
- Exactly half of the entire queue Half of the queue.
- I wonder if the XOR and the order of the sums could be interchanged…
- It would be difficult to add all the digits, but I guess it could be done bit by bit.
- OK, the following holds for the 0/1 column
- XOR and Sum Exchange
- In other words, you can count the number of 1’s for each digit of all the numbers in advance, and find the sum by inverting the above formula only where the 1 in Ai stands, which is fast enough since the number of digits is 60.
- Since what we have obtained here is the whole matrix, we can halve it to get the answer
- Official Explanation
- The above is sufficient, but the official explanation does a similar conversion further
- Since the value we want is half of this .
This page is auto-translated from /nishio/ABC147D using DeepL. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I’m very happy to spread my thought to non-Japanese readers.