Thought Process

I recommend trying Problem 301 and Problem 306 before trying this one!

Recently I've been learning combinatorial game theory so I've been going through the Project Euler Nim variants.

Using the Sprague-Grundy theorem, (I like this blog post a lot!) this problem becomes trivial.

We know that if we can find the Grundy numbers for the 1 heap version of this game, then we can simply XOR the 3 Grundy numbers for each triple (a, b, c) and if the result is 0, then the position is losing for the next player.

Finding the Grundy numbers for the 1 heap version is also extremely easy, it is simply Grundy(x) = mex{Grundy(x - a) : 1 ⩽ a ⩽ x} where Grundy(0) = 0, since an empty heap is a losing position for whoever starts.

We calculate a few mor examples:

1. Grundy(1) = mex{Grundy(0)} = mex{0} = 1

   1. The player who starts wins

2. Grundy(2) = mex{Grundy(1)} = mex{1} = 0

   1. The player who starts loses

3. Grundy(3) = mex{Grundy(2)} = mex{0} = 1

   1. The player who starts wins

4. Grundy(4) = mex{Grundy(0), Grundy(3)} = {0, 1} = 2

   1. Player who starts wins by taking 4 from the pile. If we take 1 we move to a position with Grundy number 1, which means the next player can force a win

But lets says we have the Nim Square game with position (3, 3, 4) then since 1 XOR 1 XOR 2 = 2, this is a winning position. We get the winning sequence by removing 4 from the last pile resulting in (3, 3, 0) which has a Grundy value of 1 XOR 1 XOR 0 = 0, hence losing for the current player!

This already gives us a O(N^3) way to solve this problem by simply calculating the Grundy value for each triple.

This is too slow, but it is not difficult to come up with a better idea. From Problem 301 we know a^b = 0 iff a=b, which means Grundy(a) ^ (Grundy(b) ^ Grundy(c)) = 0 iff Grundy(a) = Grundy(b) ^ Grundy(c), then we for each a, the number of pairs (b, c) such that Grundy(a) = Grundy(b) ^ Grundy(c) is the number of losing positions, but we must be careful since we must have a⩽b⩽c. 

I did this by iterating a backwards, then let b = a and compute Grundy(b) ^ Grundy(c) for all b⩽c⩽100,000 keeping it in a frequency dictionary. That is freq[x] = number of pairs (b, c), where b⩽c and Grundy(b) ^ Grundy(c) = x.
This means that for each a we can find the number of pairs (b, c) such that Grundy(a) = Grundy(b) ^ Grundy(c) where a⩽b⩽c.