(Zero XOR Subset)-less
Contest: Educational Codeforces Round 58 (Rated for Div. 2)
Difficulty rating: 2300
Tags: math, matrices

You are given an array $$$a_1, a_2, \dots, a_n$$$ of integer numbers.

Your task is to divide the array into the maximum number of segments in such a way that:

- each element is contained in exactly one segment;
- each segment contains at least one element;
- there doesn't exist a non-empty subset of segments such that bitwise XOR of the numbers from them is equal to $$$0$$$.

Print the maximum number of segments the array can be divided into. Print -1 if no suitable division exists.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the size of the array.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$).

Output format:
Print the maximum number of segments the array can be divided into while following the given constraints. Print -1 if no suitable division exists.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example $$$2$$$ is the maximum number. If you divide the array into $$$\{[5], [5, 7, 2]\}$$$, the XOR value of the subset of only the second segment is $$$5 \oplus 7 \oplus 2 = 0$$$. $$$\{[5, 5], [7, 2]\}$$$ has the value of the subset of only the first segment being $$$5 \oplus 5 = 0$$$. However, $$$\{[5, 5, 7], [2]\}$$$ will lead to subsets $$$\{[5, 5, 7]\}$$$ of XOR $$$7$$$, $$$\{[2]\}$$$ of XOR $$$2$$$ and $$$\{[5, 5, 7], [2]\}$$$ of XOR $$$5 \oplus 5 \oplus 7 \oplus 2 = 5$$$.

Let's take a look at some division on $$$3$$$ segments — $$$\{[5], [5, 7], [2]\}$$$. It will produce subsets:

- $$$\{[5]\}$$$, XOR $$$5$$$;
- $$$\{[5, 7]\}$$$, XOR $$$2$$$;
- $$$\{[5], [5, 7]\}$$$, XOR $$$7$$$;
- $$$\{[2]\}$$$, XOR $$$2$$$;
- $$$\{[5], [2]\}$$$, XOR $$$7$$$;
- $$$\{[5, 7], [2]\}$$$, XOR $$$0$$$;
- $$$\{[5], [5, 7], [2]\}$$$, XOR $$$5$$$;

As you can see, subset $$$\{[5, 7], [2]\}$$$ has its XOR equal to $$$0$$$, which is unacceptable. You can check that for other divisions of size $$$3$$$ or $$$4$$$, non-empty subset with $$$0$$$ XOR always exists.

The second example has no suitable divisions.

The third example array can be divided into $$$\{[3], [1], [10]\}$$$. No subset of these segments has its XOR equal to $$$0$$$.

Example input:
4
5 5 7 2

Example output:
2

Example input:
3
1 2 3

Example output:
-1

Editorial:
Let's consider some division $$$[0, i_1)$$$, $$$[i_1, i_2)$$$, ..., $$$[i_k, n)$$$. Represent the XOR sum of the subset via prefix-XOR. Those are $$$pr[i_1] \oplus pr[0]$$$, $$$pr[i_2] \oplus pr[i_1]$$$, ..., $$$pr[n] \oplus pr[i_k]$$$.
I claim that you can collect any subset that is a XOR of an even number of $$$pr[x]$$$ for pairwise distinct values of $$$x$$$. Let's take a look on some prefix of processed segments, where the last segment is taken into subset. The previous taken $$$pr[x]$$$'s can't be changed, the last taken $$$pr[x]$$$ can either be eliminated if we also take the current segment (and that segment erases one value and adds one) or added to the answer if we don't take it (but the next taken segment will add two values). You can see that the parity doesn't change.
Moreover, you can collect any subset that is a XOR of an odd number of $$$pr[x]$$$ for pairwise distinct values of $$$x$$$. Just forget about $$$pr[0]$$$ taken into the answer, as its value is $$$0$$$. Then all the even subsets which included it will become odd.
This way we can collect all subsets of $$$pr[x]$$$ for some division. Now you just want find the division that produces the maximum number of linearly independent numbers (binary vectors). That is — the size of the basis of the space of chosen numbers (binary vectors).
Now it's time to abuse the fact that adding a number into the set can only increase the size of basis of the space. Thus, adding anything to the maximum set won't change the answer (otherwise the result would be greater than the "maximum").
Finally, you say that the maximum basis size is equal to the basis size of all the prefix-XOR and easily calculate in $$$O(n \log MAXN)$$$.
The only corner case is $$$pr[n]$$$ being $$$0$$$ itself. Then for any division the full subset will also give $$$0$$$ result. That is the only case with answer $$$-1$$$.
Overall complexity: $$$O(n \log MAXN)$$$.