The question is about this problem: (Zero XOR Subset)-less.

The problem's editorial describes the solution as follows:

First let . If we divided the array into *k* segments, where the right boundaries of these segments are (in increasing order) *i*_{1}, *i*_{2}, …, *i*_{k} (*i*_{k} must be *n*), Every segments subset-xor can be represented as *pr*[*i*_{j}] subset-xor. Therefore besides maximizing *k*, we want to guarantee that the any *pr*[*i*_{j}] non-empty subset has a non-zero XOR-sum. So we calculate the basis size of *pr*[1], *pr*[2], …, *pr*[*n*] numbers (binary vectors) under *GF*(2). Because the basis size will represent the maximum *k* such that all *pr*[*i*_{j}] are linearly independent under *GF*(2) (no *pr*[*i*_{j}] non-empty subset has a zero XOR-sum).

My question is: from the calculated basis size *k*, we know that we can choose *k* linearly independent (under *GF*(2)) *pr*[*i*_{j}] values, but how do we guarantee that we can choose these values such that *i*_{k} = *n* (as the last right boundary of our chosen segments has to be *n*)?

Thanks in advance.

If

pr_{n}= 0 it's clear that answer does not exist (because XOR of all segments will be always 0 despite of partitioning).Otherwise if

pr_{n}is not in maximal basis let's look at basis decomposition ofpr_{n}(it always exists, because otherwise it's possible to addpr_{n}to basis and basis is not maximal), remove any decomposition element from basis and addpr_{n}. Resulting set of vectors obviously has the same size as maximal basis and vectors in it are linear independent (letx_{i}be elements in basis decomposition ofpr_{n}, then , so each non-trivial zero linear combination of vectors in new set of vectors leads to non-trivial zero linear combination of vectors in old set, which is impossible).However, this fact wasn't required to solve this problem, you can simply add

pr_{n}to basis at first stage of Gaussian elimination and basis will always containpr_{n}(moreover, it is another proof of this fact because all bases of set of vectors have the same size).So this means: for a set of vectors

Vwith maximal basis of sizek, if a non-zero vectorvbelongs toV, we can always construct a basis of sizekwhich includesv.Thanks a lot for making it clear to me.