「MtOI2019」异或和(非官方数据)
测试数据来自 North_Home/1002
背景
- Idea: MtOI2019
- Data: bfw
- Solution: bfw
- 题面: MtOI2019 + bfw
- 在一个迷茫的森林中,恐怕你难以再回返 \(\cdots \cdots\)
- 那还不如一路向前
注:\(\oplus\) 表示 \(\text{xor}\) 运算。
描述
给定一个长度为 \(n\) 的序列 \(a\),你需要将它们 不重不漏 地分组(即每个数在且仅在一组里)。当前分组方案的 “异或和值” 为 每一组所有数的异或之和。求这个最小的异或和值。
输入格式
第一行一个数,\(n\).
第二行 \(n\) 个数,表示序列 \(a\),空格隔开。
输出格式
一行,最小的异或和值。
样例
样例输入 \(1\)
3
1 2 3
样例输出 \(1\)
0
样例输入 \(2\)
7
9 1 3 4 5 6 2
样例输出 \(2\)
14
样例输入 \(3\)
15
1 6 4 8 15 31 94 6 6 21 21 4 54 6 64
样例输出 \(3\)
49
样例解释
样例 \(1\) 的解释
对于序列 \(\{ 1 , 2 , 3 \}\) 中,有以下几种分组方案:
- \(\{ 1 \} , \{ 2 , 3 \}\) , 异或和为 \(1 + 2 \oplus 3 = 1 + 1 = 2\).
- \(\{ 2 \} , \{ 1 , 3 \}\) , 异或和为 \(2 + 1 \oplus 3 = 2 + 2 = 4\).
- \(\{ 3 \} , \{ 1 , 2 \}\) , 异或和为 \(3 + 1 \oplus 2 = 3 + 0 = 3\).
- \(\{ 1 , 2 , 3 \}\) , 异或和为 \(1 \oplus 2 \oplus 3 = 0\).
所以最小值为 \(0\).
数据范围与约定
对于 \(30 \%\) 的数据,\(n \leq 15\).
对于 \(60 \%\) 的数据,\(n \leq 3 \times 10^3 , a_i \leq 10^3\).
对于 \(80 \%\) 的数据,\(n , a_i \leq 2 \times 10^5\).
对于 \(100 \%\) 的数据,\(1 \leq n \leq 10^6 , 0 \leq a_i \leq 10^6\).