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\).
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.
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)\).
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 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.
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.
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}\).
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.
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.
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.
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.
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.
Eine Stellung von Partisan Nim kann als zwei ganzzahlige Partitionen geschrieben werden:
$$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),$$
je eine Partition für die nichtleeren Haufen jeder Seite. Setze
$$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j.$$
Für \(N=5000\) zählt die Implementierung alle geordneten Stellungen mit \(t_A+t_B\le N\), die genau das Kriterium
$$v_B\le v_A-2\quad\text{oder}\quad\bigl(v_B=v_A-1\text{ und }t_A\equiv t_B\pmod 2\bigr)$$
erfüllen. Das Ergebnis wird modulo \(1234567891\) gesucht. Die entscheidende Vereinfachung ist, dass nach dieser Klassifikation die exakten Haufengrößen nur noch über die Anzahl der Partitionen mit gegebenem Gesamtwert \(t\) und gegebener Teilezahl \(v\) eingehen.
Damit wird das Spielproblem zu einer präzisen Zählaufgabe über Partitionen. Sobald eine Stellung durch \((t_A,v_A,t_B,v_B)\) beschrieben ist, muss man nur noch ausrechnen, wie viele Partitionspaare zu jedem zulässigen Vierer-Tupel gehören.
Sortiert man die Haufen auf beiden Seiten, erhält man ein geordnetes Paar von Partitionen \(A\) und \(B\). Für die Zählung sind zwei Größen wichtig:
$$t=\text{Gesamtzahl der Steine},\qquad v=\text{Anzahl der nichtleeren Haufen}.$$
Gesucht ist also eine Tabelle, die für jedes \(t\) und \(v\) angibt, wie viele Partitionen von \(t\) genau \(v\) positive Teile besitzen. Diese Zahl nennen wir \(g(t,v)\).
Definiere \(P(u,s)\) als die Anzahl der Partitionen von \(s\) in höchstens \(u\) positive Teile. Die leere Partition liefert
$$P(0,0)=1,\qquad P(0,s)=0\ \text{für}\ s>0.$$
Für \(u\ge 1\) teilt man die Partitionen von \(s\) in zwei Gruppen: solche mit höchstens \(u-1\) Teilen und solche mit genau \(u\) Teilen. Im zweiten Fall zieht man von jedem der \(u\) Teile 1 ab; dadurch verschwinden \(u\) Steine und es bleibt eine Partition von \(s-u\) in höchstens \(u\) Teile. Also gilt
$$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$$
Nimmt man nun eine Partition von \(t\) in genau \(v\) positive Teile und zieht von jedem Teil 1 ab, so bleibt eine Partition von \(t-v\) in höchstens \(v\) Teile. Damit folgt
$$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$$
mit \(g(0,0)=1\) und \(g(t,v)=0\), falls \(v>t\).
Die Implementierungen benutzen den Satz, dass eine geordnete Stellung \((A,B)\) genau in zwei Fällen gezählt wird:
$$v_B\le v_A-2,$$
oder
$$v_B=v_A-1\quad\text{und}\quad t_B\equiv t_A\pmod 2.$$
Dadurch zerfällt die Antwort in zwei Summen. Der erste Zweig ist
$$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).$$
Der zweite Zweig ist
$$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).$$
Somit gilt insgesamt
$$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$$
Die zentrale Invariante lautet: Innerhalb dieser Formeln zählt nur noch \(t_A,t_B,v_A,v_B\) sowie eine Paritätsbedingung. Die konkrete Form der Partitionen spielt darüber hinaus keine Rolle mehr.
Eine direkte vierfache Summation wäre zu langsam. Daher werden Präfixsummen verwendet. Für den ersten Zweig definiert man
$$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w).$$
Dann wird
$$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).$$
Für den paritätssensitiven Zweig definiert man
$$E_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ gerade}}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ ungerade}}} g(r,v-1).$$
Damit gilt
$$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{ gerade},\\ O_{v_A}(N-t_A), & t_A\text{ ungerade}. \end{cases}$$
Genau dadurch bleiben die Implementierungen quadratisch und vermeiden eine deutlich langsamere Verschachtelung.
Betrachte
$$A=(4,2,1),\qquad B=(3,2).$$
Dann sind \(t_A=7\), \(v_A=3\), \(t_B=5\) und \(v_B=2\). Also gilt \(v_B=v_A-1\), und beide Summen sind ungerade. Die Stellung gehört damit zum zweiten Zweig. Für jedes \(N\ge 12\) wird jedes geordnete Partitionspaar mit genau diesen Kenndaten gezählt.
Wie viele sind das? Es gilt
$$g(7,3)=4,\qquad g(5,2)=2,$$
denn die Partitionen von 7 in 3 Teile sind \((5,1,1)\), \((4,2,1)\), \((3,3,1)\), \((3,2,2)\), und die Partitionen von 5 in 2 Teile sind \((4,1)\), \((3,2)\). Daher liefert diese Parameterklasse \(4\cdot 2=8\) geordnete Stellungen. Würde man \(B\) bei gleicher Haufenanzahl auf Gesamtwert 4 ändern, dann scheitert die Paritätsbedingung und die gesamte Klasse verschwindet aus \(C_{=1}\).
Die Implementierungen in C++, Python und Java folgen demselben Ablauf: zuerst die Partitionstabellen aufbauen, dann in exakte Haufenanzahlen umwandeln und anschließend die beiden Zweige des Satzes modulo \(1234567891\) aufsummieren.
Die erste Tabelle speichert \(P(u,s)\) für alle \(0\le u,s\le N\). Danach wird daraus für jedes zulässige Paar \((t,v)\) der Wert \(g(t,v)=P(v,t-v)\) erzeugt. Sobald \(g\) vollständig vorliegt, wird die ursprüngliche Tabelle nicht mehr benötigt.
Für jede mögliche Haufenanzahl \(v_A\) hält die Implementierung eine laufende Summe über alle kleineren Haufenanzahlen \(v_B\le v_A-2\). Eine Präfixsumme über \(t_B\) liefert dann die innere Anfrage
$$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B)$$
in \(O(1)\) Zeit. Multipliziert man das mit \(g(t_A,v_A)\) und iteriert über alle \((t_A,v_A)\), so erhält man den ersten Zweig.
Im Fall \(v_B=v_A-1\) bleibt nur noch die Paritätsbedingung. Deshalb baut die Implementierung für jedes \(v_A\) zwei Präfixsummen von \(g(t_B,v_A-1)\): eine über gerade \(t_B\) und eine über ungerade \(t_B\). Für ein gegebenes \(t_A\) wird dann einfach die passende Präfixsumme an der Stelle \(N-t_A\) gewählt und mit \(g(t_A,v_A)\) multipliziert.
Alle Additionen und Multiplikationen werden sofort modulo \(1234567891\) reduziert; beliebig große Ganzzahlen sind also nicht erforderlich.
Der Aufbau von \(P(u,s)\) kostet \(O(N^2)\) Zeit und \(O(N^2)\) Speicher. Das Füllen der exakten Tabelle \(g(t,v)\) ist ein weiterer \(O(N^2)\)-Durchlauf. Auch die beiden Summationsphasen sind \(O(N^2)\), denn jede Haufenanzahl \(v_A\) führt nur zu linearen Durchläufen über den Gesamtwert.
Damit arbeitet der gesamte Algorithmus in \(O(N^2)\) Zeit und \(O(N^2)\) Speicher, mit nur \(O(N)\) zusätzlichem Arbeitsraum für laufende Summen und Präfixsummen. Für \(N=5000\) ist genau das die passende Größenordnung; eine naive Enumeration über alle vier Parameter wäre deutlich langsamer.
Partisan Nim'de bir konum iki tamsayı partition'ı olarak yazılabilir:
$$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),$$
yani iki tarafın boş olmayan yığınlarını gösteren iki sıralı liste. Şimdi
$$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j$$
olsun. \(N=5000\) için uygulama, \(t_A+t_B\le N\) koşulunu sağlayan ve tam olarak şu ölçüte uyan bütün sıralı konumları sayar:
$$v_B\le v_A-2\quad\text{veya}\quad\bigl(v_B=v_A-1\text{ ve }t_A\equiv t_B\pmod 2\bigr).$$
Sonuç \(1234567891\) modunda istenir. Temel sadeleşme şudur: bu sınıflandırmaya ulaşıldıktan sonra \(A\) ve \(B\)'nin ayrıntılı şekli değil, yalnızca belirli bir toplam \(t\) ve parça sayısı \(v\) için kaç farklı partition bulunduğu önemlidir.
Böylece oyun problemi, partition sayıları üzerinde yapılan net bir sayım problemine dönüşür. Bir durum \((t_A,v_A,t_B,v_B)\) ile özetlenince yapılacak iş, bu izinli parametre dörtlülerinin her biri için kaç sıralı partition çifti bulunduğunu hesaplamaktır.
Her iki taraftaki yığınlar büyükten küçüğe sıralandığında durum bir \(A\) ve \(B\) partition çifti olur. Sayım açısından iki istatistik yeterlidir:
$$t=\text{toplam taş sayısı},\qquad v=\text{boş olmayan yığın sayısı}.$$
Bu nedenle her \(t\) ve \(v\) için, \(t\)'yi tam olarak \(v\) pozitif parçaya ayıran partition sayısını veren bir tabloya ihtiyacımız var. Buna \(g(t,v)\) diyelim.
\(P(u,s)\) ile, \(s\)'nin en fazla \(u\) pozitif parçaya ayrılma sayısını gösterelim. Boş partition taban durumu verir:
$$P(0,0)=1,\qquad P(0,s)=0\ \text{ eğer }\ s>0.$$
\(u\ge 1\) için \(s\)'nin partition'larını iki gruba ayırırız: en fazla \(u-1\) parçalı olanlar ve tam \(u\) parçalı olanlar. İkinci grupta her parçadan 1 çıkarırsak toplamdan \(u\) eksilir ve geriye \(s-u\)'nun en fazla \(u\) parçalı bir partition'ı kalır. Bu yüzden
$$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$$
Şimdi \(t\)'nin tam \(v\) pozitif parçalı bir partition'ından her parçaya 1 azaltma uygularsak, \(t-v\)'nin en fazla \(v\) parçalı bir partition'ını elde ederiz. Dolayısıyla
$$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$$
ve ayrıca \(g(0,0)=1\), \(v>t\) ise \(g(t,v)=0\).
Uygulamaların kullandığı oyun-teorik karakterizasyon şudur: sıralı bir \((A,B)\) konumu tam olarak şu iki durumda sayılır:
$$v_B\le v_A-2,$$
veya
$$v_B=v_A-1\quad\text{ve}\quad t_B\equiv t_A\pmod 2.$$
Böylece cevap iki toplama ayrılır. Birinci dal
$$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)$$
şeklindedir. İkinci dal ise
$$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).$$
Sonuç olarak
$$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$$
Buradaki temel invariant, gerçek yığın boyutlarının yalnızca \(t_A,t_B,v_A,v_B\) ve tek bir parity koşulu üzerinden etkili olmasıdır; bunun ötesinde ayrı bir şekil bilgisine ihtiyaç yoktur.
Doğrudan dört katmanlı toplama yavaş olur. Bu yüzden formüller prefix sum ile yeniden yazılır. Birinci dal için
$$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w)$$
tanımlanır. O zaman
$$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)$$
olur. Parity koşullu dal için de
$$E_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ çift}}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ tek}}} g(r,v-1)$$
tanımlarını yaparız. Böylece
$$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{ çift},\\ O_{v_A}(N-t_A), & t_A\text{ tek}. \end{cases}$$
Bu dönüşüm yüzünden uygulamalar kübik ya da daha kötü değil, kuadratik karmaşıklıkta kalır.
Şu konumu alalım:
$$A=(4,2,1),\qquad B=(3,2).$$
Burada \(t_A=7\), \(v_A=3\), \(t_B=5\) ve \(v_B=2\). Yani \(v_B=v_A-1\) ve her iki toplam da tek olduğu için bu durum ikinci dala girer. \(N\ge 12\) olduğu her durumda, bu istatistiklere sahip bütün sıralı partition çiftleri sayılır.
Bunların sayısı nedir? Şunlar vardır:
$$g(7,3)=4,\qquad g(5,2)=2.$$
Çünkü 7'nin 3 parçalı partition'ları \((5,1,1)\), \((4,2,1)\), \((3,3,1)\), \((3,2,2)\); 5'in 2 parçalı partition'ları ise \((4,1)\) ve \((3,2)\)'dir. Dolayısıyla bu parametre sınıfı \(4\cdot 2=8\) sıralı konum katkısı yapar. Eğer \(B\)'nin toplamı 4 olup yine \(v_B=2\) olsaydı, parity koşulu bozulacağı için bu sınıf \(C_{=1}\)'den tamamen kaybolurdu.
C++, Python ve Java uygulamaları aynı akışı izler: önce partition tablolarını kurar, sonra bunları tam yığın sayısı bilgisine çevirir ve en sonunda teoremin iki dalını modüler aritmetikle toplar.
İlk tablo, tüm \(0\le u,s\le N\) için \(P(u,s)\) değerlerini tutar. Bu tablo hazır olunca her geçerli \((t,v)\) çifti için \(g(t,v)=P(v,t-v)\) hesaplanır. \(g\) tamamlandıktan sonra ilk tablo artık gerekmediği için serbest bırakılabilir.
Her olası \(v_A\) için uygulama, bütün küçük \(v_B\le v_A-2\) değerlerini kapsayan bir kümülatif toplam taşır. \(t_B\) üzerinde alınan prefix sum sayesinde
$$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B)$$
iç toplamı \(O(1)\) zamanda okunur. Bu değer \(g(t_A,v_A)\) ile çarpılıp tüm \((t_A,v_A)\) çiftleri üzerinden gezilerek birinci dal hesaplanır.
\(v_B=v_A-1\) durumunda ek bilgi yalnızca parity'dir. Bu yüzden her \(v_A\) için \(g(t_B,v_A-1)\) değerlerinin biri çift \(t_B\)'ler, diğeri tek \(t_B\)'ler için olmak üzere iki prefix toplamı hazırlanır. Belirli bir \(t_A\) işlendiğinde kod sadece doğru parity sınıfındaki prefix değerini \(N-t_A\) noktasında okur ve bunu \(g(t_A,v_A)\) ile çarpar.
Bütün toplama ve çarpımlar her adımda \(1234567891\) moduna indirgenir; bu nedenle keyfi büyüklükte tamsayılara ihtiyaç yoktur.
\(P(u,s)\) tablosunu kurmak \(O(N^2)\) zaman ve \(O(N^2)\) bellek ister. Tam parçalı tablo \(g(t,v)\)'yi doldurmak da bir başka \(O(N^2)\) geçiştir. İki ana toplama fazı yine \(O(N^2)\) düzeyindedir; çünkü her \(v_A\) için yalnızca toplam değişkeni üzerinde doğrusal taramalar yapılır.
Dolayısıyla bütün algoritma \(O(N^2)\) zamanda çalışır ve \(O(N^2)\) bellek kullanır; ek çalışma alanı ise prefix ve kümülatif toplamlar için \(O(N)\) kadardır. \(N=5000\) için doğru ölçek budur; dört parametreyi saf biçimde saymak çok daha yavaş olurdu.
Una posición de Partisan Nim puede escribirse como dos particiones enteras:
$$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),$$
una partición para los montones no vacíos de cada lado. Definimos
$$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j.$$
Para \(N=5000\), la implementación cuenta todas las posiciones ordenadas con \(t_A+t_B\le N\) que satisfacen exactamente el criterio
$$v_B\le v_A-2\quad\text{o}\quad\bigl(v_B=v_A-1\text{ y }t_A\equiv t_B\pmod 2\bigr).$$
La respuesta se toma módulo \(1234567891\). La simplificación decisiva es que, una vez alcanzada esta clasificación, la forma fina de \(A\) y \(B\) solo importa a través de cuántas particiones producen un total \(t\) con un número de partes \(v\).
Por tanto, el problema se convierte en una cuenta estructurada sobre particiones enteras. Cuando un estado queda resumido por \((t_A,v_A,t_B,v_B)\), solo falta calcular cuántos pares ordenados de particiones realizan cada cuádrupla admisible.
Si ordenamos los montones de cada lado de mayor a menor, toda posición queda representada por un par ordenado de particiones \(A\) y \(B\). Para contar, solo hacen falta dos estadísticas:
$$t=\text{número total de fichas},\qquad v=\text{número de montones no vacíos}.$$
Así que necesitamos una tabla que indique, para cada \(t\) y cada \(v\), cuántas particiones de \(t\) tienen exactamente \(v\) partes positivas. Denotemos esa cantidad por \(g(t,v)\).
Sea \(P(u,s)\) el número de particiones de \(s\) en a lo sumo \(u\) partes positivas. La partición vacía da el caso base
$$P(0,0)=1,\qquad P(0,s)=0\ \text{si}\ s>0.$$
Para \(u\ge 1\), separamos las particiones de \(s\) en dos grupos: las que usan a lo sumo \(u-1\) partes y las que usan exactamente \(u\) partes. En el segundo grupo restamos 1 a cada una de las \(u\) partes; eso elimina \(u\) fichas y deja una partición de \(s-u\) en a lo sumo \(u\) partes. Por eso
$$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$$
Ahora, si tomamos una partición de \(t\) en exactamente \(v\) partes positivas y restamos 1 a cada parte, obtenemos una partición de \(t-v\) en a lo sumo \(v\) partes. Por tanto,
$$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$$
con \(g(0,0)=1\) y \(g(t,v)=0\) cuando \(v>t\).
Las implementaciones usan el resultado de que una posición ordenada \((A,B)\) se cuenta exactamente en dos casos:
$$v_B\le v_A-2,$$
o bien
$$v_B=v_A-1\quad\text{y}\quad t_B\equiv t_A\pmod 2.$$
Eso divide la respuesta en dos contribuciones. La primera es
$$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).$$
La segunda es
$$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).$$
En consecuencia,
$$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$$
La invariante importante es que, dentro de estas fórmulas, solo sobreviven \(t_A,t_B,v_A,v_B\) y una condición de paridad. Los tamaños concretos de las partes ya no intervienen de forma adicional.
Una suma cuádruple directa sería demasiado lenta, así que las fórmulas se reorganizan con prefijos acumulados. Para la primera rama definimos
$$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w).$$
Entonces
$$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).$$
Para la rama con paridad definimos
$$E_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ par}}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ impar}}} g(r,v-1).$$
Con ello,
$$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{ par},\\ O_{v_A}(N-t_A), & t_A\text{ impar}. \end{cases}$$
Esa es exactamente la razón por la que la solución se mantiene en tiempo cuadrático y no en una enumeración anidada mucho más costosa.
Tomemos
$$A=(4,2,1),\qquad B=(3,2).$$
Entonces \(t_A=7\), \(v_A=3\), \(t_B=5\) y \(v_B=2\). Se cumple \(v_B=v_A-1\), y ambos totales son impares, así que esta posición entra en la segunda rama. Para cualquier presupuesto \(N\ge 12\), todos los pares ordenados de particiones con esas mismas estadísticas quedan contados.
¿Cuántos hay? Tenemos
$$g(7,3)=4,\qquad g(5,2)=2,$$
porque las particiones de 7 en 3 partes son \((5,1,1)\), \((4,2,1)\), \((3,3,1)\), \((3,2,2)\), y las de 5 en 2 partes son \((4,1)\), \((3,2)\). Por tanto, esta clase de parámetros aporta \(4\cdot 2=8\) posiciones ordenadas. Si en cambio \(B\) tuviera total 4 manteniendo \(v_B=2\), la condición de paridad fallaría y toda esa clase desaparecería de \(C_{=1}\).
Las implementaciones en C++, Python y Java siguen la misma secuencia: construir las tablas de particiones, convertirlas en datos por número exacto de montones y luego acumular las dos ramas del teorema usando aritmética modular.
La primera tabla almacena \(P(u,s)\) para todos los valores \(0\le u,s\le N\). Después, a partir de ella se obtiene \(g(t,v)=P(v,t-v)\) para cada par admisible \((t,v)\). Una vez completada \(g\), la tabla inicial deja de ser necesaria.
Para cada valor posible de \(v_A\), la implementación mantiene un acumulado sobre todos los valores menores \(v_B\le v_A-2\). Un prefijo sobre \(t_B\) permite responder en \(O(1)\) la consulta
$$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B).$$
Multiplicar eso por \(g(t_A,v_A)\) y recorrer todos los pares \((t_A,v_A)\) evalúa la primera contribución.
En el caso \(v_B=v_A-1\), la única condición extra es la paridad. Por eso, para cada \(v_A\), la implementación construye dos prefijos de \(g(t_B,v_A-1)\): uno sobre \(t_B\) pares y otro sobre \(t_B\) impares. Cuando se procesa un \(t_A\) concreto, el código elige el prefijo con la misma paridad en la posición \(N-t_A\) y lo multiplica por \(g(t_A,v_A)\).
Todas las sumas y multiplicaciones se reducen módulo \(1234567891\), así que no hace falta aritmética de precisión arbitraria.
Construir \(P(u,s)\) cuesta \(O(N^2)\) en tiempo y \(O(N^2)\) en memoria. Llenar la tabla exacta \(g(t,v)\) es otro recorrido \(O(N^2)\). Las dos fases de acumulación también son \(O(N^2)\), ya que cada valor de \(v_A\) solo provoca barridos lineales sobre el total.
En conjunto, el algoritmo completo trabaja en \(O(N^2)\) tiempo y usa \(O(N^2)\) memoria, con solo \(O(N)\) espacio adicional para sumas corrientes y prefijos. Esa es la escala adecuada para \(N=5000\); una enumeración ingenua de los cuatro parámetros sería mucho más lenta.
Partisan Nim 的一个局面可以写成两个整数分拆：
$$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),$$
它们分别记录两边所有非空堆的大小。记
$$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j.$$
当 \(N=5000\) 时，实现要统计所有满足 \(t_A+t_B\le N\) 的有序局面，并且这些局面必须恰好满足下面的判定条件：
$$v_B\le v_A-2\quad\text{或}\quad\bigl(v_B=v_A-1\text{ 且 }t_A\equiv t_B\pmod 2\bigr).$$
答案对 \(1234567891\) 取模。最关键的化简在于：一旦把题目降到这个判定定理，\(A\) 和 \(B\) 的具体分拆形状就不再重要，真正需要的只是“总数为 \(t\)、部分个数为 \(v\) 的分拆有多少个”。
因此，整道题被转化成一个关于整数分拆的计数问题。只要一个局面能由 \((t_A,v_A,t_B,v_B)\) 概括，剩下的工作就是计算每个允许的四元组对应多少个有序分拆对。
把每一边的堆按从大到小排序之后，一个局面就变成了分拆 \(A\) 与 \(B\) 的有序对。对计数而言，真正有用的是两个量：
$$t=\text{总棋子数},\qquad v=\text{非空堆的个数}.$$
于是我们需要一张表，给出对每个 \(t\) 与 \(v\)，把 \(t\) 拆成恰好 \(v\) 个正部分的方案数。把这个数量记为 \(g(t,v)\)。
定义 \(P(u,s)\) 为把 \(s\) 分拆成至多 \(u\) 个正部分的方案数。空分拆给出基本条件
$$P(0,0)=1,\qquad P(0,s)=0\ \text{当}\ s>0.$$
对 \(u\ge 1\)，把 \(s\) 的所有分拆分成两类：一类只用了至多 \(u-1\) 个部分，另一类恰好用了 \(u\) 个部分。对第二类中的每一个分拆，从所有 \(u\) 个部分各减去 1，就会总共去掉 \(u\) 个棋子，并留下一个把 \(s-u\) 分拆成至多 \(u\) 个正部分的方案。因此有递推式
$$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$$
现在考虑把 \(t\) 分拆成恰好 \(v\) 个正部分。若从每个部分都减去 1，就得到一个把 \(t-v\) 分拆成至多 \(v\) 个正部分的对象，所以
$$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$$
并且 \(g(0,0)=1\)，当 \(v>t\) 时 \(g(t,v)=0\)。
实现所依据的题目特定结论是：有序局面 \((A,B)\) 被计入答案，当且仅当落在下面两种情形之一：
$$v_B\le v_A-2,$$
或者
$$v_B=v_A-1\quad\text{且}\quad t_B\equiv t_A\pmod 2.$$
因此答案分成两个求和。第一部分为
$$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).$$
第二部分为
$$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).$$
于是最终结果就是
$$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$$
这里最重要的不变量是：一旦进入这两个公式，真正保留下来的信息只有 \(t_A,t_B,v_A,v_B\) 和一个奇偶性条件，分拆内部每一项的具体大小不再单独起作用。
如果直接做四重求和，速度会很差，所以需要把内部结构压缩成前缀和。对第一部分，定义
$$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w).$$
那么
$$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).$$
对带奇偶性限制的第二部分，定义
$$E_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ 为偶数}}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ 为奇数}}} g(r,v-1).$$
于是
$$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{ 为偶数},\\ O_{v_A}(N-t_A), & t_A\text{ 为奇数}. \end{cases}$$
这一步正是实现能够保持 \(O(N^2)\) 而不是退化成更慢多重枚举的原因。
考虑
$$A=(4,2,1),\qquad B=(3,2).$$
此时 \(t_A=7\)、\(v_A=3\)、\(t_B=5\)、\(v_B=2\)。这里有 \(v_B=v_A-1\)，而且两个总数都是奇数，所以这个局面属于第二个分支。只要预算 \(N\ge 12\)，所有具有这组统计量的有序分拆对都会被计入。
这样的局面一共有多少个？有
$$g(7,3)=4,\qquad g(5,2)=2,$$
因为把 7 分成 3 个正部分的分拆共有 \((5,1,1)\)、\((4,2,1)\)、\((3,3,1)\)、\((3,2,2)\) 四种，而把 5 分成 2 个正部分的分拆有 \((4,1)\)、\((3,2)\) 两种。所以这一组参数贡献 \(4\cdot 2=8\) 个有序局面。如果把 \(B\) 的总数改成 4 且保持 \(v_B=2\)，那么奇偶性不再匹配，这整个参数类就不会出现在 \(C_{=1}\) 中。
C++、Python 和 Java 三个实现都遵循同一条主线：先构造分拆表，再转换成“恰好 \(v\) 个堆”的统计表，最后按照定理的两个分支分别累加，并始终在模 \(1234567891\) 下运算。
第一张表保存所有 \(0\le u,s\le N\) 的 \(P(u,s)\)。表建好以后，再对每个合法的 \((t,v)\) 填入 \(g(t,v)=P(v,t-v)\)。当 \(g\) 已经完全得到以后，原始的 \(P\) 表就可以丢弃。
对每一个可能的 \(v_A\)，实现会维护一个关于所有较小堆数 \(v_B\le v_A-2\) 的累计量。再对 \(t_B\) 做一次前缀和，就能在 \(O(1)\) 时间回答
$$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B)$$
这个内部查询。把它乘上 \(g(t_A,v_A)\)，再遍历所有 \((t_A,v_A)\)，就完成了第一部分。
在 \(v_B=v_A-1\) 的情况下，额外条件只剩下奇偶性。因此对每个 \(v_A\)，实现都会为 \(g(t_B,v_A-1)\) 构造两条前缀和：一条只累计偶数 \(t_B\)，另一条只累计奇数 \(t_B\)。当处理某个固定的 \(t_A\) 时，只需在 \(N-t_A\) 的位置读取与 \(t_A\) 同奇偶性的前缀值，再乘上 \(g(t_A,v_A)\)。
所有加法和乘法都在每一步取模 \(1234567891\)，因此整个过程不需要任意精度整数。
构造 \(P(u,s)\) 需要 \(O(N^2)\) 时间和 \(O(N^2)\) 内存。填充精确部分计数表 \(g(t,v)\) 也是一次 \(O(N^2)\) 的扫描。后面的两个累加阶段同样是 \(O(N^2)\)，因为对每个 \(v_A\) 都只做与总数参数有关的线性扫描。
所以整个算法总时间复杂度为 \(O(N^2)\)，空间复杂度为 \(O(N^2)\)，另外只需要 \(O(N)\) 的辅助空间来保存运行和前缀和。对于 \(N=5000\)，这正是合适的规模；如果直接对四个参数做朴素枚举，速度会慢得多。
Позицию в Partisan Nim можно записать как две целочисленные разбиения:
$$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),$$
по одному разбиению для непустых куч каждой стороны. Обозначим
$$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j.$$
При \(N=5000\) реализация считает все упорядоченные позиции с \(t_A+t_B\le N\), которые удовлетворяют точному критерию
$$v_B\le v_A-2\quad\text{или}\quad\bigl(v_B=v_A-1\text{ и }t_A\equiv t_B\pmod 2\bigr).$$
Ответ берется по модулю \(1234567891\). Ключевое упрощение состоит в том, что после такого сведения важны уже не конкретные формы \(A\) и \(B\), а только число разбиений с данным суммарным размером \(t\) и данным числом частей \(v\).
Тем самым игровая задача превращается в аккуратную задачу подсчета разбиений. Как только состояние сводится к \((t_A,v_A,t_B,v_B)\), остается только посчитать, сколько упорядоченных пар разбиений реализуют каждый допустимый набор параметров.
Если упорядочить кучи по невозрастанию, каждая позиция становится упорядоченной парой разбиений \(A\) и \(B\). Для подсчета важны две характеристики:
$$t=\text{общее число фишек},\qquad v=\text{число непустых куч}.$$
Значит, нужна таблица, которая для каждого \(t\) и \(v\) сообщает, сколько разбиений числа \(t\) имеют ровно \(v\) положительных частей. Обозначим это число через \(g(t,v)\).
Пусть \(P(u,s)\) обозначает число разбиений числа \(s\) не более чем на \(u\) положительных частей. Пустое разбиение дает базу
$$P(0,0)=1,\qquad P(0,s)=0\ \text{при}\ s>0.$$
Для \(u\ge 1\) разобьем разбиения числа \(s\) на две группы: использующие не более \(u-1\) частей и использующие ровно \(u\) частей. Во второй группе вычтем 1 из каждой из \(u\) частей; тем самым удаляется \(u\) фишек, и остается разбиение числа \(s-u\) не более чем на \(u\) частей. Поэтому
$$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$$
Теперь возьмем разбиение числа \(t\) ровно на \(v\) положительных частей и вычтем 1 из каждой части. Получится разбиение числа \(t-v\) не более чем на \(v\) частей. Следовательно,
$$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$$
причем \(g(0,0)=1\), а при \(v>t\) имеем \(g(t,v)=0\).
Реализации используют результат о том, что упорядоченная позиция \((A,B)\) должна считаться тогда и только тогда, когда выполняется один из двух случаев:
$$v_B\le v_A-2,$$
или
$$v_B=v_A-1\quad\text{и}\quad t_B\equiv t_A\pmod 2.$$
Поэтому ответ раскладывается на две суммы. Первая ветвь:
$$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).$$
Вторая ветвь:
$$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).$$
Итак, окончательно
$$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$$
Главная инварианта здесь в том, что внутри этих выражений остаются только \(t_A,t_B,v_A,v_B\) и условие на четность. Более тонкая структура самих разбиений уже не нужна.
Прямая четырехкратная сумма была бы слишком медленной, поэтому формулы перестраиваются с помощью префиксных сумм. Для первой ветви вводится
$$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w).$$
Тогда
$$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).$$
Для ветви с условием по четности вводятся
$$E_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ четно}}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\text{ нечетно}}} g(r,v-1).$$
После этого
$$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{ четно},\\ O_{v_A}(N-t_A), & t_A\text{ нечетно}. \end{cases}$$
Именно это преобразование позволяет удержать время работы на уровне \(O(N^2)\).
Рассмотрим
$$A=(4,2,1),\qquad B=(3,2).$$
Здесь \(t_A=7\), \(v_A=3\), \(t_B=5\), \(v_B=2\). Выполняется \(v_B=v_A-1\), и обе суммы нечетны, значит эта позиция относится ко второй ветви. Для любого бюджета \(N\ge 12\) все упорядоченные пары разбиений с такими же статистиками будут посчитаны.
Сколько их? Имеем
$$g(7,3)=4,\qquad g(5,2)=2,$$
потому что разбиения числа 7 на 3 части равны \((5,1,1)\), \((4,2,1)\), \((3,3,1)\), \((3,2,2)\), а разбиения числа 5 на 2 части равны \((4,1)\), \((3,2)\). Следовательно, этот класс параметров дает \(4\cdot 2=8\) упорядоченных позиций. Если бы при том же \(v_B=2\) сумма \(t_B\) была равна 4, условие четности нарушилось бы, и весь этот класс исчез бы из \(C_{=1}\).
Реализации на C++, Python и Java следуют одному и тому же конвейеру: сначала строят таблицы разбиений, затем преобразуют их в таблицу точного числа куч и после этого суммируют обе ветви теоремы в арифметике по модулю.
Первая таблица хранит \(P(u,s)\) для всех \(0\le u,s\le N\). Затем из нее для каждой допустимой пары \((t,v)\) вычисляется значение \(g(t,v)=P(v,t-v)\). После заполнения \(g\) исходная таблица больше не требуется.
Для каждого возможного \(v_A\) реализация поддерживает накопленную сумму по всем меньшим значениям \(v_B\le v_A-2\). Префиксная сумма по \(t_B\) дает внутренний запрос
$$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B)$$
за \(O(1)\) времени. После умножения на \(g(t_A,v_A)\) и прохода по всем \((t_A,v_A)\) получается первая ветвь.
В случае \(v_B=v_A-1\) дополнительное условие связано только с четностью. Поэтому для каждого \(v_A\) код строит две префиксные суммы значений \(g(t_B,v_A-1)\): по четным и по нечетным \(t_B\). Для фиксированного \(t_A\) остается выбрать префикс той же четности в точке \(N-t_A\) и умножить его на \(g(t_A,v_A)\).
Все сложения и умножения немедленно приводятся по модулю \(1234567891\), поэтому произвольная точность не нужна.
Построение \(P(u,s)\) требует \(O(N^2)\) времени и \(O(N^2)\) памяти. Заполнение таблицы точных значений \(g(t,v)\) дает еще один проход \(O(N^2)\). Обе итоговые фазы суммирования также имеют сложность \(O(N^2)\), потому что для каждого \(v_A\) выполняются только линейные проходы по суммарному параметру.
Следовательно, полный алгоритм работает за \(O(N^2)\) времени и использует \(O(N^2)\) памяти, плюс только \(O(N)\) дополнительного пространства для текущих и префиксных сумм. Для \(N=5000\) это именно тот масштаб, который нужен; наивная переборная схема по четырем параметрам была бы заметно хуже.
يمكن كتابة وضعية Partisan Nim على هيئة تقسيمين صحيحين:
$$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),$$
أي تقسيم لكل جهة يصف الأكوام غير الفارغة الخاصة بها. نعرّف
$$t_A=|A|=\sum_i a_i,\qquad t_B=|B|=\sum_j b_j.$$
عند \(N=5000\) تقوم الشيفرة بعدّ جميع الأوضاع المرتبة التي تحقق \(t_A+t_B\le N\) والتي تستوفي بالضبط الشرط
$$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).$$
ويؤخذ الجواب بترديد \(1234567891\). الفكرة الحاسمة هي أنه بعد الوصول إلى هذا الوصف لم تعد الأشكال التفصيلية لـ \(A\) و\(B\) مهمة، بل المهم فقط هو عدد التقسيمات التي تعطي مجموعًا \(t\) مع عدد أجزاء \(v\).
بهذا تتحول المسألة من تحليل لعبة إلى مسألة عد منظّم على التقسيمات الصحيحة. ما إن نلخص الحالة بالرباعية \((t_A,v_A,t_B,v_B)\) حتى يصبح المطلوب هو حساب عدد أزواج التقسيمات المرتبة التي تحقق كل رباعية مسموح بها.
إذا رتبنا الأكوام في كل جهة ترتيبًا تنازليًا، فإن كل وضعية تصبح زوجًا مرتبًا من التقسيمين \(A\) و\(B\). ولأغراض العد تكفي كميتان فقط:
$$t=\text{total counters},\qquad v=\text{nonempty heaps}.$$
لذلك نحتاج إلى جدول يعطي، لكل \(t\) و\(v\)، عدد تقسيمات \(t\) إلى \(v\) أجزاء موجبة بالضبط. ولنرمز إلى هذا العدد بالرمز \(g(t,v)\).
لنعرّف \(P(u,s)\) بأنه عدد تقسيمات \(s\) إلى عدد لا يتجاوز \(u\) من الأجزاء الموجبة. التقسيم الفارغ يعطي الحالة الأساسية
$$P(0,0)=1,\qquad P(0,s)=0\quad (s>0).$$
ولكل \(u\ge 1\) نقسم تقسيمات \(s\) إلى مجموعتين: تقسيمات تستخدم على الأكثر \(u-1\) جزءًا، وتقسيمات تستخدم \(u\) أجزاء بالضبط. في المجموعة الثانية نطرح 1 من كل واحد من الأجزاء \(u\)، فينقص المجموع بمقدار \(u\) ونحصل على تقسيم لـ \(s-u\) إلى عدد لا يتجاوز \(u\) من الأجزاء. لذلك نحصل على العلاقة
$$P(u,s)=P(u-1,s)+ \begin{cases} P(u,s-u), & s\ge u,\\ 0, & s<u. \end{cases}$$
والآن إذا أخذنا تقسيمًا للعدد \(t\) إلى \(v\) أجزاء موجبة بالضبط وطرحنا 1 من كل جزء، نحصل على تقسيم للعدد \(t-v\) إلى عدد لا يتجاوز \(v\) من الأجزاء. ومن ثم
$$g(t,v)=P(v,t-v)\qquad (0\le v\le t),$$
مع \(g(0,0)=1\)، بينما إذا كان \(v>t\) فلدينا \(g(t,v)=0\).
النتيجة الخاصة بالمسألة والتي تعتمد عليها التنفيذات تقول إن الوضعية المرتبة \((A,B)\) تُعدّ بالضبط في حالتين:
$$v_B\le v_A-2,$$
أو
$$v_B=v_A-1\quad\text{and}\quad t_B\equiv t_A\pmod 2.$$
ولهذا ينقسم الجواب إلى مجموعين. الفرع الأول هو
$$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).$$
والفرع الثاني هو
$$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).$$
إذًا يكون الناتج النهائي
$$\operatorname{Ans}\equiv C_{\ge 2}+C_{=1}\pmod{1234567891}.$$
والثابت المهم هنا هو أن ما يبقى مؤثرًا داخل هذين التعبيرين هو فقط \(t_A,t_B,v_A,v_B\) مع شرط parity واحد، أما تفاصيل أحجام الأجزاء نفسها فلا تدخل بعد ذلك بشكل مستقل.
المجموع الرباعي المباشر سيكون بطيئًا جدًا، لذا تُعاد كتابة الصيغ باستخدام مجاميع بادئة. في الفرع الأول نعرّف
$$H_v(s)=\sum_{r=0}^{s}\sum_{w=0}^{v-2} g(r,w).$$
وعندها يصبح
$$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).$$
أما في الفرع الحساس للزوجية فنعرّف
$$E_v(s)=\sum_{\substack{0\le r\le s\\ r\equiv 0\pmod 2}} g(r,v-1),\qquad O_v(s)=\sum_{\substack{0\le r\le s\\ r\equiv 1\pmod 2}} g(r,v-1).$$
وبالتالي
$$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\equiv 0\pmod 2,\\ O_{v_A}(N-t_A), & t_A\equiv 1\pmod 2. \end{cases}$$
ولهذا السبب تحديدًا تبقى الخوارزمية ضمن \(O(N^2)\) بدل أن تنحدر إلى تعداد متداخل أبطأ بكثير.
خذ
$$A=(4,2,1),\qquad B=(3,2).$$
عندئذٍ \(t_A=7\) و\(v_A=3\) و\(t_B=5\) و\(v_B=2\). هنا لدينا \(v_B=v_A-1\)، كما أن المجموعين فرديان، لذا تدخل هذه الوضعية في الفرع الثاني. ولكل ميزانية \(N\ge 12\) فإن كل زوج مرتب من التقسيمات يملك هذه الإحصاءات نفسها سيكون معدودًا.
كم عدد هذه الأزواج؟ لدينا
$$g(7,3)=4,\qquad g(5,2)=2,$$
لأن تقسيمات 7 إلى 3 أجزاء هي \((5,1,1)\) و\((4,2,1)\) و\((3,3,1)\) و\((3,2,2)\)، وتقسيمات 5 إلى جزأين هي \((4,1)\) و\((3,2)\). لذلك تسهم هذه الفئة من المعاملات بعدد \(4\cdot 2=8\) من الأوضاع المرتبة. ولو غيّرنا \(B\) ليصبح مجموعه 4 مع الإبقاء على \(v_B=2\)، فسيفشل شرط الزوجية وتختفي هذه الفئة بالكامل من \(C_{=1}\).
تتبع تنفيذات C++ وPython وJava المسار نفسه: بناء جداول التقسيم، ثم تحويلها إلى جدول لعدد الأكوام الدقيق، ثم جمع فرعي النظرية باستخدام الحسابات بترديد ثابت.
الجدول الأول يخزن \(P(u,s)\) لكل \(0\le u,s\le N\). وبعد اكتماله تُشتق منه قيم \(g(t,v)=P(v,t-v)\) لكل زوج مسموح \((t,v)\). وبعد ملء \(g\) لا يعود الجدول الأول مطلوبًا.
لكل قيمة ممكنة لـ \(v_A\) تحتفظ الشيفرة بمجموع جارٍ يشمل جميع القيم الأصغر \(v_B\le v_A-2\). وبعد أخذ مجموع بادئ على \(t_B\) تصبح الاستعلامات من الشكل
$$\sum_{t_B=0}^{N-t_A}\sum_{v_B=0}^{v_A-2} g(t_B,v_B)$$
متاحة في \(O(1)\). ثم يُضرب ذلك في \(g(t_A,v_A)\)، ومع المرور على كل الأزواج \((t_A,v_A)\) يكتمل الفرع الأول.
في الحالة \(v_B=v_A-1\) يبقى الشرط الإضافي متعلقًا بالزوجية فقط. لذلك تبني الشيفرة لكل \(v_A\) مجموعين بادئين لقيم \(g(t_B,v_A-1)\): أحدهما للأعداد الزوجية \(t_B\) والآخر للأعداد الفردية. وعند معالجة قيمة معينة لـ \(t_A\)، يكفي اختيار البادئة ذات الزوجية المطابقة عند الموضع \(N-t_A\) ثم ضربها في \(g(t_A,v_A)\).
كل عمليات الجمع والضرب تُختزل مباشرة بترديد \(1234567891\)، ولذلك لا حاجة إلى أعداد صحيحة ذات دقة غير محدودة.
بناء الجدول \(P(u,s)\) يحتاج إلى زمن \(O(N^2)\) وذاكرة \(O(N^2)\). كما أن ملء جدول العد الدقيق \(g(t,v)\) هو مرور آخر بكلفة \(O(N^2)\). ومرحلتا الجمع النهائيتان هما أيضًا \(O(N^2)\)، لأن كل قيمة لـ \(v_A\) تتطلب فقط مسوحات خطية في متغير المجموع.
إجمالًا، تعمل الخوارزمية في زمن \(O(N^2)\) وتستخدم ذاكرة \(O(N^2)\)، مع مساحة إضافية مقدارها \(O(N)\) فقط للمجاميع الجارية والبادئات. وهذا هو الحجم المناسب عندما يكون \(N=5000\)، أما التعداد الساذج للمعاملات الأربعة فسيكون أبطأ بكثير.