Present (Codeforces 1323D)
Tags: Math, bitmasks

Catherine received an array of integers as a gift for March 8. Eventually she grew bored with it, and she started calculated various useless characteristics for it. She succeeded to do it for each one she came up with. But when she came up with another one — xor of all pairwise sums of elements in the array, she realized that she couldn't compute it for a very large array, thus she asked for your help. Can you do it? Formally, you need to compute$$$$$$ (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) \\ $$$$$$Here $$$x \oplus y$$$ is a bitwise XOR operation (i.e. $$$x$$$ ^ $$$y$$$ in many modern programming languages). You can read about it in Wikipedia: https://en.wikipedia.org/wiki/Exclusive_or#Bitwise_operation.

Input: The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 400\,000$$$) — the number of integers in the array.The second line contains integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^7$$$).

Output: Print a single integer — xor of all pairwise sums of integers in the given array.

Note: In the first sample case there is only one sum $$$1 + 2 = 3$$$.In the second sample case there are three sums: $$$1 + 2 = 3$$$, $$$1 + 3 = 4$$$, $$$2 + 3 = 5$$$. In binary they are represented as $$$011_2 \oplus 100_2 \oplus 101_2 = 010_2$$$, thus the answer is 2.$$$\oplus$$$ is the bitwise xor operation. To define $$$x \oplus y$$$, consider binary representations of integers $$$x$$$ and $$$y$$$. We put the $$$i$$$-th bit of the result to be 1 when exactly one of the $$$i$$$-th bits of $$$x$$$ and $$$y$$$ is 1. Otherwise, the $$$i$$$-th bit of the result is put to be 0. For example, $$$0101_2 \, \oplus \, 0011_2 = 0110_2$$$.

Sample Inputs:
2
1 2

3
1 2 3

Sample Outputs:
3

2

Solution (Python):
import sys
from array import array
from typing import List, Tuple, TypeVar, Generic, Sequence, Union

def input():
    return sys.stdin.buffer.readline().decode('utf-8')

def main():
    n = int(input())
    a = sorted(map(int, input().split()))
    ans = 0
    for d in range(25, -1, -1):
        bit = 1 << d
        cnt = 0
        j = k = l = n - 1
        for (i, x) in enumerate(a):
            (j, k, l) = (max(j, i), max(k, i), max(l, i))
            while i < j and a[j] >= bit - x:
                j -= 1
            while j < k and a[k] >= 2 * bit - x:
                k -= 1
            while k < l and a[l] >= 3 * bit - x:
                l -= 1
            cnt += k - j + n - 1 - l
        if cnt & 1:
            ans += bit
        for i in range(n):
            a[i] &= ~bit
        a.sort()
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import io
import os
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
DEBUG = False

def solveBrute(N, A):
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            ans ^= A[i] + A[j]
    return ans

def solve(N, A):
    B = max(A).bit_length()
    ans = 0
    for k in range(B + 1):
        MOD = 1 << k + 1
        MASK = MOD - 1
        i = 0
        right = []
        for x in A:
            if x >> k & 1:
                right.append(x)
            else:
                A[i] = x
                i += 1
        assert N - i == len(right)
        A[i:] = right
        arr = [x & MASK for x in A]
        if DEBUG:
            assert arr == sorted(arr)
        numPairs = 0
        tlo = 1 << k
        thi = (1 << k + 1) - 1
        for (targetLo, targetHi) in [(tlo, thi), (MOD + tlo, MOD + thi)]:
            lo = N
            hi = N
            for (i, x) in enumerate(arr):
                lo = max(lo, i + 1)
                hi = max(hi, lo)
                while lo - 1 >= i + 1 and arr[lo - 1] >= targetLo - x:
                    lo -= 1
                while hi - 1 >= lo and arr[hi - 1] >= targetHi - x + 1:
                    hi -= 1
                numPairs += hi - lo
                if DEBUG:
                    assert lo == bisect_left(arr, targetLo - x, i + 1)
                    assert hi == bisect_right(arr, targetHi - x, lo)
                    for (j, y) in enumerate(arr):
                        cond = i < j and targetLo <= x + y <= targetHi
                        if lo <= j < hi:
                            assert cond
                        else:
                            assert not cond
        ans += numPairs % 2 << k
    return ans
if DEBUG:
    import random
    random.seed(0)
    for i in range(100):
        A = [random.randint(1, 1000) for i in range(100)]
        N = len(A)
        ans1 = solveBrute(N, A)
        ans2 = solve(N, A)
        print(A, bin(ans1), bin(ans2))
        assert ans1 == ans2
elif False:
    import random
    random.seed(0)
    A = [random.randint(1, 10 ** 7) for i in range(400000)]
    N = len(A)
    print(solve(N, A))
if __name__ == '__main__':
    (N,) = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)

Solution (Python):
import io
import os
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
DEBUG = False

def solveBrute(N, A):
    ans = 0
    for i in range(N):
        for j in range(i + 1, N):
            ans ^= A[i] + A[j]
    return ans

def solve(N, A):
    B = max(A).bit_length()
    ans = 0
    for k in range(B + 1):
        MOD = 1 << k + 1
        MASK = MOD - 1
        left = []
        right = []
        for x in A:
            if x >> k & 1:
                right.append(x)
            else:
                left.append(x)
        A = left + right
        arr = [x & MASK for x in A]
        if DEBUG:
            assert arr == sorted(arr)
        numPairs = 0
        tLo = 1 << k
        tHi = (1 << k + 1) - 1
        for (targetLo, targetHi) in [(tLo, tHi), (MOD + tLo, MOD + tHi)]:
            lo = N
            hi = N
            for (i, x) in enumerate(arr):
                lo = max(lo, i + 1)
                hi = max(hi, lo)
                while lo - 1 >= i + 1 and arr[lo - 1] >= targetLo - x:
                    lo -= 1
                while hi - 1 >= lo and arr[hi - 1] > targetHi - x:
                    hi -= 1
                numPairs += hi - lo
                if DEBUG:
                    assert lo == bisect_left(arr, targetLo - x, i + 1)
                    assert hi == bisect_right(arr, targetHi - x, lo)
                    for (j, y) in enumerate(arr):
                        cond = i < j and targetLo <= x + y <= targetHi
                        if lo <= j < hi:
                            assert cond
                        else:
                            assert not cond
        ans += numPairs % 2 << k
    return ans
if DEBUG:
    import random
    random.seed(0)
    for i in range(100):
        A = [random.randint(1, 1000) for i in range(100)]
        N = len(A)
        ans1 = solveBrute(N, A)
        ans2 = solve(N, A)
        print(A, bin(ans1), bin(ans2))
        assert ans1 == ans2
elif False:
    import random
    random.seed(0)
    A = [random.randint(1, 10 ** 7) for i in range(400000)]
    N = len(A)
    print(solve(N, A))
if __name__ == '__main__':
    (N,) = list(map(int, input().split()))
    A = list(map(int, input().split()))
    ans = solve(N, A)
    print(ans)