D - XXOR

分数: $400$ 分

问题描述

给定 $N$ 个非负整数 $A_1, A_2, ..., A_N$ 和另一个非负整数 $k$。

对于 $0$ 到 $k$ 之间的一个整数 $X$，定义 $f(X) = (X$ 异或 $A_1)$ $+$ $(X$ 异或 $A_2)$ $+$ $...$ $+$ $(X$ 异或 $A_N)$。

这里，对于非负整数 $a$ 和 $b$，$a$ 异或 $b$ 表示 $a$ 和 $b$ 的按位异或。

找到 $f$ 的最大值。

异或运算 $X$（表示 $a$ 异或 $b$）定义如下：

• 当 $X$ 表示为二进制时，$2^k$ 位（$k \geq 0$）的数字是 $1$ 当且仅当在 $a$ 和 $b$ 的二进制表示中，恰好有一个数字在 $2^k$ 位上为 $1$；否则为 $0$。

例如，$3$ 异或 $5 = 6$（二进制表示为：$011$ 异或 $101 = 110$）。

</details>

约束

• 输入中的所有值都是整数。
• $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$ 的最大值。

3 7
1 6 3

14

最大值是：$f(4) = (4$ 异或 $1) + (4$ 异或 $6) + (4$ 异或 $3) = 5 + 2 + 7 = 14$。

4 9
7 4 0 3

46

1 0
1000000000000

1000000000000