Detailed mathematical approach

Problem Summary

A position is an integer partition \(\lambda=(s_1,\dots,s_t)\) of \(n\), where each part is a heap size. For a fixed parameter \(k\), one move chooses one heap and replaces it by any partition of that heap into between \(2\) and \(k\) nonempty heaps. Let \(F_k(n)\) denote the number of winning partitions of \(n\) under normal play. The required quantity is

$g(n)=\sum_{k=2}^{n}F_k(n),$

evaluated at \(n=200\) modulo \(10^9+7\). The solution does not enumerate all game trees of all partitions directly. Instead, it first determines the single-heap Sprague-Grundy laws and then counts whole partitions by XOR dynamic programming.

Mathematical Approach

For a partition \(\lambda=(s_1,\dots,s_t)\), let \(\operatorname{sg}_k(s)\) be the Sprague-Grundy value of one heap of size \(s\) in the version with parameter \(k\). By the Sprague-Grundy theorem, \(\lambda\) is losing exactly when

$\operatorname{sg}_k(s_1)\oplus \operatorname{sg}_k(s_2)\oplus \cdots \oplus \operatorname{sg}_k(s_t)=0.$

So the problem has two layers: determine \(\operatorname{sg}_k(s)\), then count the partitions of \(n\) whose heap nim-sum is zero.

Step 1: Reduce Each Partition to a Nim-Sum

If we write

$L_k(n)=\#\left\{\lambda\vdash n:\bigoplus_{s\in\lambda}\operatorname{sg}_k(s)=0\right\},$

then \(L_k(n)\) counts the losing partitions, while the winning partitions are

$F_k(n)=p(n)-L_k(n),$

where \(p(n)\) is the ordinary partition number. Therefore \(g(n)\) can be found once we know the heap Grundy values and can count XOR-zero partitions for each relevant \(k\).

Step 2: Closed Form for \(k=2\)

When only two-way splits are allowed, a heap of size \(s\) can move to \(a+(s-a)\) with \(1\le a\le s-1\). The implementations use the exact law

$\operatorname{sg}_2(s)=\begin{cases} 1,&s\equiv 0\pmod{2},\\ 0,&s\equiv 1\pmod{2}, \end{cases}\qquad s\ge1.$

The induction is short. Assume the rule holds below \(s\). If \(s\) is even, every split has two parts of the same parity, so every option has xor \(0\), hence the mex is \(1\). If \(s\) is odd, every split has one odd and one even part, so every option has xor \(1\), hence the mex is \(0\).

This means that for \(k=2\), a partition is losing exactly when it contains an even number of even parts.

Step 3: Exact Recurrence for \(k=3\)

For three-way scattering, a heap of size \(s\) may be split into either two or three positive parts. There is no extra closed form in the implementations; instead they compute the Sprague-Grundy table directly from the mex definition:

$\operatorname{sg}_3(s)=\operatorname{mex}\Bigl(A_2(s)\cup A_3(s)\Bigr),$

with

$A_2(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(s-a):1\le a\le s-1\right\},$

$A_3(s)=\left\{\operatorname{sg}_3(a)\oplus \operatorname{sg}_3(b)\oplus \operatorname{sg}_3(c):a+b+c=s,\ a,b,c\ge1\right\}.$

Starting from \(\operatorname{sg}_3(1)=0\), this gives the initial values

$0,1,2,3,1,4,3,2,4,5,\dots$

for heap sizes \(1,2,3,4,5,6,7,8,9,10,\dots\). Since the target is only \(n=200\), tabulating these values once is easily fast enough.

Step 4: Saturation for All \(k\ge4\)

Once four-way splits are allowed, the single-heap game settles into the exact linear rule

$\operatorname{sg}_k(s)=s-1\qquad (k\ge4,\ s\ge1).$

The reason is that the mex saturates. Every move from a heap of size \(s\) creates \(r\ge2\) positive heaps \(x_1,\dots,x_r\), so under the linear law the option value is

$\bigoplus_{i=1}^{r}(x_i-1).$

This xor is always at most the ordinary sum, and therefore

$\bigoplus_{i=1}^{r}(x_i-1)\le \sum_{i=1}^{r}(x_i-1)=s-r\le s-2,$

so \(s-1\) is not reachable in one move. The four-way regime is already rich enough to realize every nimber from \(0\) through \(s-2\), which forces the mex to be exactly \(s-1\). Consequently all parameters \(k=4,5,\dots,n\) lead to the same partition-counting problem.

