Project Euler Problem 939

Solution

Answer: 246776732

Let a partition on one side have:

total stones $n$,
number of piles $k$,
$r\in{0,1}$ = parity of the number of odd piles.

Define

$$v=n-k.$$

Using combinatorial game theory, each pile contributes a combination of the infinitesimal game $\uparrow$ and possibly a star $*$. For a whole position:

$$M=v_A-v_B,\qquad S=r_A\oplus r_B.$$

Then A wins regardless of who starts iff:

$S=0$ and $M\ge 1$,
or $S=1$ and $M\ge 2$.

So the problem reduces to counting partitions by $(n,k,r)$.

The partition DP is:

$$f[n,k,r] = f[n-1,k-1,r\oplus 1] + f[n-k,k,r\oplus (k\bmod 2)].$$

This counts partitions of $n$ into $k$ parts while tracking parity of odd parts.

Implementing the optimized $O(N^2)$ algorithm for $N=5000$ gives:

$$E(5000)\bmod 1234567891 = 246776732.$$

Answer: 246776732