Problem Statement
Construct a sequence a = {a_1,\ a_2,\ ...,\ a_{2^{M + 1}}} of length 2^{M + 1} that satisfies the following conditions, if such a sequence exists.
- Each integer between 0 and 2^M - 1 (inclusive) occurs twice in a.
- For any i and j (i < j) such that a_i = a_j, the formula a_i \ xor \ a_{i + 1} \ xor \ ... \ xor \ a_j = K holds.
What is xor (bitwise exclusive or)?
The xor of integers c_1, c_2, ..., c_n is defined as follows:
- When c_1 \ xor \ c_2 \ xor \ ... \ xor \ c_n is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if the number of integers among c_1, c_2, ...c_m whose binary representations have 1 in the 2^k's place is odd, and 0 if that count is even.
For example, 3 \ xor \ 5 = 6. (If we write it in base two: 011
xor 101
= 110
.)