2218E.md (2392B)
1 Source: https://codeforces.com/problemset/problem/2218/E 2 3 E. The 67th XOR Problem 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 The PMOI wasn't even that awful - word on the street was that the problems were decent, and even (heaven forbid) enjoyable! To Macaque's dismay, however, three unruly participants (Cloud, ChatGBT and Grook) started cheating using their perfect memory of the OEIS. What utter rapscallions! Suddenly, Macaque had to act fast, and devise a problem that these three could not feasibly cheat on. You, demoted from the rank of his companion to his wretched slave, have been enlisted to test. 22 23 You are given an array $a$, initially containing $n$ non-negative integers. 24 25 You perform the following operation exactly $n-1$ times: 26 27 1. Select an index $i$ of $a$ ($1 \leq i \leq |a|$, where $|a|$ denotes the current length of $a$). Let $x = a_i$. 28 2. Set $a_j = a_j \oplus x$ for all $1 \leq j \leq |a|$, where $\oplus$ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). 29 3. Remove $a_i$ from the array. 30 31 It can be shown that after $n-1$ operations, exactly one element remains in the array. Your task is to determine the maximum possible value of this final remaining element if you perform the operations optimally. 32 33 Input 34 35 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). The description of the test cases follows. 36 37 The first line of each test case contains a single integer $n$ ($2 \le n \le 3105$) — the initial length of the array. 38 39 The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the array. 40 41 It is guaranteed that the sum of $n$ over all test cases does not exceed $3105$. 42 43 Output 44 45 For each test case, output a single integer — the maximum possible value of the final element. 46 47 Example 48 49 Input 50 51 ``` 52 3 53 54 2 55 56 67 67 57 58 3 59 60 1 2 3 61 62 10 63 64 67 667 167 867 267 467 367 567 767 967 65 ``` 66 67 Output 68 69 ``` 70 0 71 72 3 73 74 1012 75 ``` 76 77 Note 78 79 In the second test case, the array is $[1, 2, 3]$. One optimal sequence of operations is: 80 81 1. Select the element $3$. Remove it. The remaining elements become $[1 \oplus 3, 2 \oplus 3] = [2, 1]$. 82 2. Select the element $2$. Remove it. The remaining element becomes $[1 \oplus 2] = [3]$. 83 84 The final value is $3$.