XORの問題

最近トップコーダーの色混ぜ問題で混乱しています。目的は最少の色を使う事です。Two approaches are possible to span all colors. One is to simply enumerate the numbers, so the count is n for n numbers. The other option is to specify a basis of all binary strings of x bits, where x is the bit length of the longest number in binary. The number of basis vectors is x (e.g. 001,010,100). However, there are cases when neither approach is optimal. For example: {100001,100000,000001} is spanned by 6 vectors considering they are all 6 bits, or could be enumerated by 3 numbers. However, choosing any 2 above generates the 3rd via XOR. Thus, 2 is the optimal answer.
The optimal solution is an elegant and non-intuitive linear algebra implementation. Gaussian elimination is used to find the basis of a set of vectors, where the basis is the subset such that no vector is a linear combination of the others. In the XOR form, the basis is the subset such that no vector is an XOR combination (i.e. C=A XOR B) of the others. The linear product definition does translate to the XOR definition, as, if a vector's one columns can be eliminated, left to right, by XOR'ing it with other vectors, that vector is an XOR combination of these other vectors.
正解は美しい線形代数学の実施です。
The Gaussian elimination algorithm works as follows:
1. set nIters to 0
2. at each execution of while loop, start at nIters+1 row and find the row with the leftmost non-zero bit (column k)
3. swap this row with the nIters+1st row
4. zero out the kth column of all rows below nIters+1 by XORing it with the nIters+1st
5. increment nIters
When no further rows are found, the algorithm halts. The size of the basis is the number of non-all-zero vectors in the resulting matrix. Note that XOR in C++ is represented by the "^" operator.