Detailed mathematical approach

Problem Summary

A Partisan Nim position can be written as two integer partitions

$A=(a_1\ge a_2\ge \cdots \ge a_{v_A}\ge 1),\qquad B=(b_1\ge b_2\ge \cdots \ge b_{v_B}\ge 1),$

one partition for each side's nonempty heaps. Let

$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j.$

For \(N=5000\), the implementation counts all ordered positions with \(t_A+t_B\le N\) that satisfy the exact game-specific criterion

$v_B\le v_A-2\quad\text{or}\quad\bigl(v_B=v_A-1\text{ and }t_A\equiv t_B\pmod 2\bigr).$

The answer is required modulo \(1234567891\). The crucial simplification is that after reaching this classification, the detailed shapes of \(A\) and \(B\) matter only through how many partitions realize a given total \(t\) with a given number of parts \(v\).

Mathematical Approach

The whole problem therefore becomes a structured counting problem on integer partitions. Once the state is summarized by \((t_A,v_A,t_B,v_B)\), the remaining job is to count how many partition pairs produce each admissible quadruple.

Encoding a Position by Totals and Heap Counts

Sorting the heaps on each side turns every state into an ordered pair of partitions \(A\) and \(B\). For counting purposes, two statistics matter:

$t= \text{total number of counters},\qquad v=\text{number of nonempty heaps}.$

So we want a table that tells us, for every \(t\) and \(v\), how many partitions of \(t\) use exactly \(v\) positive parts. Denote this quantity by \(g(t,v)\).

A Dynamic Program for Exact Part Counts

Introduce \(P(u,s)\), the number of partitions of \(s\) into at most \(u\) positive parts. The empty partition gives the base value

$P(0,0)=1,\qquad P(0,s)=0\ \text{for}\ s>0.$

For \(u\ge 1\), split partitions of \(s\) into two groups: those using at most \(u-1\) parts, and those using exactly \(u\) parts. In the second group, subtract 1 from each of the \(u\) parts; this removes \(u\) counters and leaves a partition of \(s-u\) into at most \(u\) parts. Therefore

$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$

Now take a partition of \(t\) into exactly \(v\) positive parts and subtract 1 from every part. What remains is a partition of \(t-v\) into at most \(v\) parts. This gives the exact-part identity

$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$

with \(g(0,0)=1\) and \(g(t,v)=0\) when \(v>t\).

The Two Branches of the Count

The implementations use the theorem that an ordered state \((A,B)\) is counted exactly in the following two cases:

$v_B\le v_A-2,$

or

$v_B=v_A-1\quad\text{and}\quad t_B\equiv t_A\pmod 2.$

That splits the answer into two sums. The first branch is

$C_{\ge 2}=\sum_{t_A=0}^{N}\sum_{v_A=0}^{t_A} g(t_A,v_A)\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B).$

The second branch is

$C_{=1}=\sum_{t_A=1}^{N}\sum_{v_A=1}^{t_A} g(t_A,v_A)\sum_{\substack{0\le t_B\le N-t_A\\ t_B\equiv t_A\pmod 2}} g(t_B,v_A-1).$

Hence the final result is

$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$

The important invariant is that within each branch, only the totals \(t_A,t_B\), the heap counts \(v_A,v_B\), and one parity condition survive. No further information about the actual part sizes is needed.

Collapsing the Inner Sums

A direct fourfold summation would be too slow, so the formulas are reorganized with prefix sums. For the first branch, define

$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w).$

Then

$C_{\ge 2}=\sum_{t_A=0}^{N}\sum_{v_A=0}^{t_A} g(t_A,v_A)\,H_{v_A}(N-t_A).$

For the parity-sensitive branch, define

$E_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ even}}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ odd}}} g(r,v-1).$

Then

$C_{=1}=\sum_{v_A=1}^{N}\sum_{t_A=v_A}^{N} g(t_A,v_A)\times \begin{cases} E_{v_A}(N-t_A), & t_A\text{ even},\\ O_{v_A}(N-t_A), & t_A\text{ odd}. \end{cases}$

This is exactly why the implementations can stay quadratic instead of falling back to a slower nested enumeration.

Worked Example

Take

$A=(4,2,1),\qquad B=(3,2).$

Then \(t_A=7\), \(v_A=3\), \(t_B=5\), and \(v_B=2\). Here \(v_B=v_A-1\), and both totals are odd, so this position belongs to the second branch. For any budget \(N\ge 12\), every ordered pair of partitions with these same statistics is counted.

How many such pairs are there? We have

$g(7,3)=4,\qquad g(5,2)=2,$

because the partitions of 7 into 3 parts are \((5,1,1)\), \((4,2,1)\), \((3,3,1)\), \((3,2,2)\), and the partitions of 5 into 2 parts are \((4,1)\), \((3,2)\). So this parameter class contributes \(4\cdot 2=8\) ordered states. If we changed \(B\) to total 4 with the same heap count \(v_B=2\), the parity condition would fail and that whole class would disappear from \(C_{=1}\).

How the Code Works

The C++, Python, and Java implementations all follow the same pipeline: build the partition tables, convert them into exact heap-count data, and then accumulate the two branches of the theorem under modular arithmetic.

Build the Partition Tables

The first table stores \(P(u,s)\) for every \(0\le u,s\le N\). Once that is complete, the implementation derives \(g(t,v)=P(v,t-v)\) for every admissible pair \((t,v)\). After \(g\) has been filled, the original partition table is no longer needed and can be discarded.

Accumulate the \(v_B\le v_A-2\) Branch

For each possible heap count \(v_A\), the implementation maintains a running total over all smaller heap counts \(v_B\le v_A-2\). A prefix sum over the total \(t_B\) then makes the inner query

$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B)$

available in \(O(1)\) time. Multiplying that by \(g(t_A,v_A)\) and sweeping over all \((t_A,v_A)\) evaluates the first branch.

Accumulate the Parity Branch

For the case \(v_B=v_A-1\), the only extra condition is parity. So for each \(v_A\), the implementation builds two prefix totals for \(g(t_B,v_A-1)\): one over even \(t_B\) and one over odd \(t_B\). When a particular \(t_A\) is processed, the code simply selects the matching parity prefix at \(N-t_A\) and multiplies by \(g(t_A,v_A)\).

Every addition and multiplication is reduced modulo \(1234567891\), so the tables never need arbitrary-precision arithmetic.

Complexity Analysis

Building \(P(u,s)\) requires \(O(N^2)\) time and \(O(N^2)\) memory. Filling the exact-part table \(g(t,v)\) is another \(O(N^2)\) pass. The two accumulation phases are also \(O(N^2)\): each heap count \(v_A\) triggers only linear scans in the total parameter.

So the complete algorithm runs in \(O(N^2)\) time and uses \(O(N^2)\) memory, with only \(O(N)\) extra workspace for running and prefix sums. That is the right scale for \(N=5000\); a naive four-parameter enumeration would be far slower.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=939
2. Partisan games: Wikipedia - Partisan game
3. Integer partitions: Wikipedia - Integer partition
4. Dynamic programming: Wikipedia - Dynamic programming
5. Parity: Wikipedia - Parity