← 返回题目列表

AtCoder · agc071_a

A. 异或交叉

中文机器翻译题面 查看原题

分数: 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。
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101 = 110).
一般来说,按位 \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. 删除 (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) 。
  2. 删除 (0,2) 从黑板开始并设置 k=1。两个新序列 (2),(2) 。
  3. 删除 (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