AT_abc386_e.[ABC386E] Maximize XOR

给定一个长度为 $N$ 的非负整数序列 $A$ 和一个整数 $K$。保证二项式系数 $\dbinom{N}{K} \leq 10^6$。

从序列 $A$ 中选择 $K$ 个不同的元素，求出这些元素的异或和的最大值。

简单来说，就是求 $\underset{1 \leq i_1 < i_2 < \ldots < i_K \leq N}{\max} A_{i_1} \oplus A_{i_2} \oplus \ldots \oplus A_{i_K}$。

在这里，异或运算（XOR）是这样定义的：对于两个非负整数 $A$ 和 $B$，其结果 $A \oplus B$ 是一个二进制数，对于每个 $2^k \ (k \geq 0)$ 位，如果 $A$ 和 $B$ 在这一位中恰好只有一个是 $1$，则结果在这一位是 $1$，否则为 $0$。

举个例子：$3 \oplus 5 = 6$，在二进制下：$011 \oplus 101 = 110$。通常来说，$k$ 个整数 $p_1, \dots, p_k$ 的异或值可以表示为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$，并且顺序不会影响结果。

从标准输入中获取输入，格式如下：

$N \ K \ A_1 \ A_2 \ \ldots \ A_N$

请输出那个最大可能的异或值。

• $1 \leq K \leq N \leq 2 \times 10^5$
• $0 \leq A_i < 2^{60}$
• $\dbinom{N}{K} \leq 10^6$
• 所有输入均为整数

示例解释 1

从 $(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$。

本翻译由 AI 自动生成