分数: 2500 点
问题陈述
你被给予 N 非负整数 A_1,A_2,\cdots,A_N。 对于每个 k=1,2,\cdots,N,解决以下问题。
爱丽丝和鲍勃玩以下游戏。
-
爱丽丝选择 k 号码来自 A_1,A_2,\cdots,A_N。 让 x_1,x_2,\cdots,x_k 作为被选中的数字(顺序任意)。
-
鲍勃形成一个序列 2k 非负整数 y=(y_1,y_2,\cdots,y_{2k}),必须满足以下条件。
- 0 \leq y_1 \leq y_2 \leq \cdots \leq y_{2k}.
- 让 z_i=y_{2i-1} \oplus y_{2i}。然后, \{z_1,z_2,\cdots,z_k\} 与 \{x_1,x_2,\cdots,x_k\} 作为一个多重集合。
在这里, \oplus 表示按位 \mathrm{XOR}.
让 分数 本实验的 游戏的值为 y_{2k}。 鲍勃的目标是最小化分数。 考虑到这一点,爱丽丝的目标是最大化分数。 分数会是多少?
什么是按位 \mathrm{XOR}?
按位 \mathrm{XOR} 非负整数 A 和 B, A\ \mathrm{XOR}\ B定义如下。
- 当 A\ \mathrm{XOR}\ B 以二进制形式写入, k- 第最低位 (k \geq 0) 是 1 如果恰好是其中之一 k- 第最低位 A 和 B is 1,和 0 否则。
一般来说,按位 \mathrm{XOR} of k 非负整数 p_1, p_2, p_3, \dots, p_k 定义为 (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k),可以证明它与顺序无关 p_1, p_2, p_3, \dots p_k.
约束
- 1 \leq N \leq 250000
- 1 \leq A_i \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \cdots A_N
输出
打印答案。
示例输入 1
3 1 2 3
示例输出 1
2 6 6
考虑这种情况 例如 k=1.
- 如果爱丽丝选择 x_1=1:鲍勃做出 y=(0,1),得分为 1.
- 如果爱丽丝选择 x_1=2:鲍勃做出 y=(0,2),得分为 2.
- 如果爱丽丝选择 x_1=3:鲍勃做出 y=(1,2),得分为 2.
因此,爱丽丝将选择 x_1=2 or x_1=3,得分为 2.
考虑这种情况 例如 k=2。 如果爱丽丝选择 (x_1,x_2)=(2,3) 而鲍勃做出 y=(1,2,4,6),分数将为 6。 这是双方最佳玩法的一个例子,答案是 6.
考虑这种情况 例如 k=3。 如果爱丽丝选择 (x_1,x_2,x_3)=(1,2,3) 而鲍勃做出 y=(0,1,1,2,4,6),分数将为 6。 这是双方最佳玩法的一个例子,答案是 6.
示例输入 2
5 1 1 1 1 1
示例输出 2
1 3 5 7 9
示例输入 3
5 1 2 4 8 16
示例输出 3
16 24 28 30 31
示例输入 4
20 167660508 377125547 866003430 419036363 234113368 201296307 408194538 249252693 207212853 190504619 306027011 652875643 335898069 545795899 204268068 274532279 342039277 975300308 901270584 360957186
示例输出 4
536870912 1610612736 2684354560 3758096384 4831838208 4831838208 4831838208 4831838208 4831838208 5100273664 5100273664 5100273664 5100273664 5100273664 5100273664 5100273664 5100273664 5100273664 5100273664 5100273664