Xor Again (XORAGN)

Chef recently discovered a function  XOR(), which computes the XOR of all elements of a sequence:

XOR(a_1..n) = a₁ ⊕ a₂ ⊕ ... ⊕ a_n

Chef has a sequence A with size n. He generated a new sequence B with size n² using the following formula:

B_in+j+1 = (A_i+1 + A_j+1) ∀ 0 ≤ i, j < n

Compute the value of XOR(B).

Input. The first line contains a single integer t (1 ≤ t ≤ 100) denoting the number of test cases. The description of t test cases follows. The first line of each test case contains a single integer n (1 ≤ n ≤ 10⁵). The second line contains n  space-separated integers a₁, a₂, …, a_n (2⁰ ≤ a_i < 2³⁰).

Output. For each test case, print a single line containing one integer – the answer to the problem.

Sample input	Sample output
1 2 1 2	6

РЕШЕНИЕ

математика

Анализ алгоритма

Изучим структуру последовательности В:

при i = 0, j = 0: B₁ = A₁ + A₁;

при i = n – 1, j = n – 1: B_n*n = A_n + A_n;

XOR(B) =

(A₁ + A₁) ⊕ (A₁ + A₂) ⊕ (A₁ + A₃) ⊕ … ⊕ (A₁ + A_n-1) ⊕ (A₁ + A_n) ⊕

(A₂ + A₁) ⊕ (A₂ + A₂) ⊕ (A₂ + A₃) ⊕ … ⊕ (A₂ + A_n-1) ⊕ (A₂ + A_n) ⊕

…

(A_n + A₁) ⊕ (A_n + A₂) ⊕ (A_n + A₃) ⊕ … ⊕ (A_n + A_n-1) ⊕ (A_n + A_n)

Очевидно, что (A_i + A_j) ⊕ (A_j + A_i) = 0. Слагаемые сократятся, останется

XOR(B) = (A₁ + A₁) ⊕ (A₂ + A₂) ⊕ (A₃ + A₃) ⊕ … ⊕ (A_n + A_n),

что вычисляется за линейное время.

Реализация алгоритма

#include <iostream>

using namespace std;

long long i, n, ai, res, tests;

int main(void)

{

cin >> tests;

while (tests--)

{

cin >> n;

res = 0;

for (i = 0; i < n; i++)

{

cin >> ai;

res = res ^ (2 * ai);

}

cout << res << endl;

}

return 0;

}