XXOR

题目描述

给定 $N$ 个非负整数 $A_1, A_2, ..., A_N$ 以及另一个非负整数 $K$。 对于介于 $0$ 和 $K$（含）之间的整数 $X$，定义 $f(X) = (X$ XOR $A_1)$ $+$ $(X$ XOR $A_2)$ $+$ $...$ $+$ $(X$ XOR $A_N)$。 这里，对于非负整数 $a$ 和 $b$，$a$ XOR $b$ 表示 $a$ 与 $b$ 的按位异或。 求 $f$ 的最大值。

What is XOR?

$a$ 与 $b$ 的按位异或，$X$，定义如下：

当 $X$ 以二进制表示时，$2^k$ 位（$k \geq 0$）的数字为 $1$ 当且仅当在二进制表示中，$A$ 与 $B$ 在 $2^k$ 位恰好有一个为 $1$，否则为 $0$。

例如，$3$ XOR $5 = 6$.（二进制表示：$011$ XOR $101 = 110$.）

输入格式

输入由标准输入给出，格式如下： $N$ $K$ $A_1$ $A_2$ $...$ $A_N$

输出格式

输出 $f$ 的最大值。

3 7
1 6 3

14

4 9
7 4 0 3

46

1 0
1000000000000

1000000000000

提示

输入中的所有值均为整数。 $1 \leq N \leq 10^5$ $0 \leq K \leq 10^{12}$ $0 \leq A_i \leq 10^{12}$最大值为：$f(4) = (4$ XOR $1) + (4$ XOR $6) + (4$ XOR $3) = 5 + 2 + 7 = 14$.

标签: AtCoder|abc117D

来源

AtCoder|abc117D