E. The 67th XOR Problem

    传统题 3000ms 256MiB

The 67th XOR Problem

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

PMOI 其实也没那么糟糕——坊间传闻说题目还不错,甚至(绝非夸张)挺有趣的!然而令 Macaque 失望的是,三名不守规矩的参赛者(Cloud、ChatGBT 和 Grook)凭借对 OEIS 的完美记忆力开始作弊。真是无赖!Macaque 必须迅速行动,设计一道这三个人无法作弊的题目。你从他的同伴被降职为可怜的奴隶,被征召来测试这道题。

给定一个数组 aa,初始包含 nn 个非负整数。

执行以下操作恰好 n−1n-1 次:

  1. 选择 aa 的一个下标 ii(1≤i≤∣a∣1 \leq i \leq |a|,其中 ∣a∣|a| 表示 aa 的当前长度)。令 x=aix = a_i。
  2. 对所有 1≤j≤∣a∣1 \leq j \leq |a|,令 aj=aj⊕xa_j = a_j \oplus x,其中 ⊕\oplus 表示按位异或操作。
  3. 从数组中移除 aia_i。

可以证明,经过 n−1n-1 次操作后,数组中恰好剩下一个元素。你的任务是确定在最优操作下,最终剩余元素的最大可能值。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 tt(1≤t≤1001 \le t \le 100)。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 nn(2≤n≤31052 \le n \le 3105)——数组的初始长度。

每个测试用例的第二行包含 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(0≤ai≤1090 \le a_i \le 10^9)——数组的元素。

保证所有测试用例的 nn 之和不超过 31053105。

输出格式

对于每个测试用例,输出一个整数——最终元素的最大可能值。

样例

3
2
67 67
3
1 2 3
10
67 667 167 867 267 467 367 567 767 967
0
3
1012

说明

在第二个测试用例中,数组为 [1,2,3][1, 2, 3]。一种最优操作序列如下:

  1. 选择元素 33。移除它。剩余元素变为 [1⊕3,2⊕3]=[2,1][1 \oplus 3, 2 \oplus 3] = [2, 1]。
  2. 选择元素 22。移除它。剩余元素变为 [1⊕2]=[3][1 \oplus 2] = [3]。

最终值为 33。

来源

导入自 Codeforces — Codeforces Round 1090 (Div. 4)。

Codeforces Round 1090 (Div. 4)

未参加
状态
已结束
规则
XCPC
题目
7
开始于
2026-11-11 15:00
结束于
2026-11-11 17:30
持续时间
2.5 小时
主持人
参赛人数
14