Задача №114742. Подарок
На восьмое марта Катерине подарили массив чисел. Со временем ей стало скучно просто смотреть на него, и она решила посчитать некоторые его бесполезные характеристики. Со всеми, что она придумывала, ей это удавалось. Придумав очередную — 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) \oplus (a_{n-1} + a_n)\)
Первая строка содержит целое число \(n\) (\(2 \leq n \leq 400\,000\)) — количество чисел в массиве.
Вторая строка содержит целые числа \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^7\)).
Выведите одно число — xor попарных сумм чисел в данном массиве.
В первом примере есть всего одна сумма: \(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\).
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | |||||
| Группа | Баллы | \(n\) | \(a_i\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 34 | \(n \le 1000\) | – | 0 | |
| 2 | 37 | – | \(1 \le a_i \le 100\) | 0 | |
| 3 | 29 | – | – | 0, 1, 2 | |
2 1 2
3
3 1 2 3
2