It took days for me to understand the DP solution by reading other solutions and comments and this link https://plus.maths.org/content/play-win-nim. I know this is an old problem but I feel like writing an editorial based on what I know since there isn't one.

First read the link above. With that we can reduce the problem to: what is the minimum number of stones to add to make the XOR of the piles equal to 0? Though, this problem is still very difficult.

Since we are dealing with XOR, it is useful to think in terms of bits. Assume the optimal solution adds to for all . What happens to the bits when we add them both? Notice that the highest bit that changes in always goes from to otherwise the result would be less than which is not possible since is positive. Let be the position of that bit . We can break into parts such that :

• the minimum to add to make the bit and all lower bits
• for turning on the bits after adding to make it all sum back to

There are s that we don't know. Here's where DP comes in.

Let's go from highest to lowest bit and set for some s where is the current bit position. This suggests a bitmask approach where the bit is on in the mask if .

Let be the minimum to add only considering XOR of the bits and above such that represents the : . The transition from to looks like a variation of the "sum-over-subsets DP" however I could not find an solution using this method. The trick is that we do not need to consider all submasks. Say that we have , such that . Since turns all 's bits lower than into zeroes, we may use to change parity as needed. Since the goal is to make the number of ones at the current bit position even, we only set at most once, right? This is only true for that are not the maximum. If there is no , such that there would be no way to change parity unless we set another , . This means there can be at most 2 maximum s. With this the transition from to can be done in thus the total time is .

Let be the position of the lowest bit such that for all .

Base cases:

• : nothing to add when all bits and above are zero.
• for all non-empty s: no need to consider the rest; mask starts empty.

DP transitions:

• for all such that the number of on bits not in the is odd.
• for all and the bit in is off and the number of on bits not in the is odd.
• for all such that the number of on bits not in the is even.
• for all such that the parity of the number of elements in the is the same as the parity of the number of on bits not in the and the number of elements in the mask is at most 2 and there are no on bits in the .

Answer:

: we may end with any mask.