

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 である。
一般に 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.
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