Official Editorial (C++)

Explanation

To solve this problem, notice that the result of performing XOR operations on a sequence of $a_i < 500$ is strictly less than $2^9$. That's because the ninth bit is the largest possible in the binary representation of $a_i$.

With this observation, we can now formulate our DP solution. Let $dp[x][i]$ represent the feasibility of getting $x$ as a result of XOR of an increasing sequence ending with a number less than or equal to $i$. There exists the following recurrence:

with

since it is always possible to get 0 from an increasing sequence consisting of zero element.

Implementation

Time Complexity: $\mathcal{O}(n \cdot 2^{\lceil \log_2(\text{MAXA}) \rceil})$

Copy
#include <bits/stdc++.h>
using namespace std;

const int MAXA = 1 << 9;

int main() {
	int n;
	cin >> n;
	vector<int> arr(n);
	for (int &i : arr) { cin >> i; }