题目描述

给定n个整数(数字可能重复),求在这些数中选取任意个,使得他们的异或和最大。

异或的一些性质

$xor$函数的运算规则可以用一句话简要概括——相同为1,不同为0.

$xor$ 1 0
1 1 0
0 0 1

因为相同的数异或等于0,因此我们来思考这样一个有趣的问题:

给你一串数字,有些数出现了2次,其中只有一个数只出现了1次。求只出现1次的数是多少。

我们根据相同的数异或等于0这个性质,只需从头到尾异或一遍,即可找出那个数。

(这个性质好像在洛谷上有一道题,但是题号忘记了)

线性基问题的解法

定义

对于一组数$a_1,a_2,…,a_n$,它们的线性基为