AT_abc365_e [ABC365E] Xor Sigma Problem

题目描述

给定一个长度为 $N$ 的整数序列 $A=(A_1,\ldots,A_N)$。请计算下式的值。

$$\sum_{i=1}^{N-1}\sum_{j=i+1}^N (A_i \oplus A_{i+1} \oplus \ldots \oplus A_j)$$

按位异或的定义如下：对于非负整数 $A, B$，$A \oplus B$ 表示 $A$ 和 $B$ 的按位异或运算。具体来说，$A \oplus B$ 的二进制表示中，第 $2^k$ 位（$k \geq 0$）的数值为 $A$ 和 $B$ 的二进制表示中第 $2^k$ 位的数值中恰好有一个为 $1$ 时为 $1$，否则为 $0$。

例如，$3 \oplus 5 = 6$（二进制表示为：$011 \oplus 101 = 110$）。 一般地，$k$ 个整数 $p_1, \dots, p_k$ 的异或和定义为 $(\cdots((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$，并且可以证明，这个结果与 $p_1, \dots, p_k$ 的顺序无关。

输入格式

输入以以下格式从标准输入读入。

$N$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3
1 3 2

输出 #1

3

输入输出样例 #2

输入 #2

7
2 5 6 5 2 1 7

输出 #2

83

说明/提示

限制条件

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i \leq 10^8$
• 输入的所有数值均为整数

样例解释 1

$A_1 \oplus A_2 = 2,\ A_1 \oplus A_2 \oplus A_3 = 0,\ A_2 \oplus A_3 = 1$，因此答案为 $2+0+1=3$。

由 ChatGPT 4.1 翻译