Nim
---

This problem looks complicated but it actually is one of the easier problems once you
get your head around it. First of all, it is useful to remember the definition of xor.
Given two numbers x and y written in binary, we define x xor y to be the sum of x and
y WITHOUT carries. For example,

    11011001
xor 10011100
------------
  = 01000101

This command is built in to both C and Java. To compute x xor y, simply write x ^ y.
Just like with addition, we can compute x ^ y ^ z as (x ^ y) ^ z, and so on. One
interesting property of xor, however, is that it is its own inverse. For example, in
addition if we want to find x such that x + a = b, we choose x = b - a. With xor, it
is even easier! If we want x ^ a = b, we choose x = b ^ a.

Now, the problem is asking the following: given positive integers, k_i, how many ways
can we replace a single k_i with a smaller number k_i' such that the xor of the resulting
numbers is 0. One approach would be for each i, to loop over every number less than k_i,
compute the resulting xor, and then see if it is 0. Unfortunately, the k_i's can be
as large as a billion, so this is prohibitively slow.

Fortunately, you can do it faster. To make the xor 0, we need to choose k_1' so that
k_1' ^ (k_2 ^ k_3 ^ ... ^ k_n) = 0. As mentioned earlier, this is equivalent to choosing
k_1' = (k_2 ^ k_3 ^ ... ^ k_n), but this is easily computed! Now, if k_1' is less than
k_1, this gives a valid winning move. Otherwise, there is no winning move for that pile.
Using one more clever (but unnecessary) observation that k_2 ^ k_3 ^ ... ^ k_n is equal
to (k_1 ^ k_2 ^ ... ^ k_n) ^ k_1, we can solve the problem in C++ as shown below.

    int i, x = 0, count = 0;
    for (i = 0; i < n; i++)
      x = x ^ k[i];
    for (i = 0; i < n; i++)
      if ((k[i] ^ x) < k[i])
	count++;
    cout << count << endl;