P3760 [TJOI2017] XOR Sum

Xiao Ming from Garidon High School has recently fallen in love with math contests. Many problems are related to the sums of contiguous segments of a sequence. For a sequence, computing all of its contiguous sums (i.e., subarray sums) is very easy for Xiao Ming. But today he encountered a tougher problem: not only do you need to quickly obtain all subarray sums, you also need to quickly compute the XOR of these sums. Xiao Ming has already computed all subarray sums. However, without telling you these sums, he challenges you to quickly compute the XOR of all subarray sums of the sequence.

The first line contains an integer $n$, indicating the length of the sequence. The second line contains $n$ non-negative integers $a_1, a_2 \dots a_n$ representing the sequence.

Output the XOR of all subarray sums of the sequence.

Sample Explanation: The sequence [1, 2, 3] has 6 subarray sums: 1, 2, 3, 3, 5, 6, and $1 \text{ xor } 2 \text{ xor } 3 \text{ xor } 3 \text{ xor } 5 \text{ xor } 6 = 0$. Constraints: - For $20\%$ of the testdata, $1 \le n \le 100$. - For $100\%$ of the testdata, $1 \le n \le 10^5$, $\sum a_i \le 10^6$. Translated by ChatGPT 5