最大异或和II

时间限制:10s      空间限制:256MB

题目描述

  我有一个数列a[1],a[2],…,a[n],每个a[i]是小于2^m的正整数。显然正整数的二进制表示下至少有一个1,
现在,我希望您能把每个数仅保留二进制下其中的某一位1,并最大化这个数列中所有数的异或和。例如,5的二进
制表示为101,那么5就只能变为4(保留从左往右第一个1,即变为100),或者1(保留另一个1,即变为001),11
的二进制表示为1011,那么它可以变为8(1000)、2(0010)、1(0001)中的某一个。


输入格式

  第一行一个正整数T,表示数据组数。对于每组数据:第一行一个正整数n。接下来一行n个正整数,表示a数组
1 ≤ T ≤ 5, 1 ≤ n ≤ 100, 1 ≤ m ≤ 60, 对所有i,有1 ≤ a[i] ≤ 2^m - 1


输出格式

  对于每组数据输出一行一个数,表示最大的异或和


样例输入

5
7
1 2 32 64 1024 2147483648 2147483648
4
15 15 15 1515 15 15 15
5
13 9 38 99 4413 9 38 99 44
10
656 546 64 72 512 256 768 384 450 512
50
12591291 3364543 629743 169925631 172761087 328110 1301503 178655 5898239 8900607 2195167 21010431 5529071 99775 68719477090 1074130671 6592 67133439 35 65711 34143 137439085183 327 268442559 87262719 8198 9843197 67292 135852031 8656895 44671 9645055 376319 131 403201023 360706 331111 1064823 2173855 318839 1148243967 139998 16777216 1086201855 16 33556783 2687 2 84033 105655

样例输出

1123
15
110
1018
207769042943
  样例说明:对于第一组数据,每个数二进制下都只有一个位是1,所以唯一的一个方案就是全部保持原样,答案
这七个数的异或和,即1123。对于第二组数据,可以变为1 2 4 8或者它的任意排列。对于第三组数据,一种最优
方案是变为4,8,2,64,32。对于第四组数据,一种最优方案是变为16,32,64,8,512,256,512,128,2,512。

提示

没有写明提示


题目来源

By matthew99

Menuappsclose