Nim

Nim is a $2$-player game played with several piles of stones. Players alternate turns; on each turn, a player removes one or more stones from a single pile. The game ends when all stones are removed, and the player who took the last stone is declared the winner. Given a Nim position, your task is to determine how many winning moves exist for that position.

A position in Nim is called losing if, after any move by the first player, the opponent can play optimally and guarantee victory. A winning move is a move that leaves the game in a losing position for the opponent. There is a well-known theorem that classifies all losing positions. Suppose a Nim position consists of $n$ piles, with k_1, k_2, \ldots, k_n stones respectively; in such a position, there are k_1 + k_2 + \ldots + k_n possible moves. Write each k_i in binary. The position is losing if and only if there is an even number of $1$'s in every bit position among all k_i. In other words, the position is losing if and only if k_1 \oplus k_2 \oplus \ldots \oplus k_n = 0 (where $\oplus$ denotes bitwise XOR).

Consider a position with three piles: k_1 = 7, k_2 = 11, k_3 = 13. Their binary representations are:

111
1011
1101

There is an odd number of $1$'s in at least one column, so this position is not losing. Suppose k_3 is changed to $12$; then, each column would have an even number of $1$'s, and the position would become losing. Any move that leaves the position in a losing state is a winning move. For the position k_1 = 7, k_2 = 11, k_3 = 13, there are three such moves—removing a stone from any pile such that the XOR of the new pile sizes is $0$.