Step 5: Count Losing Partitions by XOR Dynamic Programming

For a fixed \(k\), define a table \(D_k(t,x)\) as the number of partitions of total \(t\) whose heap Grundy xor equals \(x\). The initial condition is

$D_k(0,0)=1.$

Now process heap sizes \(s=1,2,\dots,n\) one by one. Because partitions are multisets, the update is the standard unbounded-partition order:

$D_k(t,\ x\oplus \operatorname{sg}_k(s))\mathrel{+}=D_k(t-s,\ x)\qquad (t\ge s).$

Iterating totals in increasing order allows the same size \(s\) to appear any number of times. When all heap sizes have been processed, the losing count is

$L_k(n)=D_k(n,0).$

The ordinary partition number \(p(n)\) is computed with the same coin-change idea but without the xor dimension, so finally

$F_k(n)=p(n)-L_k(n)\pmod{10^9+7}.$

Step 6: Collapse the Sum over \(k\)

The three regimes above imply that only three distinct counting problems remain:

$k=2,\qquad k=3,\qquad k\ge4.$

Therefore

$g(n)=F_2(n)+F_3(n)+(n-3)F_4(n).$

This is the decisive simplification: instead of solving \(n-1\) different games, the program solves only three.

Worked Example: \(n=5\)

The partitions of \(5\) are

$5,\ 4+1,\ 3+2,\ 3+1+1,\ 2+2+1,\ 2+1+1+1,\ 1+1+1+1+1,$

so \(p(5)=7\).

For \(k=2\), the heap values are \(0,1,0,1,0\) on sizes \(1\) through \(5\). A partition is losing iff it contains an even number of even parts, so the winning partitions are

$4+1,\qquad 3+2,\qquad 2+1+1+1,$

hence \(F_2(5)=3\).

For \(k=3\), the recurrence above gives

$\operatorname{sg}_3(1),\dots,\operatorname{sg}_3(5)=0,1,2,3,1.$

The only losing partitions are then

$2+2+1,\qquad 1+1+1+1+1,$

so \(F_3(5)=5\).

For every \(k\ge4\), the rule \(\operatorname{sg}_k(s)=s-1\) gives heap values \(0,1,2,3,4\), and the same two partitions remain losing, so \(F_4(5)=5\). Therefore

$g(5)=F_2(5)+F_3(5)+2F_4(5)=3+5+2\cdot 5=18.$

This small case matches the checkpoint values used by the implementations.

How the Code Works

The C++, Python, and Java implementations follow the same plan. They first compute \(p(n)\) with the standard partition DP. Next they build three single-heap Grundy tables: the parity rule for \(k=2\), the direct mex table for \(k=3\), and the linear table \(s-1\) for the saturated regime \(k\ge4\).

For each of those three tables, the implementation runs a second DP over total sum and xor-state. The xor dimension has width \(256\), which is enough for every Grundy value that appears up to heap size \(200\). The count of losing partitions is the state with total \(n\) and xor \(0\), and subtracting that from \(p(n)\) yields the winning count for the regime.

Finally the program combines the three contributions as

$F_2(n)+F_3(n)+(n-3)F_4(n)\pmod{10^9+7}.$

It also checks small control values such as \(F_2(5)=3\), \(F_3(5)=5\), \(g(7)=66\), and \(g(10)=291\) before producing the final value for \(n=200\).

Complexity Analysis

Let \(n\) be the target heap total and let \(X=256\) be the xor-state width. Computing the partition numbers costs \(O(n^2)\) time. Building the \(k=2\) and \(k\ge4\) Grundy tables is linear, while the direct mex recurrence for \(k=3\) costs \(O(n^3)\) time because each heap size scans all two-part and three-part splits. Each XOR-partition DP costs \(O(n^2X)\) time and \(O(nX)\) memory, and this is done for three regimes. Hence the overall complexity is

$O(n^3+n^2X)\ \text{time},\qquad O(nX)\ \text{memory},$

which is entirely practical for \(n=200\).

Footnotes and References

1. Problem page: https://projecteuler.net/problem=629
2. Sprague-Grundy theorem: Wikipedia — Sprague-Grundy theorem
3. Integer partition: Wikipedia — Integer partition
4. Minimum excluded value (mex): Wikipedia — mex
5. Nim: Wikipedia — Nim