E - Maximize XOR Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500

問題文

長さ N の非負整数列 A および整数 K が与えられます。ここで二項係数 \dbinom{N}{K}10^6 以下であることが保証されます。

A から異なる K 項を選ぶとき、選んだ K 個の数の総 XOR としてあり得る最大値を求めてください。

すなわち \underset{1\leq i_1\lt i_2\lt \ldots\lt i_K\leq N}{\max} A_{i_1}\oplus A_{i_2}\oplus \ldots \oplus A_{i_K} を求めてください。

XOR とは 非負整数 A,B の XOR A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k \, (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、 3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101=110)。
一般に k 個の整数 p_1, \dots, p_k の XOR は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。

制約

  • 1\leq K\leq N\leq 2\times 10^5
  • 0\leq A_i\lt 2^{60}
  • \dbinom{N}{K}\leq 10^6
  • 入力は全て整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

答えを出力せよ。


入力例 1

4 2
3 2 6 4

出力例 1

7

(3,2,6,4) から異なる 2 つの項を選ぶ方法は以下の 6 通りあります。

  • (3,2) のとき、選んだ数の総 XOR は 3\oplus 2 = 1 です。
  • (3,6) のとき、選んだ数の総 XOR は 3\oplus 6 = 5 です。
  • (3,4) のとき、選んだ数の総 XOR は 3\oplus 4 = 7 です。
  • (2,6) のとき、選んだ数の総 XOR は 2\oplus 6 = 4 です。
  • (2,4) のとき、選んだ数の総 XOR は 2\oplus 4 = 6 です。
  • (6,4) のとき、選んだ数の総 XOR は 6\oplus 4 = 2 です。

よって、求める最大値は 7 です。


入力例 2

10 4
1516 1184 1361 2014 1013 1361 1624 1127 1117 1759

出力例 2

2024

Score : 500 points

Problem Statement

You are given a sequence A of non-negative integers of length N, and an integer K. It is guaranteed that the binomial coefficient \dbinom{N}{K} is at most 10^6.

When choosing K distinct elements from A, find the maximum possible value of the XOR of the K chosen elements.

That is, find \underset{1\leq i_1\lt i_2\lt \ldots\lt i_K\leq N}{\max} A_{i_1}\oplus A_{i_2}\oplus \ldots \oplus A_{i_K}.

About XOR For non-negative integers A,B, the XOR A \oplus B is defined as follows:
  • In the binary representation of A \oplus B, the bit corresponding to 2^k (k \ge 0) is 1 if and only if exactly one of the bits corresponding to 2^k in A and B is 1, and is 0 otherwise.
For example, 3 \oplus 5 = 6 (in binary notation: 011 \oplus 101 = 110).
In general, the XOR of K integers p_1, \dots, p_k is defined as (\cdots((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). It can be proved that it does not depend on the order of p_1, \dots, p_k.

Constraints

  • 1\leq K\leq N\leq 2\times 10^5
  • 0\leq A_i<2^{60}
  • \dbinom{N}{K}\leq 10^6
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the answer.


Sample Input 1

4 2
3 2 6 4

Sample Output 1

7

Here are six ways to choose two distinct elements from (3,2,6,4).

  • (3,2): The XOR is 3\oplus 2 = 1.
  • (3,6): The XOR is 3\oplus 6 = 5.
  • (3,4): The XOR is 3\oplus 4 = 7.
  • (2,6): The XOR is 2\oplus 6 = 4.
  • (2,4): The XOR is 2\oplus 4 = 6.
  • (6,4): The XOR is 6\oplus 4 = 2.

Hence, the maximum possible value is 7.


Sample Input 2

10 4
1516 1184 1361 2014 1013 1361 1624 1127 1117 1759

Sample Output 2

2024