/ 7FOJ / 题库 /

「MtOI2019」异或和(非官方数据)

「MtOI2019」异或和(非官方数据)

测试数据来自 North_Home/1002

背景

  • Idea: MtOI2019
  • Data: bfw
  • Solution: bfw
  • 题面: MtOI2019 + bfw

  • 在一个迷茫的森林中,恐怕你难以再回返 \cdots \cdots
  • 那还不如一路向前

注:\oplus 表示 xor\text{xor} 运算。

描述

给定一个长度为 nn 的序列 aa,你需要将它们 不重不漏 地分组(即每个数在且仅在一组里)。当前分组方案的 “异或和值” 为 每一组所有数的异或之和。求这个最小的异或和值。

输入格式

第一行一个数,nn.
第二行 nn 个数,表示序列 aa,空格隔开。

输出格式

一行,最小的异或和值。

样例

样例输入 11

3
1 2 3

样例输出 11

样例输入 22

7
9 1 3 4 5 6 2

样例输出 22

14

样例输入 33

15
1 6 4 8 15 31 94 6 6 21 21 4 54 6 64

样例输出 33

49

样例解释

样例 11 的解释

对于序列 {1,2,3}\{ 1 , 2 , 3 \} 中,有以下几种分组方案:

  • {1},{2,3}\{ 1 \} , \{ 2 , 3 \} , 异或和为 1+23=1+1=21 + 2 \oplus 3 = 1 + 1 = 2.
  • {2},{1,3}\{ 2 \} , \{ 1 , 3 \} , 异或和为 2+13=2+2=42 + 1 \oplus 3 = 2 + 2 = 4.
  • {3},{1,2}\{ 3 \} , \{ 1 , 2 \} , 异或和为 3+12=3+0=33 + 1 \oplus 2 = 3 + 0 = 3.
  • {1,2,3}\{ 1 , 2 , 3 \} , 异或和为 123=01 \oplus 2 \oplus 3 = 0.

所以最小值为 00.

数据范围与约定

对于 30%30 \% 的数据,n15n \leq 15.
对于 60%60 \% 的数据,n3×103,ai103n \leq 3 \times 10^3 , a_i \leq 10^3.
对于 80%80 \% 的数据,n,ai2×105n , a_i \leq 2 \times 10^5.
对于 100%100 \% 的数据,1n106,0ai1061 \leq n \leq 10^6 , 0 \leq a_i \leq 10^6.

信息

ID
1121
难度
6
分类
数论 | 贪心 点击显示
标签
递交数
1
已通过
1
通过率
100%
上传者