#649. [MtOI2019] 永夜的报应

[MtOI2019] 永夜的报应

题目描述

蓬莱山 辉夜(Kaguya)手里有一堆数字。

辉夜手里有 nn 个非负整数 a1,a2⋯ana_1,a_2\cdots a_n,由于辉夜去打 Gal Game 去了,她希望智慧的你来帮忙。

  • 你需要将这些数分成若干组,满足 nn 个数中的每一个数都恰好被分到了一个组中,且每一组至少包含一个数。

定义一组数的权值为该组内所有数的异或和。请求出一种分组方案,使得分出的所有组数的权值之和最小,输出权值之和的最小值。

输入格式

输入的第一行包含一个正整数 nn,表示给定的非负整数的数量。

接下来一行包含 nn 个非负整数 a1,a2⋯ana_1,a_2\cdots a_n。

输出格式

输出一行一个整数表示答案。

样例

3
1 2 5
6
6
9 18 36 25 9 32
15

题目来源:洛谷 P5514