/ 7FOJ / 题库 /

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

「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\).

信息

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