分数: 500 点
问题陈述
给你一个序列 A 长度非负整数 N,和一个整数 K。保证二项式系数 \dbinom{N}{K} 最多是 10^6.
选择时 K 不同的元素 A,找到 XOR 的最大可能值 K 选择的元素。
即找到 \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}.
关于异或
对于非负整数 A,B,异或 A \oplus B 定义如下:- 在二进制表示中 A \oplus B,对应的位 2^k (k \ge 0) is 1 当且仅当正好对应于的位之一 2^k in A 和 B is 1,并且是 0 否则。
一般来说,XOR K 整数 p_1, \dots, p_k 定义为 (\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<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).
- (3,2):异或是 3\oplus 2 = 1.
- (3,6):异或是 3\oplus 6 = 5.
- (3,4):异或是 3\oplus 4 = 7.
- (2,6):异或是 2\oplus 6 = 4.
- (2,4):异或是 2\oplus 4 = 6.
- (6,4):异或是 6\oplus 4 = 2.
因此,最大可能值为 7.
示例输入 2
10 4 1516 1184 1361 2014 1013 1361 1624 1127 1117 1759
示例输出 2
2024