求助 - 洛谷仓库

给你一个长度为

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$ 的二进制表示中，当且仅当 $A$ 和 $B$ 中与 $2^k$ 相对应的位中正好有一位是 $1$ 时，与 $2^k (k \ge 0)$ 相对应的位才是 $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

的阶数无关。

求做法，给关

求助