题解

• 结论

  • 设数组为 $a_1,\dots,a_n$，最大值为 $M=\max(a_i)$，其二进制长度为 $L$（特别地，当 $M=0$ 时 $L=1$）。
  • 记按位与为 $A=\bigwedge_{i=1}^n a_i$，定义掩码 $mask=2^L-1$。
  • 使总和最大的最小初始 $x$ 为：

  

题目内容

小美有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} ，他希望构造一个非负整数 $x$ ， 满足 $x$ 的二进制位数不超过数组中最大值的二进制位数(特别的 $0$ 二进制位数为 $1$ )。

随后，可对数组 $a$ 重复进行以下操作，以使所有元素的总和最大：

• 选择一个下标 $i$ ，同时将 $a_i$ 修改为 $a_i$ $or$ $x$ ，将 $x$ 修改为 $a_i$ $and$ $x$ 。

在使元素总和达到最大值的前提下，要求所有操作前初始的 $x$ 尽可能小。请输出最大总和及对应的最小 $x$ 。

按位或：$or$ 表示按位或运算，即对两个整数的二进制表示的每一位进行逻辑或操作。

按位与：$and$ 表示按位与运算，即对两个整数的二进制表的每一位进行逻辑与操作。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1≦T≦1000)$ ，代表数据组数；

对于每组测试数据，输入如下：

第一行输入一个整数 $n(1 ≦ n≦ 500)$ ，表示数组的长度；

第二行输入 $n$ 个整数 $a_1, a_2,...,a_n(0 ≦ a_i< 2^{30})$，表示数组 $a$ 的元素。

输出描述

对于每组测试数据，新起一行，输出两个整数，用空格分隔：第一个整数为数组可以达到的最大总和；第二个整数为在达到最大总和的前提下初始最小的 $x$ 。

样例1

输入

2
2
3 3
3
1 2 3

输出

6 0
9 3