← 返回题目列表

AtCoder · abc386_e

H. 最大化异或

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \oplus 5 = 6 (二进制表示法: 011 \oplus 101 = 110).
一般来说,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