Detailed mathematical approach

Problem Summary

We study an impartial heap game in which a heap of size \(n\) may be changed in two ways: remove \(1\), \(2\), \(4\), or \(9\) counters, or split the heap into two positive heaps whose sizes add up to \(n\). For the large parameters \(N=12{,}491{,}249\) and \(m=1249\), the required quantity \(S(N,m)\) is the number of size-\(m\) multisets of heap sizes chosen from \(\{1,2,\dots,N\}\) whose combined position is losing, taken modulo \(912491249\).

By the Sprague-Grundy theorem, a disjoint sum of heaps is losing exactly when the xor of the single-heap Grundy values is \(0\). The whole problem therefore becomes: compute the Grundy value \(g(n)\) for one heap, understand how often each Grundy value appears among \(1\le n\le N\), and count size-\(m\) multisets whose xor is zero.

Mathematical Approach

The implementations combine game theory, eventual periodicity, and a compact xor dynamic program. The key point is that the huge bound \(N\) is handled through periodic structure, not by computing every \(g(n)\) all the way to \(N\).

Step 1: Write the Single-Heap Grundy Recurrence

Let \(g(n)\) be the Grundy value of one heap of size \(n\). Then \(g(0)=0\), and for \(n\ge 1\) every legal move contributes one reachable Grundy value. The subtraction moves contribute \(g(n-1)\), \(g(n-2)\), \(g(n-4)\), and \(g(n-9)\) whenever the index is nonnegative. A split \(n=a+(n-a)\) contributes the xor \(g(a)\oplus g(n-a)\).

Therefore

$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$

The upper limit \(\lfloor n/2\rfloor\) is enough because the split \(a,n-a\) is the same position as \(n-a,a\). Computing the first values gives

$g(1..10)=1,2,0,3,4,6,1,2,5,3.$

These initial values already show that the sequence is nontrivial: subtraction moves alone would be much simpler, but the split move injects xor structure into the recurrence.

Step 2: Separate Even and Odd Indices and Exploit Periodicity

The implementations do not try to prove a closed form for \(g(n)\). Instead they compute a long prefix and then look for eventual periodicity separately in the even and odd subsequences

$e_k=g(2k),\qquad o_k=g(2k-1).$

This parity split is exactly what works in practice. The computed data show that the even subsequence becomes periodic with period \(79\) after the first \(22\) even terms, while the odd subsequence becomes periodic with period \(70\) after the first \(161\) odd terms.

If \(c_r(N)\) denotes the number of heap sizes \(n\in[1,N]\) with Grundy value \(r\), then

$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$

For each parity subsequence, once a preperiod and a period are known, the count of any value \(r\) among the first \(T\) terms is obtained by prefix plus whole cycles plus a short tail. That turns the enormous value \(N=12{,}491{,}249\) into a straightforward counting exercise.

Step 3: Collapse Heap Sizes into Grundy Classes

After periodic counting, all heap sizes are grouped only by their Grundy value. Let

$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$

Now consider one fixed class \(r\). There are \(c_r\) distinct heap sizes inside this class, and the game position allows repeated heap sizes, so choosing exactly \(k\) heaps from that class is a multiset-counting problem. The number of possibilities is

$\binom{c_r+k-1}{k}.$

This is the usual combinations-with-repetition formula, equivalently the coefficient of \(z^k\) in

$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$

The xor contribution of those \(k\) heaps is especially simple: since \(r\oplus r=0\), the total xor from class \(r\) is \(0\) when \(k\) is even and \(r\) when \(k\) is odd.

Step 4: Run a Dynamic Program on Xor and Heap Count

Process the Grundy classes one by one. Let \(DP[\xi][t]\) be the number of ways to choose \(t\) heaps from the classes processed so far so that the current xor is \(\xi\). Initially, before any class is used,

$DP[0][0]=1.$

When the class \(r\) is added, choosing \(k\) heaps from it changes the count by \(k\) and changes the xor only according to the parity of \(k\). Thus the transition is

$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{for even }k,$

$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{for odd }k.$

After every Grundy class has been processed, the answer is

$S(N,m)=DP[0][m]\pmod{912491249}.$

The computed prefix shows that only Grundy values \(0\) through \(10\) occur, so the xor state space has size \(16\), which keeps the dynamic program compact.

Step 5: Worked Example \((N,m)=(10,2)\)

Using the first ten Grundy values

$g(1..10)=1,2,0,3,4,6,1,2,5,3,$

the class counts are

$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$

With exactly two heaps, the total xor is \(0\) precisely when both chosen heaps come from the same Grundy class. So

$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$

This matches the dynamic-program interpretation perfectly: every class contributes its even-sized selections to xor \(0\), and for \(m=2\) that means selecting two heaps from one class.

How the Code Works

The implementation first computes a prefix of the Grundy sequence up to \(20000\). For each heap size it gathers all reachable Grundy values into a bit mask and then takes the mex. That gives both the sequence itself and the maximum Grundy value appearing in the prefix.

Next it extracts the even-indexed and odd-indexed subsequences and searches for a short period in each one. Candidate periods up to \(300\) are tested, the tail is required to contain at least six consecutive repetitions, and then the start is moved left to the earliest index where the same period still works. In the final data this yields period \(79\) starting after \(22\) even terms and period \(70\) starting after \(161\) odd terms.

Using those periodic descriptions, the implementation counts how many times each Grundy value occurs in \(\{1,\dots,N\}\). For each class size \(c_r\), it then builds the coefficients \(\binom{c_r+k-1}{k}\bmod 912491249\) for \(0\le k\le m\). The coefficients are split into even-\(k\) and odd-\(k\) lists so that the xor update is just “stay in the same mask” or “toggle by \(r\)”.

Finally, a rolling two-layer dynamic program over xor masks and selected-heap count is executed. Since the observed Grundy values lie in \(0,\dots,10\), only \(16\) xor masks are needed, and the answer is the entry with xor \(0\) and total size \(1249\).

Complexity Analysis

Let \(M=20000\) be the precomputation cutoff, let \(R\) be the number of Grundy classes actually used, and let \(X\) be the number of xor masks. The Grundy prefix computation costs

$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$

time, because every \(n\) checks all splits up to \(n/2\), and it uses \(O(M)\) memory for the stored sequence. The period search over the even and odd subsequences is much smaller and is negligible compared with the quadratic prefix build.

The counting stage after periodic compression is linear in the period lengths. The main combinatorial stage uses a dynamic program of size \(X\times (m+1)\), updated for each class over all \(k\le m\), so its running time is \(O(RXm^2)\) and its memory use is \(O(Xm)\). In this problem \(R=11\) and \(X=16\), so the practical bottleneck is the one-time Grundy precomputation, not the final xor DP.

Footnotes and References

1. Problem page: Project Euler 888
2. Sprague-Grundy theorem: Wikipedia - Sprague-Grundy theorem
3. Mex function in combinatorial game theory: Wikipedia - mex
4. Nim and xor evaluation: Wikipedia - Nim
5. Combinations with repetition: Wikipedia - combinations with repetition