[ABC117D] XXOR

ID: 17941

传统题

2000ms

1024MiB

难度: 4

上传者:

配点 : $400$ 点

問題文

$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$ の最大値を求めてください。

XOR とは

整数 $A, B$ のビットごとの排他的論理和 $X$ は、以下のように定義されます。

$X$ を二進表記した際の $2^k$ ( $k \geq 0$ ) の位の数は、 $A, B$ を二進表記した際の $2^k$ の位の数のうち一方のみが $1$ であれば $1$ 、そうでなければ $0$ である。

例えば、 $3$ XOR $5 = 6$ となります (二進数表記すると: $011$ XOR $101 = 110$ )。

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$A_1$ $A_2$ $...$ $A_N$

$f$ の最大値を出力せよ。

3 7
1 6 3

$f(4) = (4$ XOR $1) + (4$ XOR $6) + (4$ XOR $3) = 5 + 2 + 7 = 14$ が最大です。

4 9
7 4 0 3

1 0
1000000000000

1000000000000