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