分数: 400 点
问题陈述
你被给予 N 非负整数 A_1, A_2, ..., A_N 和另一个非负整数 K.
对于整数 X 之间 0 和 K (含),让 f(X) = (X 异或 A_1) + (X 异或 A_2) + ... + (X 异或 A_N).
这里,对于非负整数 a 和 b, a 异或 b 表示按位异或 a 和 b.
找到最大值 f.
什么是异或?
按位异或 a 和 b, X,定义如下:
- 当 X 以基数 2 书写,即 2^k的地点 (k \geq 0) 是 1 如果以二为基数书写时,恰好是以下之一 A 和 B 有 1 在 2^k的地点,以及 0 否则。
例如, 3 异或 5 = 6。 (当以二为基数书写时: 011 异或 101 = 110.)
约束
- 输入中的所有值都是整数。
- 1 \leq N \leq 10^5
- 0 \leq K \leq 10^{12}
- 0 \leq A_i \leq 10^{12}
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 ... A_N
输出
打印最大值 f.
示例输入 1
3 7 1 6 3
示例输出 1
14
最大值为: f(4) = (4 异或 1) + (4 异或 6) + (4 异或 3) = 5 + 2 + 7 = 14.
示例输入 2
4 9 7 4 0 3
示例输出 2
46
示例输入 3
1 0 1000000000000
示例输出 3
1000000000000