分数: 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