子段异或

题目描述

给定一个长度为 $n$ 的数列 $a_1, a_2, \cdots, a_n$，计算这个序列所有连续子序列的和的异或值，也就是计算

$$\bigoplus_{1 \le i \le j \le n} \{ a_i + a_{i+1} + \cdots + a_j \}$$

其中 $\oplus$ 表示异或运算。例如对于数列 $20, 10, 35$，有六个子序列，它们的和分别是：$20, 10, 35, 30, 45, 65$，它们的异或和为 $79$。

输入格式

第一行：单个整数 $n$； 第二行：$n$ 个整数表示 $a_1, a_2, \cdots, a_n$。

输出格式

单个整数：所有连续子序列的和的异或值。

数据范围

$0 \le a_i$；$a_1 + a_2 + \cdots + a_n \le 1{,}000{,}000$； 对于 30% 的数据，$1 \le n \le 10^3$； 对于 60% 的数据，$1 \le n \le 10^4$； 对于 100% 的数据，$1 \le n \le 10^5$。

样例输入

3
20 10 35

样例输出

79

知识点与难度

本题涉及的知识点从属于 GESP五级（前缀和、位运算），难度等级：⭐⭐⭐。

---

测试点分布

Subtask	分值	测试点编号	说明
0	10	1~2	样例
1	20	3~8	小规模
2	15	9~11	Hack
3	30	12~20	中大规模
4	25	21~25	随机回归