P11651 [COCI 2024/2025 #4] Xor

题目背景

译自 COCI 2024/2025 #4 T3。$\texttt{1s,0.5G}$。满分为 $90$。

题目描述

给定长度为 $n$ 的非负整数序列 $a_1,a_2,\ldots,a_n$，求出 $\displaystyle \bigoplus _{1\le i\le j\le n} \left(a_i+a_j\right)$。

这里，$\oplus$ 指按位异或运算。

输入格式

第一行，一个正整数 $n$。

第二行，$n$ 个非负整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

3
2 4 5

输出 #1

14

输入输出样例 #2

输入 #2

4
6 7 3 1

输出 #2

3

输入输出样例 #3

输入 #3

7
2 3 5 7 9 11 13

输出 #3

6

说明/提示

对于 $100\%$ 的数据，保证：

• $1\le n\le 5\times 10^5$；
• $0\le a_i\lt 2^{30}$。

子任务编号	$n\le$	$a_i\lt$	得分
$1$	$2\times 10^3$	$2^{30}$	$7$
$2$	$5\times 10^5$	$2^{10}$	$17$
$3$	$10^5$	$2^{30}$	$45$
$4$	$5\times 10^5$		$21$

#5720. 「COCI 2024/2025 #4」Xor

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #4 T3「Xor」

Fran 最近学习了异或（xor）运算。对于两个整数 $x$ 和 $y$，异或运算会返回按位异或的结果。异或运算记作 $\oplus$，它通过比较 $x$ 和 $y$ 对应的二进制位，并根据以下规则确定结果中的每一位：

• 若对应位置的二进制位不同（$0$ 和 $1$，或 $1$ 和 $0$），则该位的结果为 $1$。
• 若对应位置的二进制位相同（$0$ 和 $0$，或 $1$ 和 $1$），则该位的结果为 $0$。

例如，对于 $x=5$ 和 $y=3$，其二进制表示分别为 $x=101_{2}$，$y=011_{2}$。对相应位应用异或运算可得 $x \oplus y=101_{2} \oplus 011_{2}=110_{2}=6$。换言之，$5 \oplus 3=6$。

Fran 得到了一个由 $n$ 个整数组成的数组 $a_{1}, a_{2}, \ldots, a_{n}$，并决定进行以下操作：

1. 对于满足 $1 \leq i \leq j \leq n$ 的每一对编号 $(i, j)$，计算它们的和 $a_{i}+a_{j}$。
2. 现在，他想要计算所有得到的这些和的异或结果。

请帮 Fran 计算出最终的运算结果。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 5 \cdot 10^{5})$，代表数组的长度。

第二行包含 $n$ 个数字 $a_{1}, a_{2}, \ldots, a_{n}$ $(0 \leq a_{i}<2^{30})$，含义如题面所述。

输出格式

在一行中输出所需的结果。

样例 1

输入

3
2 4 5

输出

14

这些和分别为 $2+2=4$，$2+4=6$，$2+5=7$，$4+4=8$，$4+5=9$ 以及 $5+5=10$。最终结果为 $4 \oplus 6 \oplus 7 \oplus 8 \oplus 9 \oplus 10=14$。

样例 2

输入

4
6 7 3 1

输出

3

样例 3

输入

7
2 3 5 7 9 11 13

输出

6

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$7$	$n \leq 2000$
$2$	$17$	对于所有的 $i$，满足 $a_{i}<2^{10}$
$3$	$45$	$n \leq 10^{5}$
$4$	$21$	无附加限制