We consider positions made from piles of cookies whose total size is \(N\). Odd may move only on an odd pile: from a pile of size \(2m+1\), Odd eats one cookie and replaces that pile by two piles of size \(m\). Even may move only on an even pile: from a pile of size \(2m\), Even eats two cookies and replaces that pile by two piles of size \(m-1\).
A position is therefore an integer partition of \(N\). Let \(C(N)\) be the number of such partitions for which Even has a winning strategy when Odd moves first. Directly exploring all partitions together with all move trees is far too expensive for \(N=300\), so the solution converts each pile into an exact short partizan game and then counts partitions by the canonical sum of those games.
Let \(G_n\) denote the game value of a single pile of size \(n\). Because every move strictly reduces pile sizes, these are finite short games, so Conway's recursive theory applies exactly.
The empty pile has no moves, so
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
If \(n=2m+1\) is odd, only Odd has a legal move, and that move replaces the pile by two piles of size \(m\). Therefore
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
If \(n=2m\) is even, only Even has a legal move, and that move replaces the pile by two piles of size \(m-1\). Hence
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
This recurrence is the mathematical core of the whole solution: every pile value is built from the value of a smaller pile doubled under disjunctive sum.
If a position has piles \(n_1,n_2,\dots,n_r\), then the players choose exactly one pile on each move, so the total position is the disjunctive sum
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$$
Equivalently, for a partition written in frequency form
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$$
the total game is
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$$
The outcome class of \(V(\lambda)\) is one of the standard four classes:
$$L,\ N,\ P,\ R,$$
where \(L\) means Odd wins regardless of who starts, \(R\) means Even wins regardless of who starts, \(N\) means the next player wins, and \(P\) means the previous player wins. Since the problem asks for positions where Odd starts and Even wins, the desired partitions are exactly those whose total game lies in class \(P\) or class \(R\).
To compare and combine games exactly, the implementation stores every short game in canonical Conway form
$$G=\{G^L\mid G^R\}.$$
The recursive order relation is
$$G\le H \iff \text{there is no left option } G^L \text{ with } H\le G^L,\ \text{and no right option } H^R \text{ with } H^R\le G.$$
Using this order, one removes dominated options. For example, a left option \(A\) is unnecessary if another left option \(B\) satisfies \(A\le B\), because choosing \(B\) is always at least as good for Odd. Symmetrically, a right option \(A\) is unnecessary if another right option \(B\) satisfies \(B\le A\).
One also removes reversible options: if a move can be answered immediately by the opponent to reach a position no worse for the responder than the original game, then that move does not need to remain as a canonical option. After repeatedly applying these reductions, equivalent games collapse to the same canonical representative, which can then be interned under one shared identifier.
For short games, disjunctive sum is defined recursively by
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
This formula exactly models the rule “choose one pile and move in that pile only.” Once a total game has been built, winner detection is also recursive: a player wins from a position if that player has some legal move to a position winning for the opponent's turn. If no legal move exists, that player loses immediately.
Evaluating that rule with Odd to move and with Even to move gives the two booleans needed to place the game into \(L,N,P,\) or \(R\). That classification is what ultimately decides whether a partition contributes to \(C(N)\).
After the single-pile games \(G_1,G_2,\dots,G_N\) have been computed, the counting problem becomes a partition DP whose states are canonical game values. Let \(D_s(g)\) be the number of partitions of total size \(s\) currently known to have total game \(g\).
Initially, the empty partition contributes one way to total \(0\):
$$D_0(0)=1.$$
Now process part sizes \(k=1,2,\dots,N\) in increasing order. Every existing state of total \(s-k\) can be extended by one more pile of size \(k\):
$$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{ is the canonical form of }g\oplus G_k.$$
Because sizes are processed in nondecreasing order, each multiset of pile sizes is counted exactly once, so this is a partition count rather than a composition count. At the end,
$$C(N)=\sum_{g\in\{P,R\}} D_N(g),$$
meaning we sum the counts of all total games whose outcome class is \(P\) or \(R\).
The seven partitions of \(5\) are
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
Only two of these outcomes are favorable for Even when Odd starts: \((5)\), which is class \(R\), and \((2,2,1)\), which is class \(P\). Therefore
$$C(5)=2.$$
This is the first checkpoint used by the implementations, and a second small checkpoint is \(C(16)=64\).
The C++, Python, and Java implementations all follow the same stages. First they build the single-pile table from \(0\) up to \(N\), using the recurrence above. Every newly created game is reduced to canonical form immediately, so equivalent positions reuse one shared canonical identifier rather than being rebuilt over and over.
Next, the implementations memoize three exact operations on short games: comparison in the Conway order, disjunctive addition, and winner detection for a specified player to move. Those memoized results are crucial, because the same subgames and the same game sums reappear many times across different partitions.
Finally, the implementations run the partition DP over totals \(0\) through \(N\). Each DP entry is a map from a canonical game identifier to the number of partitions that realize that game. After all part sizes have been processed, the map for total \(N\) is scanned and the counts in outcome classes \(P\) and \(R\) are added together. That final sum is the desired value \(C(N)\).
Let \(S_s\) be the number of distinct canonical game values that appear in the DP map for total \(s\). The partition phase performs one state extension for each reachable pair \((g,s-k)\), so its transition count is
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$$
Each transition requires one memoized disjunctive sum lookup, plus a canonical-game construction only when that exact sum has not been seen before. Precomputing the single-pile games adds \(N\) more canonical constructions of the same kind. Hence the practical runtime is governed by the number of distinct game comparisons and sums that are actually reached, not by the astronomically larger number of raw game trees.
The memory usage is the total size of the canonical game database, the comparison/addition/winner caches, and the DP maps:
$$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{plus memoized short-game data}.$$
For \(N=300\), this exact method remains feasible because many different partitions collapse to the same canonical game value.
Wir betrachten Stellungen aus Cookie-Stapeln mit Gesamtsumme \(N\). Odd darf nur auf einem ungeraden Stapel ziehen: Aus einem Stapel der Größe \(2m+1\) isst Odd ein Cookie und ersetzt den Stapel durch zwei Stapel der Größe \(m\). Even darf nur auf einem geraden Stapel ziehen: Aus einem Stapel der Größe \(2m\) isst Even zwei Cookies und ersetzt den Stapel durch zwei Stapel der Größe \(m-1\).
Jede Stellung ist also eine ganzzahlige Partition von \(N\). Sei \(C(N)\) die Anzahl der Partitionen, für die Even eine Gewinnstrategie besitzt, wenn Odd beginnt. Eine direkte Suche über alle Partitionen samt vollständigen Spielbäumen wäre für \(N=300\) unbrauchbar, daher übersetzt die Lösung jeden Stapel in ein exaktes kurzes partizanes Spiel und zählt anschließend Partitionen nach der kanonischen Summe dieser Spiele.
Sei \(G_n\) der Spielwert eines einzelnen Stapels der Größe \(n\). Da jeder Zug die Stapelgrößen strikt verkleinert, sind dies endliche kurze Spiele, sodass Conways rekursive Theorie hier exakt anwendbar ist.
Der leere Stapel hat keine Züge, also
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
Ist \(n=2m+1\) ungerade, so hat nur Odd einen legalen Zug; dieser ersetzt den Stapel durch zwei Stapel der Größe \(m\). Daher gilt
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
Ist \(n=2m\) gerade, so hat nur Even einen legalen Zug; dieser ersetzt den Stapel durch zwei Stapel der Größe \(m-1\). Also
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
Diese Rekursion ist der mathematische Kern der gesamten Methode: Jeder Stapelwert entsteht aus dem Wert eines kleineren Stapels, der unter disjunkter Summe verdoppelt wird.
Hat eine Stellung Stapel \(n_1,n_2,\dots,n_r\), dann wählt ein Zug immer genau einen Stapel aus. Die Gesamtstellung ist daher die disjunkte Summe
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$$
Schreibt man eine Partition in Häufigkeitsform
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$$
so ist das Gesamtspiel
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$$
Die Ergebnisklasse von \(V(\lambda)\) gehört zu den vier Standardklassen
$$L,\ N,\ P,\ R,$$
wobei \(L\) bedeutet, dass Odd unabhängig vom Starter gewinnt, \(R\) bedeutet, dass Even unabhängig vom Starter gewinnt, \(N\) steht für „der nächste Spieler gewinnt“, und \(P\) für „der vorherige Spieler gewinnt“. Da die Aufgabe Stellungen zählt, in denen Odd beginnt und Even gewinnt, sind genau die Partitionen mit Ergebnisklasse \(P\) oder \(R\) relevant.
Um Spiele exakt zu vergleichen und zu addieren, speichert die Implementierung jedes kurze Spiel in kanonischer Conway-Form
$$G=\{G^L\mid G^R\}.$$
Die rekursive Ordnungsrelation lautet
$$G\le H \iff \text{es gibt keine linke Option } G^L \text{ mit } H\le G^L,\ \text{und keine rechte Option } H^R \text{ mit } H^R\le G.$$
Mit dieser Ordnung entfernt man dominierte Optionen. Eine linke Option \(A\) ist zum Beispiel überflüssig, wenn eine andere linke Option \(B\) die Beziehung \(A\le B\) erfüllt; dann ist \(B\) für Odd immer mindestens so gut. Symmetrisch ist eine rechte Option \(A\) überflüssig, wenn es eine andere rechte Option \(B\) mit \(B\le A\) gibt.
Außerdem werden reversible Optionen gestrichen: Wenn auf einen Zug sofort mit einer Antwort reagiert werden kann, die für den Antwortenden keine schlechtere Lage als das Ursprungsspiel erzeugt, muss dieser Zug in der kanonischen Darstellung nicht erhalten bleiben. Nach wiederholter Anwendung dieser Reduktionen fallen äquivalente Spiele auf denselben kanonischen Repräsentanten zusammen und können unter einer gemeinsamen Kennung gespeichert werden.
Für kurze Spiele ist die disjunkte Summe rekursiv definiert durch
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
Genau diese Formel modelliert die Regel, dass pro Zug nur in einem Stapel gespielt wird. Sobald ein Gesamtspiel konstruiert ist, wird der Sieger ebenfalls rekursiv bestimmt: Ein Spieler gewinnt von einer Position aus genau dann, wenn er einen legalen Zug in eine Position besitzt, die für den Gegner am Zug verloren ist. Hat ein Spieler keinen legalen Zug, verliert er sofort.
Wertet man diese Regel einmal für Odd am Zug und einmal für Even am Zug aus, erhält man die beiden Wahrheitswerte, aus denen die Klassifikation in \(L,N,P\) oder \(R\) folgt. Genau diese Klassifikation entscheidet später, ob eine Partition zu \(C(N)\) beiträgt.
Nachdem die Einzelstapelspiele \(G_1,G_2,\dots,G_N\) vorliegen, wird das Zählproblem zu einer Partition-DP mit kanonischen Spielwerten als Zuständen. Sei \(D_s(g)\) die Anzahl der bisher bekannten Partitionen der Summe \(s\), deren Gesamtspiel den Wert \(g\) hat.
Zu Beginn gibt es genau eine leere Partition der Summe \(0\):
$$D_0(0)=1.$$
Nun werden die Teilgrößen \(k=1,2,\dots,N\) aufsteigend verarbeitet. Jeder vorhandene Zustand der Summe \(s-k\) kann um einen weiteren Stapel der Größe \(k\) erweitert werden:
$$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{ ist die kanonische Form von }g\oplus G_k.$$
Da die Teilgrößen nicht absteigend, sondern aufsteigend verarbeitet werden, wird jede Multimenge von Stapelgrößen genau einmal erfasst. Somit zählt die DP Partitionen und keine geordneten Kompositionen. Am Ende gilt
$$C(N)=\sum_{g\in\{P,R\}} D_N(g),$$
also die Summe aller Zählwerte, deren Gesamtspiel die Ergebnisklasse \(P\) oder \(R\) besitzt.
Die sieben Partitionen von \(5\) werden durch die rekursiv aufgebauten Einzelstapelspiele wie folgt klassifiziert:
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
Für Even bei Start von Odd sind also genau zwei Partitionen günstig: \((5)\) mit Klasse \(R\) und \((2,2,1)\) mit Klasse \(P\). Daher
$$C(5)=2.$$
Das ist der erste Kontrollwert der Implementierungen; ein zweiter kleiner Kontrollwert ist \(C(16)=64\).
Die C++-, Python- und Java-Implementierungen folgen denselben Stufen. Zuerst wird die Tabelle der Einzelstapelspiele von \(0\) bis \(N\) mittels der obigen Rekursion aufgebaut. Jedes neu erzeugte Spiel wird sofort kanonisiert, sodass äquivalente Positionen dieselbe kanonische Kennung wiederverwenden, statt mehrfach neu konstruiert zu werden.
Anschließend werden drei exakte Operationen auf kurzen Spielen memoisiert: Vergleich in der Conway-Ordnung, disjunkte Addition und Siegerbestimmung für einen fest vorgegebenen Spieler am Zug. Diese Zwischenspeicherung ist entscheidend, weil dieselben Teilspiele und dieselben Summen in vielen verschiedenen Partitionen wieder auftauchen.
Zum Schluss läuft die Partition-DP über die Summen \(0\) bis \(N\). Jeder DP-Eintrag ist eine Abbildung von einer kanonischen Spielkennung auf die Anzahl der Partitionen, die genau diesen Spielwert erzeugen. Nach Verarbeitung aller Teilgrößen wird die Abbildung für die Summe \(N\) durchlaufen, und die Zählwerte der Ergebnisklassen \(P\) und \(R\) werden addiert. Diese Summe ist genau \(C(N)\).
Sei \(S_s\) die Anzahl verschiedener kanonischer Spielwerte in der DP-Abbildung für die Summe \(s\). In der Partition-Phase wird für jedes erreichbare Paar \((g,s-k)\) genau eine Zustandsfortsetzung ausgeführt; die Zahl der Übergänge ist also
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$$
Jeder Übergang benötigt einen memoisierten Lookup für die disjunkte Summe sowie nur dann eine neue kanonische Konstruktion, wenn diese Summe bislang noch nie aufgetreten ist. Die Vorberechnung der Einzelstapelspiele fügt weitere \(N\) kanonische Konstruktionen derselben Art hinzu. Praktisch wird die Laufzeit deshalb durch die Zahl der tatsächlich erreichten Spielvergleiche und Spielsummen bestimmt und nicht durch die astronomisch viel größere Zahl roher Spielbäume.
Der Speicherbedarf besteht aus der kanonischen Spieldatenbank, den Caches für Vergleich, Addition und Siegerabfrage sowie den DP-Abbildungen:
$$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{zuzüglich memoisierten Kurzdaten der Spiele}.$$
Für \(N=300\) bleibt das exakt handhabbar, weil viele verschiedene Partitionen auf denselben kanonischen Spielwert zusammenfallen.
Toplamı \(N\) olan kurabiye yığınlarından oluşan konumları inceliyoruz. Odd yalnızca tek bir yığında hamle yapabilir: Boyutu \(2m+1\) olan bir yığından bir kurabiye yer ve o yığını iki adet \(m\) boyutlu yığınla değiştirir. Even ise yalnızca çift bir yığında hamle yapabilir: Boyutu \(2m\) olan bir yığından iki kurabiye yer ve o yığını iki adet \(m-1\) boyutlu yığınla değiştirir.
Dolayısıyla her konum, \(N\)'nin bir tamsayı bölüşümüdür. \(C(N)\), Odd ilk oynarken Even'in kazanma stratejisine sahip olduğu bölüşüm sayısını göstersin. \(N=300\) için tüm bölüşümleri ve tüm oyun ağaçlarını doğrudan taramak pratik değildir; bu yüzden çözüm her yığını tam bir sonlu partizan oyuna çevirir ve ardından bölüşümleri bu oyunların kanonik toplamına göre sayar.
\(G_n\), boyutu \(n\) olan tek bir yığının oyun değeri olsun. Her hamle yığın boyutlarını kesin olarak küçülttüğü için bunlar sonlu kısa oyunlardır; dolayısıyla Conway'in özyinelemeli kuramı burada doğrudan uygulanabilir.
Boş yığında hamle yoktur, dolayısıyla
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
Eğer \(n=2m+1\) tek ise yalnızca Odd hamle yapabilir ve bu hamle yığını iki adet \(m\) boyutlu yığına dönüştürür. Bu yüzden
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
Eğer \(n=2m\) çift ise yalnızca Even hamle yapabilir ve bu hamle yığını iki adet \(m-1\) boyutlu yığına dönüştürür. O halde
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
Bu bağıntı çözümün matematiksel omurgasıdır: Her yığın değeri, daha küçük bir yığının değerinin ayrık toplam altında iki kez alınmasıyla oluşur.
Bir konumun yığınları \(n_1,n_2,\dots,n_r\) ise, her hamlede yalnızca bir yığın seçildiğinden toplam konum
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}$$
ayrık toplamıyla ifade edilir. Bölüşümü sıklık biçiminde
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots$$
yazarsak toplam oyun
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k$$
olur. \(V(\lambda)\)'nin sonuç sınıfı standart dört sınıftan biridir:
$$L,\ N,\ P,\ R.$$
Burada \(L\), Odd'ın kim başlarsa başlasın kazandığını; \(R\), Even'in kim başlarsa başlasın kazandığını; \(N\), sıradaki oyuncunun kazandığını; \(P\) ise önceki oyuncunun kazandığını belirtir. Soru Odd ilk oynarken Even'in kazandığı konumları istediği için aradığımız bölüşümler tam olarak sınıfı \(P\) ya da \(R\) olanlardır.
Oyunları tam olarak karşılaştırıp toplayabilmek için uygulama her kısa oyunu kanonik Conway biçiminde saklar:
$$G=\{G^L\mid G^R\}.$$
Özyinelemeli sıralama ilişkisi şöyledir:
$$G\le H \iff \text{ } H\le G^L \text{ olan bir sol seçenek } G^L \text{ yoktur ve } H^R\le G \text{ olan bir sağ seçenek } H^R \text{ yoktur.}$$
Bu sıra kullanılarak baskın seçenekler temizlenir. Örneğin bir sol seçenek \(A\), başka bir sol seçenek \(B\) için \(A\le B\) sağlanıyorsa gereksizdir; çünkü Odd açısından \(B\) her zaman en az \(A\) kadar iyidir. Simetrik olarak bir sağ seçenek \(A\), başka bir sağ seçenek \(B\) için \(B\le A\) olduğunda gereksizdir.
Ayrıca geri alınabilir seçenekler de kaldırılır: Bir hamleye rakip hemen cevap verip başlangıç konumundan kendi açısından daha kötü olmayan bir yere dönebiliyorsa, o hamlenin kanonik biçimde tutulmasına gerek yoktur. Bu indirgemeler tekrar tekrar uygulandığında eşdeğer oyunlar tek bir kanonik temsilciye düşer ve ortak bir kimlik altında saklanabilir.
Kısa oyunlarda ayrık toplam şu özyinelemeli formülle tanımlanır:
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
Bu formül “hamlede yalnızca bir yığında oyna” kuralını tam olarak modeller. Toplam oyun kurulduktan sonra kazanan da özyinelemeli olarak belirlenir: Bir oyuncu, kendi sırası geldiğinde rakibini kaybeden duruma götüren en az bir yasal hamleye sahipse kazanır. Hiç yasal hamlesi yoksa anında kaybeder.
Bu kural Odd sıradayken ve Even sıradayken ayrı ayrı değerlendirilerek iki doğruluk değeri elde edilir; bunlardan da oyunun \(L,N,P\) veya \(R\) sınıfına ait olduğu belirlenir. Bir bölüşümün \(C(N)\)'ye katkı verip vermediğini belirleyen tam olarak bu sınıflamadır.
Tek yığın oyunları \(G_1,G_2,\dots,G_N\) hesaplandıktan sonra, sayım problemi durumları kanonik oyun değerleri olan bir partition DP'ye dönüşür. \(D_s(g)\), toplamı \(s\) olan ve toplam oyun değeri \(g\) olan bilinen bölüşüm sayısı olsun.
Başlangıçta toplam \(0\) için yalnızca boş bölüşüm vardır:
$$D_0(0)=1.$$
Şimdi parça boyları \(k=1,2,\dots,N\) artan sırayla işlenir. Toplamı \(s-k\) olan her mevcut durum, boyutu \(k\) olan bir yığın daha eklenerek genişletilebilir:
$$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{, }g\oplus G_k\text{'nın kanonik biçimidir.}$$
Boyutlar artan sırayla işlendiği için her yığın çokluğu tam olarak bir kez sayılır; böylece sıralı bileşimler değil, gerçekten bölüşümler sayılmış olur. Sonuçta
$$C(N)=\sum_{g\in\{P,R\}} D_N(g)$$
elde edilir; yani toplam oyun sınıfı \(P\) veya \(R\) olan tüm durumların sayıları toplanır.
\(5\)'in yedi bölüşümü, özyinelemeli olarak bulunan tek-yığın oyunları kullanıldığında şu sınıflara düşer:
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
Odd ilk oynarken Even için uygun olan yalnızca iki durum vardır: sınıfı \(R\) olan \((5)\) ve sınıfı \(P\) olan \((2,2,1)\). Bu nedenle
$$C(5)=2.$$
Bu, uygulamaların kullandığı ilk küçük kontrol değeridir; ikinci küçük kontrol değeri ise \(C(16)=64\)'tür.
C++, Python ve Java uygulamalarının üçü de aynı akışı izler. Önce \(0\)'dan \(N\)'e kadar tüm tek-yığın oyunları yukarıdaki bağıntıyla oluşturulur. Yeni üretilen her oyun hemen kanonik biçime indirgenir; böylece eşdeğer konumlar tekrar tekrar kurulmak yerine aynı kanonik kimliği paylaşır.
Daha sonra kısa oyunlar üzerinde üç kesin işlem belleklenir: Conway sırasına göre karşılaştırma, ayrık toplam ve belirli bir oyuncu sıradayken kazananı belirleme. Bu önbellekleme kritik önemdedir, çünkü aynı alt oyunlar ve aynı oyun toplamları farklı bölüşümlerde defalarca yeniden ortaya çıkar.
Son aşamada partition DP toplamlar \(0\) ile \(N\) arasında çalıştırılır. Her DP girişi, bir kanonik oyun kimliğini o oyun değerini veren bölüşüm sayısına eşleyen bir sözlüktür. Tüm parça boyları işlendiğinde, toplamı \(N\) olan tablodaki sınıfı \(P\) veya \(R\) olan tüm sayımlar toplanır. Elde edilen toplam tam olarak \(C(N)\)'dir.
\(S_s\), toplamı \(s\) olan DP sözlüğünde görünen farklı kanonik oyun değeri sayısı olsun. Partition aşamasında yapılan geçiş sayısı
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}$$
kadardır; çünkü erişilebilir her \((g,s-k)\) çifti için tam bir durum genişletmesi yapılır. Her geçiş bir ayrık toplam önbellek sorgusu gerektirir; yalnızca o toplam daha önce hiç görülmemişse yeni bir kanonik oyun kurulumu yapılır. Tek-yığın ön hesaplaması da aynı tipten \(N\) ek kurulum daha yapar. Bu nedenle pratik çalışma süresi, gerçekleşen farklı oyun karşılaştırmaları ve toplamlarının sayısına bağlıdır; ham oyun ağaçlarının astronomik sayısına değil.
Bellek kullanımı, kanonik oyun veritabanı, karşılaştırma/toplama/kazanan önbellekleri ve DP sözlüklerinden oluşur:
$$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{artı belleklenmiş kısa oyun verileri.}$$
\(N=300\) için bu tam yöntem uygulanabilir kalır, çünkü birçok farklı bölüşüm aynı kanonik oyun değerine çöker.
Estudiamos posiciones formadas por montones de galletas cuya suma total es \(N\). Odd solo puede mover en un montón impar: si el montón tiene tamaño \(2m+1\), come una galleta y reemplaza ese montón por dos montones de tamaño \(m\). Even solo puede mover en un montón par: si el montón tiene tamaño \(2m\), come dos galletas y reemplaza ese montón por dos montones de tamaño \(m-1\).
Por tanto, cada posición es una partición entera de \(N\). Sea \(C(N)\) el número de particiones para las que Even tiene estrategia ganadora cuando Odd mueve primero. Explorar directamente todas las particiones y todos los árboles de juego es demasiado costoso para \(N=300\), así que la solución traduce cada montón a un juego partizano corto exacto y luego cuenta las particiones por la suma canónica de esos juegos.
Sea \(G_n\) el valor del juego asociado a un único montón de tamaño \(n\). Como cada jugada reduce estrictamente los tamaños de los montones, todos estos juegos son finitos y cortos, de modo que la teoría recursiva de Conway se aplica sin aproximaciones.
El montón vacío no tiene movimientos, luego
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
Si \(n=2m+1\) es impar, solo Odd tiene un movimiento legal y ese movimiento sustituye el montón por dos montones de tamaño \(m\). Entonces
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
Si \(n=2m\) es par, solo Even puede mover y su jugada sustituye el montón por dos montones de tamaño \(m-1\). Por tanto
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
Esta recurrencia es el núcleo matemático del método completo: cada valor de montón se construye a partir del valor de un montón menor duplicado bajo suma disyuntiva.
Si una posición contiene montones \(n_1,n_2,\dots,n_r\), cada jugada afecta a un solo montón, así que la posición total es la suma disyuntiva
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$$
Si escribimos una partición en forma de frecuencias
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$$
entonces el juego total es
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$$
La clase de resultado de \(V(\lambda)\) pertenece a una de las cuatro clases estándar
$$L,\ N,\ P,\ R,$$
donde \(L\) significa que Odd gana juegue quien juegue primero, \(R\) significa que Even gana juegue quien juegue primero, \(N\) indica que gana el siguiente jugador, y \(P\) indica que gana el jugador anterior. Como el problema pide las posiciones en las que Odd empieza y Even gana, las particiones buscadas son exactamente las que tienen clase \(P\) o clase \(R\).
Para comparar y combinar juegos con exactitud, la implementación almacena cada juego corto en forma canónica de Conway
$$G=\{G^L\mid G^R\}.$$
La relación de orden recursiva es
$$G\le H \iff \text{no existe una opción izquierda } G^L \text{ con } H\le G^L,\ \text{y no existe una opción derecha } H^R \text{ con } H^R\le G.$$
Con este orden se eliminan las opciones dominadas. Por ejemplo, una opción izquierda \(A\) es innecesaria si existe otra opción izquierda \(B\) tal que \(A\le B\), porque para Odd siempre es al menos tan bueno elegir \(B\). De forma simétrica, una opción derecha \(A\) es innecesaria si existe otra opción derecha \(B\) con \(B\le A\).
También se eliminan las opciones reversibles: si una jugada puede ser contestada inmediatamente por el rival con una respuesta que devuelve a una posición no peor para quien responde que el juego original, esa jugada no necesita permanecer en la representación canónica. Tras repetir estas reducciones, los juegos equivalentes colapsan al mismo representante canónico y pueden compartirse mediante un único identificador.
Para juegos cortos, la suma disyuntiva se define recursivamente por
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
Esta fórmula modela exactamente la regla “elige un montón y mueve solo en ese montón”. Una vez construida la suma total, el ganador también se decide de forma recursiva: un jugador gana desde una posición si tiene alguna jugada legal que lleve a una posición perdedora para el turno del oponente. Si no tiene jugadas legales, pierde de inmediato.
Evaluar esa regla con Odd al turno y con Even al turno produce los dos valores lógicos necesarios para clasificar el juego en \(L,N,P\) o \(R\). Esa clasificación final es lo que determina si una partición contribuye a \(C(N)\).
Una vez calculados los juegos de un solo montón \(G_1,G_2,\dots,G_N\), el problema de conteo se convierte en una DP de particiones cuyos estados son valores canónicos de juego. Sea \(D_s(g)\) el número de particiones conocidas del total \(s\) cuyo juego total vale \(g\).
Al principio, la partición vacía aporta una única forma al total \(0\):
$$D_0(0)=1.$$
Después se procesan los tamaños de parte \(k=1,2,\dots,N\) en orden creciente. Cada estado existente del total \(s-k\) puede extenderse añadiendo un montón más de tamaño \(k\):
$$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{ es la forma canónica de }g\oplus G_k.$$
Como los tamaños se procesan en orden no decreciente, cada multiconjunto de tamaños aparece exactamente una vez; por eso la DP cuenta particiones y no composiciones ordenadas. Al final,
$$C(N)=\sum_{g\in\{P,R\}} D_N(g),$$
es decir, sumamos los conteos de todos los juegos totales cuya clase es \(P\) o \(R\).
Las siete particiones de \(5\) quedan clasificadas así cuando se evalúan con los juegos de un solo montón obtenidos recursivamente:
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
Solo dos de ellas favorecen a Even cuando Odd empieza: \((5)\), que es de clase \(R\), y \((2,2,1)\), que es de clase \(P\). Por lo tanto,
$$C(5)=2.$$
Ese es el primer punto de control usado por las implementaciones, y un segundo control pequeño es \(C(16)=64\).
Las implementaciones en C++, Python y Java siguen las mismas etapas. Primero construyen la tabla de juegos de un solo montón desde \(0\) hasta \(N\) usando la recurrencia anterior. Cada juego recién creado se reduce inmediatamente a forma canónica, de modo que las posiciones equivalentes reutilizan un único identificador canónico en lugar de reconstruirse muchas veces.
Después, las implementaciones memorizan tres operaciones exactas sobre juegos cortos: la comparación en el orden de Conway, la suma disyuntiva y la determinación del ganador para un jugador concreto al mover. Esa memorización es esencial, porque los mismos subjuegos y las mismas sumas reaparecen continuamente a través de particiones distintas.
Por último, las implementaciones ejecutan la DP de particiones sobre los totales \(0\) a \(N\). Cada entrada de la DP es un mapa desde un identificador canónico de juego hasta el número de particiones que producen exactamente ese juego. Tras procesar todos los tamaños de parte, se recorre el mapa del total \(N\) y se suman los conteos de las clases \(P\) y \(R\). Esa suma final es precisamente \(C(N)\).
Sea \(S_s\) el número de valores canónicos distintos que aparecen en el mapa de DP para el total \(s\). La fase de particiones realiza una extensión de estado por cada par alcanzable \((g,s-k)\), de modo que el número de transiciones es
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$$
Cada transición necesita una consulta memoizada de suma disyuntiva y, solo si esa suma exacta no se había visto antes, la construcción de un nuevo juego canónico. El precálculo de los juegos de un solo montón añade otras \(N\) construcciones canónicas del mismo tipo. En consecuencia, el tiempo práctico depende del número de comparaciones y sumas de juegos realmente alcanzadas, no del número muchísimo mayor de árboles de juego sin reducir.
La memoria está formada por la base de datos de juegos canónicos, las cachés de comparación/suma/ganador y los mapas de la DP:
$$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{más los datos memoizados de juegos cortos.}$$
Para \(N=300\), este método exacto sigue siendo viable porque muchas particiones diferentes colapsan en el mismo valor canónico.
我们研究由若干饼干堆组成、总和为 \(N\) 的局面。Odd 只能在奇数堆上行动：若某堆大小为 \(2m+1\)，他吃掉 1 块饼干，并把这一堆替换为两堆大小都为 \(m\) 的新堆。Even 只能在偶数堆上行动：若某堆大小为 \(2m\)，她吃掉 2 块饼干，并把这一堆替换为两堆大小都为 \(m-1\) 的新堆。
因此，一个局面正好对应于 \(N\) 的一个整数分拆。记 \(C(N)\) 为这样一些分拆的数量：在 Odd 先手的前提下，Even 仍然有必胜策略。对于 \(N=300\)，如果直接枚举所有分拆并继续展开完整博弈树，代价会非常高；所以解法先把每个单堆转化为一个精确的有限偏置博弈，再按这些博弈的规范和来统计分拆数量。
设 \(G_n\) 表示一个大小为 \(n\) 的单堆所对应的博弈值。由于每一步都会严格减小堆的大小，所以这些博弈都是有限的短博弈，Conway 的递归博弈理论可以被精确使用。
空堆没有任何合法行动，因此
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
如果 \(n=2m+1\) 是奇数，那么只有 Odd 可以行动；他的唯一行动会把这一堆变成两堆大小都为 \(m\) 的堆，所以
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
如果 \(n=2m\) 是偶数，那么只有 Even 可以行动；她的行动会把这一堆变成两堆大小都为 \(m-1\) 的堆，因此
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
这组递推关系是整套方法的数学核心：每个单堆博弈都由一个更小堆的博弈值，通过“自身与自身的直和”递归构造出来。
若某个局面包含的堆为 \(n_1,n_2,\dots,n_r\)，则每一步都只会作用于其中一堆，所以总局面正是这些单堆博弈的直和：
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$$
若把分拆写成频数形式
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$$
则总博弈可写为
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$$
\(V(\lambda)\) 的结果类别属于四个标准类别之一：
$$L,\ N,\ P,\ R.$$
其中 \(L\) 表示 Odd 无论先手后手都能赢，\(R\) 表示 Even 无论先手后手都能赢，\(N\) 表示先手必胜，\(P\) 表示后手必胜。题目要求的是“Odd 先手时 Even 获胜”的分拆，所以我们真正需要统计的是总博弈属于 \(P\) 或 \(R\) 的那些分拆。
为了能够精确比较和相加短博弈，实现中把每个博弈都存成 Conway 的规范形式
$$G=\{G^L\mid G^R\}.$$
递归顺序关系写成
$$G\le H \iff \text{不存在某个左选项 } G^L \text{ 使得 } H\le G^L,\ \text{并且不存在某个右选项 } H^R \text{ 使得 } H^R\le G.$$
利用这个顺序，可以去掉被支配的选项。例如，如果某个左选项 \(A\) 满足存在另一个左选项 \(B\) 使 \(A\le B\)，那么对 Odd 来说选 \(B\) 永远不比选 \(A\) 差，因此 \(A\) 可以删去。右选项也完全类似：若存在另一个右选项 \(B\) 使 \(B\le A\)，那么右选项 \(A\) 就是多余的。
还要去掉可逆选项：如果一方走出某一步后，对手可以立刻回应并回到一个对自己不比原局面更差的位置，那么这一步不必保留在规范表示中。经过反复消除重复、被支配与可逆选项之后，等价的短博弈会收缩到同一个规范代表，从而可以共用一个规范标识。
短博弈的直和按照下面的递归公式定义：
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
这正好对应题目的规则：每一步只在一个堆上操作。得到总博弈以后，胜负判定同样递归进行：若当前行动方存在某一步，能够把局面送到“轮到对手而对手必败”的位置，那么当前行动方必胜；如果当前行动方根本没有合法步，则立刻判负。
分别对 “Odd 行动” 和 “Even 行动” 两种起手情况执行这一递归判定，就能得到两个布尔结果，并据此把总博弈归入 \(L,N,P,R\) 四类之一。最后决定一个分拆是否计入 \(C(N)\) 的，正是这一步得到的类别。
当 \(G_1,G_2,\dots,G_N\) 都求出来以后，计数问题就变成了一个“状态是规范博弈值”的分拆动态规划。设 \(D_s(g)\) 表示：目前已知总和为 \(s\)、总博弈值恰好为 \(g\) 的分拆有多少个。
初始时，和为 \(0\) 的空分拆只有一种：
$$D_0(0)=1.$$
然后按部件大小 \(k=1,2,\dots,N\) 递增处理。任何一个总和为 \(s-k\) 的已知状态，都可以再加入一个大小为 \(k\) 的堆：
$$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{ 是 }g\oplus G_k\text{ 的规范形式。}$$
因为部件大小是按非降顺序处理的，所以每一个堆大小多重集只会被计算一次，这样得到的是整数分拆的数量，而不是有序拆分的数量。处理结束后，
$$C(N)=\sum_{g\in\{P,R\}} D_N(g),$$
也就是把所有总博弈类别为 \(P\) 或 \(R\) 的状态计数加起来。
把 \(5\) 的七个分拆代入递归得到的单堆博弈后，可得到如下结果类别：
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
在 Odd 先手的条件下，只有两种分拆对 Even 有利：\((5)\) 属于 \(R\)，\((2,2,1)\) 属于 \(P\)。因此
$$C(5)=2.$$
这也是实现中使用的第一个小型校验值；另一个小型校验值是 \(C(16)=64\)。
C++、Python 和 Java 实现遵循完全相同的流程。第一步是根据上面的递推，从 \(0\) 一直构造到 \(N\) 的所有单堆博弈。每个新生成的短博弈都会立刻被化简为规范形式，因此等价局面会共享同一个规范标识，而不会在后续计算中被重复构造。
第二步是对三类精确操作做记忆化：Conway 顺序下的比较、直和运算，以及“指定哪一方行动时该局面是否必胜”的递归判定。这样做非常关键，因为不同分拆中会反复出现相同的子博弈和相同的博弈和。
最后一步是在总和 \(0\) 到 \(N\) 上做分拆 DP。每个 DP 项都是一个映射：键是规范博弈标识，值是能够得到该博弈值的分拆数量。等所有部件大小都处理完以后，扫描总和为 \(N\) 的映射，把类别为 \(P\) 和 \(R\) 的计数相加，得到的就是题目要求的 \(C(N)\)。
记 \(S_s\) 为 DP 中总和 \(s\) 这一层出现的不同规范博弈值个数。则分拆阶段做出的状态扩展次数为
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$$
每一次扩展都需要做一次记忆化的直和查询；只有当这个直和结果此前从未出现过时，才会新建一个规范博弈。单堆博弈的预处理还会额外带来 \(N\) 次同类型的规范构造。因此，实际运行时间主要取决于真正被访问到的不同博弈比较与博弈求和数量，而不是未经合并时那种天文数量级的原始博弈树。
内存使用包括规范博弈数据库、比较/求和/胜负判定缓存，以及 DP 映射本身：
$$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{外加记忆化的短博弈数据。}$$
对于 \(N=300\)，这一精确方法之所以仍然可行，是因为大量不同分拆最终会折叠到相同的规范博弈值上。
Рассматриваются позиции, состоящие из стопок печенья с общей суммой \(N\). Odd может ходить только по нечётной стопке: если её размер равен \(2m+1\), он съедает одно печенье и заменяет эту стопку двумя стопками размера \(m\). Even может ходить только по чётной стопке: если её размер равен \(2m\), она съедает два печенья и заменяет эту стопку двумя стопками размера \(m-1\).
Следовательно, каждая позиция является разбиением числа \(N\). Обозначим через \(C(N)\) количество таких разбиений, для которых Even имеет выигрышную стратегию при первом ходе Odd. Для \(N=300\) прямой перебор всех разбиений и всех деревьев ходов слишком дорог, поэтому решение переводит каждую отдельную стопку в точную конечную партизанскую игру, а затем считает разбиения по канонической сумме этих игр.
Пусть \(G_n\) обозначает значение игры для одной стопки размера \(n\). Так как каждый ход строго уменьшает размеры стопок, все такие игры являются конечными короткими играми, и рекурсивная теория Конвея применима здесь без оговорок.
Пустая стопка не допускает ходов, значит
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
Если \(n=2m+1\) нечётно, то легальный ход есть только у Odd, и этот ход заменяет стопку двумя стопками размера \(m\). Поэтому
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
Если \(n=2m\) чётно, то ходить может только Even, причём её ход заменяет стопку двумя стопками размера \(m-1\). Следовательно,
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
Эта рекурсия и есть математическое ядро всего метода: значение любой стопки строится из значения меньшей стопки, взятого дважды в дизъюнктивной сумме.
Если позиция содержит стопки \(n_1,n_2,\dots,n_r\), то каждый ход затрагивает ровно одну из них. Поэтому полная позиция описывается дизъюнктивной суммой
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$$
Если записать разбиение в частотной форме
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$$
то полная игра равна
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$$
Класс результата \(V(\lambda)\) принадлежит одной из четырёх стандартных категорий
$$L,\ N,\ P,\ R,$$
где \(L\) означает победу Odd независимо от того, кто начинает, \(R\) означает победу Even независимо от стартующего игрока, \(N\) означает победу следующего игрока, а \(P\) означает победу предыдущего игрока. Так как в задаче Odd ходит первым, а выиграть должна Even, нам нужны в точности те разбиения, для которых суммарная игра попадает в класс \(P\) или \(R\).
Чтобы сравнивать и складывать короткие игры без приближений, реализация хранит каждую игру в канонической форме Конвея
$$G=\{G^L\mid G^R\}.$$
Рекурсивное отношение порядка имеет вид
$$G\le H \iff \text{не существует левой опции } G^L \text{ с } H\le G^L,\ \text{и не существует правой опции } H^R \text{ с } H^R\le G.$$
Это позволяет удалять доминируемые опции. Например, левая опция \(A\) не нужна, если существует другая левая опция \(B\) такая, что \(A\le B\): для Odd выбор \(B\) всегда не хуже выбора \(A\). Аналогично правая опция \(A\) удаляется, если есть другая правая опция \(B\) с \(B\le A\).
Кроме того, удаляются обратимые опции: если на некоторый ход соперник может немедленно ответить так, чтобы вернуться в позицию, не худшую для себя, чем исходная игра, то такой ход не нужен в каноническом представлении. После повторного удаления дубликатов, доминируемых и обратимых опций эквивалентные игры сводятся к одному и тому же каноническому представителю и могут совместно использовать один идентификатор.
Для коротких игр дизъюнктивная сумма задаётся рекурсивно формулой
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
Именно эта формула точно выражает правило «за ход выбрать одну стопку и сделать ход только в ней». После построения суммарной игры победитель определяется тоже рекурсивно: игрок выигрывает из позиции тогда и только тогда, когда у него есть ход в позицию, проигрышную для соперника на его ходе. Если допустимых ходов нет, текущий игрок немедленно проигрывает.
Если вычислить это правило отдельно для случая, когда ходит Odd, и для случая, когда ходит Even, то получаются два булевых значения, из которых затем следует принадлежность игры к \(L,N,P\) или \(R\). Именно эта классификация определяет, засчитывается ли разбиение в \(C(N)\).
После вычисления игр одной стопки \(G_1,G_2,\dots,G_N\) задача подсчёта превращается в динамическое программирование по разбиениям, где состояниями служат канонические значения игр. Пусть \(D_s(g)\) обозначает число уже построенных разбиений суммы \(s\), для которых суммарная игра имеет значение \(g\).
Начальное условие: пустое разбиение даёт единственный способ получить сумму \(0\):
$$D_0(0)=1.$$
Далее размеры частей \(k=1,2,\dots,N\) обрабатываются по возрастанию. Каждый имеющийся state для суммы \(s-k\) можно продолжить, добавив ещё одну стопку размера \(k\):
$$D_s(h)\leftarrow D_s(h)+D_{s-k}(g),\qquad h\text{ есть каноническая форма }g\oplus G_k.$$
Так как размеры частей перебираются в неубывающем порядке, каждое мультимножество размеров учитывается ровно один раз. Значит, DP считает именно разбиения, а не упорядоченные композиции. В конце получаем
$$C(N)=\sum_{g\in\{P,R\}} D_N(g),$$
то есть суммируем количества всех состояний общей суммы \(N\), чья итоговая игра относится к классам \(P\) или \(R\).
Семь разбиений числа \(5\), после оценки через рекурсивно построенные игры одной стопки, дают следующие классы:
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
При старте Odd благоприятны для Even только два разбиения: \((5)\), имеющее класс \(R\), и \((2,2,1)\), имеющее класс \(P\). Следовательно,
$$C(5)=2.$$
Это первый контрольный результат, используемый реализациями; второй небольшой контрольный результат равен \(C(16)=64\).
Реализации на C++, Python и Java устроены одинаково. Сначала они строят таблицу игр для одной стопки от \(0\) до \(N\) по приведённой выше рекурсии. Каждая новая игра сразу приводится к канонической форме, поэтому эквивалентные позиции повторно используют один и тот же канонический идентификатор, а не пересоздаются много раз.
Затем реализации мемоизируют три точные операции над короткими играми: сравнение в порядке Конвея, дизъюнктивное сложение и определение победителя для фиксированного игрока, которому предстоит ход. Эта мемоизация критически важна, потому что одни и те же подигры и одни и те же суммы игр встречаются снова и снова в разных разбиениях.
После этого выполняется DP по суммам от \(0\) до \(N\). Каждый элемент DP представляет собой отображение из канонического идентификатора игры в число разбиений, которые реализуют именно эту игру. Когда все размеры частей уже обработаны, сканируется отображение для суммы \(N\), и все количества, относящиеся к классам \(P\) и \(R\), суммируются. Полученная сумма и есть искомое значение \(C(N)\).
Обозначим через \(S_s\) число различных канонических значений игры, появляющихся в DP-отображении для суммы \(s\). Тогда на фазе разбиений выполняется ровно одно расширение состояния для каждой достижимой пары \((g,s-k)\), а общее число переходов равно
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$$
Каждый переход требует одного мемоизированного запроса на дизъюнктивную сумму и только в том случае приводит к построению новой канонической игры, если такая точная сумма ещё не встречалась ранее. Предварительное вычисление игр одной стопки добавляет ещё \(N\) канонических построений того же типа. Поэтому практическое время работы определяется числом реально достигнутых сравнений и сумм игр, а не астрономически большим числом сырых деревьев игры.
Память состоит из базы канонических игр, кэшей сравнения/сложения/выигрыша и DP-отображений:
$$O\!\left(\sum_{s=0}^{N} S_s\right)\ \text{плюс мемоизированные данные коротких игр.}$$
Для \(N=300\) этот точный подход остаётся осуществимым именно потому, что множество разных разбиений сжимается в гораздо меньшее число канонических значений игры.
ننظر إلى أوضاع مكوّنة من أكوام بسكويت مجموع أحجامها \(N\). اللاعب Odd لا يستطيع اللعب إلا على كومة فردية: إذا كان حجم الكومة \(2m+1\)، فإنه يأكل قطعة واحدة ويستبدل تلك الكومة بكومتين حجم كل منهما \(m\). أمّا Even فلا يتحرك إلا على كومة زوجية: إذا كان حجم الكومة \(2m\)، فإنها تأكل قطعتين وتستبدل الكومة بكومتين حجم كل منهما \(m-1\).
إذن كل وضع يمثّل تجزئة صحيحة للعدد \(N\). ولْيكن \(C(N)\) هو عدد هذه التجزئات التي تمتلك فيها Even استراتيجية فوز عندما يبدأ Odd أولاً. الاستكشاف المباشر لجميع التجزئات وجميع أشجار اللعب مكلف جداً عند \(N=300\)، لذلك يحوّل الحل كل كومة إلى لعبة جزئية قصيرة دقيقة، ثم يعدّ التجزئات بحسب المجموع القانوني لهذه الألعاب.
لنرمز بـ \(G_n\) إلى قيمة اللعبة الخاصة بكومة واحدة حجمها \(n\). وبما أن كل نقلة تُنقص أحجام الأكوام نقصاناً صارماً، فإن جميع هذه الألعاب منتهية وقصيرة، ولذلك تنطبق عليها نظرية كونواي العودية بدقة كاملة.
الكومة الفارغة لا تحتوي على أي نقلات، ومن ثم
$$G_0=0=\{\varnothing\mid\varnothing\}.$$
إذا كان \(n=2m+1\) فردياً، فإن Odd وحده يملك نقلة قانونية، وهذه النقلة تستبدل الكومة بكومتين حجم كل منهما \(m\). لذلك
$$G_{2m+1}=\{G_m\oplus G_m\mid\varnothing\}\qquad (m\ge 0).$$
وإذا كان \(n=2m\) زوجياً، فإن Even وحدها تملك نقلة قانونية، وهذه النقلة تستبدل الكومة بكومتين حجم كل منهما \(m-1\). ومن ثم
$$G_{2m}=\{\varnothing\mid G_{m-1}\oplus G_{m-1}\}\qquad (m\ge 1).$$
هذه العلاقة هي القلب الرياضي للحل كله: فقيمة أي كومة تُبنى من قيمة كومة أصغر ثم تُؤخذ مرتين تحت الجمع المنفصل.
إذا كان الوضع يحتوي على الأكوام \(n_1,n_2,\dots,n_r\)، فإن كل نقلة تؤثر في كومة واحدة فقط، ولذلك يكون الوضع الكلي هو المجموع المنفصل
$$V(n_1,\dots,n_r)=G_{n_1}\oplus G_{n_2}\oplus \cdots \oplus G_{n_r}.$$
وإذا كتبنا التجزئة بصيغة التكرارات
$$\lambda=1^{a_1}2^{a_2}3^{a_3}\cdots,$$
فإن اللعبة الكلية تصبح
$$V(\lambda)=\bigoplus_{k\ge 1}\ \bigoplus_{j=1}^{a_k} G_k.$$
تصنيف النتيجة للعبة \(V(\lambda)\) ينتمي إلى إحدى الفئات الأربع القياسية
$$L,\ N,\ P,\ R.$$
الفئة \(L\) تعني أن Odd يفوز سواء بدأ أم لم يبدأ، والفئة \(R\) تعني أن Even تفوز سواء بدأت أم لم تبدأ، والفئة \(N\) تعني أن اللاعب التالي هو الفائز، والفئة \(P\) تعني أن اللاعب السابق هو الفائز. وبما أن السؤال يطلب الحالات التي يبدأ فيها Odd وتفوز فيها Even، فإن التجزئات المطلوبة هي بالضبط تلك التي تقع لعبتها الكلية في الفئة \(P\) أو الفئة \(R\).
لكي نقارن الألعاب ونجمعها بدقة، تخزّن الخوارزمية كل لعبة قصيرة في صيغة كونواي القانونية
$$G=\{G^L\mid G^R\}.$$
وعلاقة الترتيب العودية يمكن كتابتها رمزياً على الصورة
$$G\le H \iff \left(\forall G^L,\ \neg(H\le G^L)\right)\land\left(\forall H^R,\ \neg(H^R\le G)\right).$$
أي لا توجد نقلة يسارية من \(G\) يمكن أن تجعل \(G\) يتجاوز \(H\)، ولا توجد نقلة يمينية من \(H\) يمكن أن تجعل \(H\) يهبط إلى ما دون \(G\).
باستخدام هذا الترتيب يمكن حذف الخيارات المهيمنة. فمثلاً إذا كانت هناك نقلة يسارية \(A\) ويوجد خيار يساري آخر \(B\) يحقق \(A\le B\)، فإن \(A\) تصبح غير ضرورية لأن اختيار \(B\) لا يكون أسوأ أبداً بالنسبة إلى Odd. وبالمثل تُحذف نقلة يمينية \(A\) إذا وُجدت نقلة يمينية أخرى \(B\) تحقق \(B\le A\).
كما تُحذف الخيارات القابلة للعكس: فإذا أمكن للخصم أن يرد مباشرة بعد نقلة ما ليصل إلى وضع ليس أسوأ له من اللعبة الأصلية، فلا حاجة إلى إبقاء تلك النقلة في التمثيل القانوني. وبعد تكرار إزالة التكرارات والخيارات المهيمنة والقابلة للعكس، تنهار الألعاب المتكافئة إلى ممثل قانوني واحد يمكن حفظه تحت معرّف مشترك.
في الألعاب القصيرة يُعرَّف المجموع المنفصل عودياً بالصيغة
$$G\oplus H=\{G^L\oplus H,\ G\oplus H^L\mid G^R\oplus H,\ G\oplus H^R\}.$$
وهذه الصيغة تعبّر بدقة عن قاعدة "اختر كومة واحدة والعب فيها فقط". وبعد بناء اللعبة الكلية، يُحدَّد الفائز أيضاً بطريقة عودية: يكون اللاعب فائزاً من وضع ما إذا كان لديه انتقال قانوني واحد على الأقل إلى وضع خاسر بالنسبة إلى الخصم عندما يأتي دوره. وإذا لم تكن لديه أي نقلة قانونية، فإنه يخسر فوراً.
وحين نقيّم هذه القاعدة مرة مع Odd على الدور ومرة مع Even على الدور، نحصل على القيمتين المنطقيتين اللتين تحددان انتماء اللعبة إلى \(L\) أو \(N\) أو \(P\) أو \(R\). وهذا التصنيف هو الذي يحسم في النهاية ما إذا كانت التجزئة تُحتسب ضمن \(C(N)\).
بعد حساب ألعاب الكومة الواحدة \(G_1,G_2,\dots,G_N\)، تتحول مسألة العد إلى برمجة ديناميكية للتجزئات تكون فيها الحالات هي القيم القانونية للألعاب. ولْيكن \(D_s(g)\) هو عدد التجزئات المعروفة حالياً للمجموع \(s\) التي تملك لعبة كلية قيمتها \(g\).
بدايةً توجد تجزئة فارغة واحدة فقط للمجموع \(0\):
$$D_0(0)=1.$$
ثم تُعالَج أحجام الأجزاء \(k=1,2,\dots,N\) بترتيب تصاعدي. وكل حالة موجودة للمجموع \(s-k\) يمكن توسيعها بإضافة كومة جديدة حجمها \(k\). وإذا رمزنا إلى الممثل القانوني لـ \(g\oplus G_k\) بالرمز \(\widetilde{g\oplus G_k}\)، فإن التحديث هو
$$D_s(\widetilde{g\oplus G_k})\leftarrow D_s(\widetilde{g\oplus G_k})+D_{s-k}(g).$$
ولأن الأحجام تُعالَج بترتيب غير تنازلي، فإن كل متعدد مجموعة من أحجام الأكوام يُحسب مرة واحدة فقط، وبذلك يكون العد عدّاً للتجزئات لا للترتيبات المرتبة. وفي النهاية نحصل على
$$C(N)=\sum_{g\in\{P,R\}} D_N(g),$$
أي نجمع جميع العدادات التي تقع لعبتها الكلية في الفئة \(P\) أو \(R\).
عند تقييم التجزئات السبع للعدد \(5\) باستخدام ألعاب الكومة الواحدة المحسوبة عودياً نحصل على التصنيفات التالية:
$$\begin{aligned} (5)&\to R,\\ (4,1)&\to N,\\ (3,2)&\to N,\\ (3,1,1)&\to N,\\ (2,2,1)&\to P,\\ (2,1,1,1)&\to N,\\ (1,1,1,1,1)&\to N. \end{aligned}$$
إذن هناك تجزئتان فقط تفيدان Even عندما يبدأ Odd: التجزئة \((5)\) لأنها من الفئة \(R\)، والتجزئة \((2,2,1)\) لأنها من الفئة \(P\). لذلك
$$C(5)=2.$$
وهذه هي قيمة التحقق الصغيرة الأولى المستخدمة في التنفيذات، أما قيمة التحقق الصغيرة الثانية فهي \(C(16)=64\).
تنفّذ تطبيقات C++ وPython وJava المراحل نفسها. أولاً تُبنى قائمة ألعاب الكومة الواحدة من \(0\) حتى \(N\) باستخدام العلاقة العودية السابقة. وكل لعبة جديدة تُختزل فوراً إلى صيغة قانونية، بحيث تعيد الأوضاع المتكافئة استخدام المعرّف القانوني نفسه بدلاً من إعادة بنائها مراراً.
بعد ذلك تُخزَّن نتائج ثلاث عمليات دقيقة على الألعاب القصيرة: المقارنة في ترتيب كونواي، والجمع المنفصل، وتحديد الرابح عندما يكون الدور للاعب محدد. هذا التخزين المؤقت أساسي، لأن الألعاب الجزئية نفسها والمجاميع نفسها تظهر مرات كثيرة عبر تجزئات مختلفة.
وأخيراً تُنفَّذ برمجة التجزئات الديناميكية على المجاميع من \(0\) إلى \(N\). كل مدخل في هذه البنية هو خريطة من معرّف لعبة قانوني إلى عدد التجزئات التي تحقق تلك اللعبة بالضبط. وبعد معالجة جميع أحجام الأجزاء، تُفحَص خريطة المجموع \(N\) وتُجمَع القيم التابعة للفئتين \(P\) و\(R\). هذا المجموع النهائي هو القيمة المطلوبة \(C(N)\).
لنرمز بـ \(S_s\) إلى عدد القيم القانونية المختلفة التي تظهر في خريطة البرمجة الديناميكية عند المجموع \(s\). في مرحلة التجزئات تُنفَّذ عملية توسيع حالة واحدة لكل زوج ممكن الوصول إليه من الشكل \((g,s-k)\)، ولذلك يكون عدد الانتقالات
$$\sum_{k=1}^{N}\ \sum_{s=k}^{N} S_{s-k}.$$
كل انتقال يحتاج إلى استعلام جمع منفصل محفوظ مسبقاً، ولا يتطلب إنشاء لعبة قانونية جديدة إلا إذا كانت تلك المحصلة الدقيقة لم تظهر من قبل. كما أن حساب ألعاب الكومة الواحدة يضيف \(N\) إنشاءات قانونية أخرى من النوع نفسه. ولذلك فالزمن العملي تحدده أعداد المقارنات والمجاميع المختلفة التي يصل إليها التنفيذ فعلاً، لا العدد الهائل جداً لأشجار اللعب الخام قبل الاختزال.
أما الذاكرة فتتكون من قاعدة بيانات الألعاب القانونية، ومخابئ المقارنة والجمع والرابح، إضافة إلى خرائط البرمجة الديناميكية. والحد الأساسي لها هو
$$O\!\left(\sum_{s=0}^{N} S_s\right).$$
ويضاف إلى ذلك حجم البيانات المحفوظة الخاصة بالألعاب القصيرة والنتائج المذكرة.
وعند \(N=300\) يبقى هذا الأسلوب الدقيق قابلاً للتنفيذ لأن عدداً كبيراً من التجزئات المختلفة ينهار في النهاية إلى القيم القانونية نفسها.