分数: 700 点
问题陈述
(在此问题陈述中,所有序列均由非负整数组成。)
有一块黑板,上面写着序列。最初,黑板只有一个长度——N 序列 A=(A_1,A_2,\dots,A_N).
我们重复以下操作,直到黑板上的所有序列都达到长度 1:
- 在黑板上的序列中,选择一个长度至少为 2,并将其从黑板上删除。令所选序列为 B=(B_1,B_2,\dots,B_n)。然后,选择一个整数 k 满意 1 \leq k < n,并定义 X = B_1 \oplus B_2 \oplus \dots \oplus B_k 和 Y=B_{k+1} \oplus B_{k+2} \oplus \dots \oplus B_n。最后写两个序列 黑板上的 (B_1 \oplus Y, B_2 \oplus Y,\dots,B_k \oplus Y) 和 (B_{k+1} \oplus X,\ B_{k+2} \oplus X,\dots,B_n \oplus X) 。
在这里, \oplus 表示按位 \mathrm{XOR} 操作。
经过这一系列的操作,让 (C_1),(C_2),\dots,(C_N) 是 分别是 N 长度序列 黑板上的 1 。找到最小可能值 \sum_{i=1}^{N} C_i.
按位注释 \mathrm{XOR} 操作
对于两个非负整数 A, B,按位 \mathrm{XOR} 操作 A \oplus B 定义如下。
- 当 A \oplus B 以二进制形式写入,对于每个 2^k 地点(k \geq 0),当且仅当恰好是该位中的一位时,该位为 1 2^k 地点 A 和 B (二进制)为 1,否则为 0。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1 \oplus p_2) \oplus p_3) \oplus \dots \oplus p_k),可以证明这个值不依赖于 p_1, p_2, \dots, p_k.
约束
- 1 \leq N \leq 500
- 0 \leq A_i < 2^{40}
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \dots A_N
输出
打印答案。
示例输入 1
4 1 3 4 5
示例输出 1
6
最初,黑板上有 上面写着 (1,3,4,5) 。从这里开始,我们按以下步骤执行操作。
- 删除 (1,3,4,5) 从黑板开始并设置 k=2。然后, X=1 \oplus 3=2 和 Y=4 \oplus 5=1,以及两个新序列 黑板上写着 (1 \oplus 1, 3 \oplus 1)=(0,2) 和 (4 \oplus 2, 5 \oplus 2)=(6,7) 。
- 删除 (0,2) 从黑板开始并设置 k=1。两个新序列 (2),(2) 。
- 删除 (6,7) 从黑板开始并设置 k=1。两个新序列 (1),(1) 。
经过这些步骤,黑板上的四个序列是 (2),(2),(1),(1),每个长度 1。他们的总和是 2+2+1+1=6.
示例输入 2
7 1 5 14 23 20 18 20
示例输出 2
39
示例输入 3
20 246260893965 450834729933 1091503137264 661761201979 238822689279 375606126051 183045127603 1004516515418 976478741401 957665143474 451659136716 828528157302 204109014940 184065081345 122138832666 130646707415 144391522538 87966805947 381909891703 343575641318
示例输出 3
3597854777632