← 返回题目列表

AtCoder · abc390_d

G. 石异或

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

分数: 400 点

问题陈述

有 N 袋子,贴有标签的袋子 1,包 2, \ldots,包 N.
包 i (1 \leq i \leq N) 包含 A_i 石头。

Takahashi 可以执行以下操作任意次数,可能为零:

选择两个袋子 A 和 B,然后移动 全部 石头从袋子 A 放入袋子 B。

重复操作后,找出以下不同可能值的数量。

  • B_1 \oplus B_2 \oplus \cdots \oplus B_N,其中 B_i 是袋子中的最终石子数量 i.
    在这里, \oplus 表示按位异或。
关于按位异或 对于非负整数 a 和 b,按位异或 a \oplus b 定义如下:
在二进制表示中 a \oplus b,中的数字 2^k 地点(k \ge 0)是 1 当且仅当恰好是 中的数字之一 2^k 地点 a 和 b is 1;否则,就是 0.
例如, 3 \oplus 5 = 6 (二进制, 011 \oplus 101 = 110).
一般来说,对于 k 非负整数 x_1, x_2, \ldots, x_k,它们的按位异或 x_1 \oplus x_2 \oplus \cdots \oplus x_k 定义为 (\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k,这不依赖于顺序 x_1, x_2, \ldots, x_k.

可以证明,在该问题的约束下,可能值的数量是有限的。

约束

  • 2 \leq N \leq 12
  • 1 \leq A_i \leq 10^{17}
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

打印不同可能值的数量 B_1 \oplus B_2 \oplus \cdots \oplus B_N 重复操作后。


示例输入 1

3
2 5 7

示例输出 1

3

例如,如果高桥选择包包 1 和 3 为操作,则袋中石子的数量 1, 2, 3 成为 0, 5, 9.
如果他在此时停止,则 XOR 为 0 \oplus 5 \oplus 9 = 12.

重复操作后其他可能的 XOR 值是 0 和 14.
因此,可能的值为 0, 12, 14;共有三个值,因此输出为 3.


示例输入 2

2
100000000000000000 100000000000000000

示例输出 2

2

示例输入 3

6
71 74 45 34 31 60

示例输出 3

84