Codeforces Round 626 (Div. 1, по задачам Открытой олимпиады школьников по программированию) |
---|
Закончено |
На восьмое марта Катерине подарили массив чисел. Со временем ей стало скучно просто смотреть на него, и она решила посчитать некоторые его бесполезные характеристики. Со всеми, что она придумывала, ей это удавалось. Придумав очередную — xor попарных сумм чисел в массиве, она поняла, что не может придумать, как посчитать её для большого массива, и попросила вас помочь. А вы сможете? Более формально, вам нужно посчитать
$$$$$$ (a_1 + a_2) \oplus (a_1 + a_3) \oplus \ldots \oplus (a_1 + a_n) \\ \oplus (a_2 + a_3) \oplus \ldots \oplus (a_2 + a_n) \\ \ldots \\ \oplus (a_{n-1} + a_n) \\ $$$$$$
Запись $$$x \oplus y$$$ обозначает битовый XOR чисел (т.е. $$$x$$$ ^ $$$y$$$ для многих современных языков программирования). Об этой операции вы можете прочитать по ссылке в Wikipedia: https://tiny.cc/34xykz.
Первая строка содержит целое число $$$n$$$ ($$$2 \leq n \leq 400\,000$$$) — количество чисел в массиве.
Вторая строка содержит целые числа $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$).
Выведите одно число — xor попарных сумм чисел в данном массиве.
2 1 2
3
3 1 2 3
2
В первом примере есть всего одна сумма: $$$1 + 2 = 3$$$.
Во втором примере есть три суммы: $$$1 + 2 = 3$$$, $$$1 + 3 = 4$$$, $$$2 + 3 = 5$$$. В двоичной системе счисления это $$$011_2 \oplus 100_2 \oplus 101_2 = 010_2$$$, то есть 2.
$$$\oplus$$$ означает операцию побитового xor. Чтобы определить $$$x \oplus y$$$ рассмотрим двоичную запись чисел $$$x$$$ и $$$y$$$. Скажем, что $$$i$$$-й бит результата равен 1, если ровно один из $$$i$$$-х битов $$$x$$$ и $$$y$$$ равен 1. В противном случае $$$i$$$-й бит результата равен 0. Например, $$$0101_2 \, \oplus \, 0011_2 = 0110_2$$$.
Название |
---|