For every positive triple \((a,b,k)\) with \(a+b+k\le W\), the problem defines one staircase component of Young's Game B. Each component is a short partizan game, and \(S(m,W)\) counts ordered \(m\)-tuples of such components whose disjunctive sum is winning for Left, with the final answer taken modulo \(10^9+7\).
The target value is \(S(8,64)\). The compiled implementations first verify the smaller checkpoints \(S(2,4)=7\) and \(S(3,9)=315319\), then reuse the same machinery for the main case.
The solution has two distinct layers. First, every staircase component is canonically reduced to a very restricted family of game values. Second, once that catalogue is known, the ordered \(m\)-tuples are counted by frequency distributions and a sparse dynamic program instead of explicit enumeration.
Fix positive integers \(a\), \(b\), and \(k\). For \(0\le i\lt a\) and \(0\le j\lt b\), let \(G_{a,b,k}(i,j)\) be the game state in row \(i\), column \(j\), and layer \(k\). Left moves in the \(j\)-direction, while Right moves in the \(i\)-direction. If a move would step past the boundary, play drops to the next smaller layer.
That gives the recursive options
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
with
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
and
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
The staircase component associated with the triple \((a,b,k)\) is the top-left state \(G_{a,b,k}=G_{a,b,k}(0,0)\). Enumerating all triples with \(a,b,k\ge 1\) and \(a+b+k\le W\) produces the full catalogue of components.
Every raw game is reduced by the standard short-game rules: dominated options are removed, reversible moves are bypassed, and if all surviving left and right options are numbers with a gap between them, the game is replaced by the simplest dyadic rational in that interval. So the reduction engine is general enough to create arbitrary dyadic numbers if needed.
After reduction, the solver computes the left and right stops recursively:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
The decisive empirical invariant for this problem is that every staircase component ends up in one of only two forms:
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
In other words, the reduced non-numeric components are always single switches with integer stops. This is not treated as a vague heuristic; the compiled implementations explicitly check for it and stop if a staircase component falls outside that family.
Write
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
Now two frequency tables are enough to describe the whole catalogue:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
and, for each weight \(w\),
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
The problem is therefore no longer about individual triples \((a,b,k)\); it becomes a counting problem over integers and switches classified by their weight and right endpoint.
The non-numeric part of any tuple sum is a sum of basic switches \(U_w\). When \(w_1\ge w_2\), canonical addition gives
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
So if the selected switch weights are sorted in nonincreasing order,
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
the top two switches collapse to the integer \(w_1\), the next two collapse to \(w_3\), and so on. If we also sum the right endpoints \(R_1,\dots,R_s\), then
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
The whole switch contribution becomes
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
That is the key simplification behind the counting stage: after sorting by weight, the switch part remembers only \(s\), the sum of right endpoints, and the sum of the weights sitting in odd positions.
For the purely numeric components, the implementations build ordered convolution tables
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
which count ordered \(n\)-tuples of integers with total \(\sigma\).
For a fixed switch weight \(w\), they also build
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
the number of ordered \(c\)-tuples of weight-\(w\) switches whose right endpoints add to \(\rho\).
The sparse dynamic program processes weights from large to small. A state records
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
where \(s\) is the number of chosen switches, \(\Sigma_R\) the accumulated sum of right endpoints, and \(\Sigma_{\mathrm{odd}}\) the accumulated odd-position contribution. If \(c\) new switches of weight \(w\) are added after the already processed heavier weights, the number of newly occupied odd positions is
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
So the transition is
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
with multiplicity \(\binom{s+c}{c}D_{w,c}(\rho)\). The binomial factor is required because the original tuples are ordered: the newly chosen weight-\(w\) switches can be interleaved with the already chosen heavier switches in \(\binom{s+c}{c}\) ways while preserving the internal order of each group.
After all switch weights have been processed, the remaining \(m-s\) entries must be integers. Interleaving those integers with the \(s\) switches contributes an additional factor \(\binom{m}{s}\). If the numeric part contributes \(\sigma\), define
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
If \(s\) is even, the total game is the integer \(T\), so Left wins exactly when \(T>0\). If \(s\) is odd, the total game is the switch \(\{T\mid T-w_s\}\), so Left has a move to \(T\) and wins when \(T\ge 0\). Combining both cases gives the final criterion
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
For \(W=4\), the admissible triples produce exactly four staircase values:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
So the catalogue is \(\{0,\{0\mid 0\},1,-1\}\). The ordered pairs that are winning for Left are
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
Hence
$$ S(2,4)=7, $$
exactly the checkpoint used by the solver before it tackles the larger inputs.
The C++ and Java implementations iterate over all \(a\) and \(b\). For fixed \(a\) and \(b\), they fill a three-dimensional table over \((k,i,j)\), working backward so that every left and right option has already been constructed when the current state is reduced. This directly implements the staircase recursion above.
After each component \(G_{a,b,k}(0,0)\) is canonically reduced, the implementations compute its stop pair. Numeric components are counted by their integer value. Non-numeric components are required to have exactly one left option and one right option, both numbers, so they can be recorded as a switch \(X(R,w)\) using its right endpoint \(R\) and weight \(w\).
Once the catalogue has been compressed into frequency tables, the implementations precompute ordered convolutions for integers and for each switch weight, run the sparse DP over descending weights, and finally combine each reachable switch state with the appropriate numeric distribution. The Python implementation does not rebuild the game engine itself; it delegates to the compiled solver and returns the parsed result.
The structural bottleneck is catalogue generation. For fixed \(a\) and \(b\), the temporary table has \((K+1)ab\) states, where \(K=W-a-b\). Summing that over all admissible pairs gives
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
This stage uses \(O(W^3)\) temporary space for one staircase family at a time, plus memoized storage for canonical game values. The counting stage is polynomial in \(m\) and in the support sizes of the integer distributions, switch distributions, and reachable sparse-DP states. In practice, that is what makes \(S(8,64)\) feasible: the code counts frequency patterns instead of enumerating astronomical numbers of ordered tuples.
Für jedes positive Tripel \((a,b,k)\) mit \(a+b+k\le W\) definiert die Aufgabe genau eine Treppen-Komponente von Young's Game B. Jede dieser Komponenten ist ein kurzes partizanes Spiel, und \(S(m,W)\) zählt geordnete \(m\)-Tupel solcher Komponenten, deren disjunktive Summe für Left gewinnend ist. Das Ergebnis wird modulo \(10^9+7\) genommen.
Gesucht ist \(S(8,64)\). Die kompilierten Implementierungen prüfen zuerst die Kontrollwerte \(S(2,4)=7\) und \(S(3,9)=315319\) und verwenden danach dieselbe Struktur für den Hauptfall.
Die Lösung trennt das Problem in zwei Ebenen. Zuerst wird jede Treppen-Komponente auf eine sehr kleine Familie kanonischer Spielwerte reduziert. Danach werden die geordneten \(m\)-Tupel nicht explizit erzeugt, sondern über Häufigkeitsverteilungen und eine spärliche dynamische Programmierung gezählt.
Fixiere positive ganze Zahlen \(a\), \(b\) und \(k\). Für \(0\le i\lt a\) und \(0\le j\lt b\) bezeichne \(G_{a,b,k}(i,j)\) den Spielzustand in Zeile \(i\), Spalte \(j\) und Schicht \(k\). Left bewegt sich in \(j\)-Richtung, Right in \(i\)-Richtung. Wenn ein Zug über den Rand hinausgehen würde, fällt das Spiel in die nächstkleinere Schicht zurück.
Damit gilt
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
mit
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
und
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
Die zur Aufgabe gehörige Komponente ist stets der linke obere Zustand \(G_{a,b,k}=G_{a,b,k}(0,0)\). Wenn man alle Tripel mit \(a,b,k\ge 1\) und \(a+b+k\le W\) durchläuft, erhält man den vollständigen Katalog der Komponenten.
Jedes Rohspiel wird mit den üblichen Regeln für kurze Spiele reduziert: dominierte Optionen werden entfernt, reversible Züge übersprungen, und wenn alle überlebenden linken und rechten Optionen Zahlen mit einer Lücke dazwischen sind, ersetzt man das Spiel durch die einfachste dyadische rationale Zahl in diesem Intervall. Der Reduktionskern ist also deutlich allgemeiner als das, was die Treppen-Familie am Ende tatsächlich benötigt.
Nach der Reduktion berechnet der Solver rekursiv den linken und rechten Stop:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
Die entscheidende Invariante dieser Aufgabe lautet: Jede Treppen-Komponente endet nach der Reduktion in genau einer von zwei Formen, nämlich
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
Mit anderen Worten: Nichtnumerische Komponenten sind immer einzelne Schalter mit ganzzahligen Stops. Das ist nicht bloß eine lose Vermutung; die kompilierten Implementierungen prüfen diese Eigenschaft explizit und brechen ab, falls eine Komponente außerhalb dieser Familie auftaucht.
Schreibe
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
Dann genügen zwei Häufigkeitstabellen, um den gesamten Katalog zu beschreiben:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
und für jedes Gewicht \(w\)
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
Damit ist das Problem nicht mehr an einzelne Tripel \((a,b,k)\) gebunden, sondern an eine gezählte Sammlung von Zahlen und Schaltern, klassifiziert nach Gewicht und rechtem Endpunkt.
Der nichtnumerische Anteil einer Summe besteht aus Basisschaltern \(U_w\). Für \(w_1\ge w_2\) gilt nach kanonischer Addition
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
Sortiert man also die gewählten Gewichte nichtzunehmend,
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
dann kollabieren die ersten beiden Schalter zu \(w_1\), die nächsten beiden zu \(w_3\) und so weiter. Mit rechten Endpunkten \(R_1,\dots,R_s\) setzt man
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
Der gesamte Schalteranteil wird dann zu
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
Genau das ist die zentrale Vereinfachung für die Zählung: Nach dem Sortieren nach Gewichten merkt sich der Schalterteil nur noch \(s\), die Summe der rechten Endpunkte und die Summe der Gewichte auf ungeraden Positionen.
Für die rein numerischen Komponenten werden geordnete Faltungen aufgebaut:
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
also die Zahl geordneter \(n\)-Tupel von Zahlen mit Gesamtsumme \(\sigma\).
Für ein festes Schaltergewicht \(w\) berechnet man außerdem
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
die Zahl geordneter \(c\)-Tupel von Gewicht-\(w\)-Schaltern mit rechter Endpunktsumme \(\rho\).
Die spärliche DP verarbeitet die Gewichte von groß nach klein. Ein Zustand speichert
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
wobei \(s\) die Zahl gewählter Schalter, \(\Sigma_R\) die aufsummierten rechten Endpunkte und \(\Sigma_{\mathrm{odd}}\) den Beitrag der ungeraden Positionen bezeichnet. Werden \(c\) neue Schalter des Gewichts \(w\) hinter die bereits verarbeiteten schwereren Gewichte gesetzt, dann ist die Zahl neu besetzter ungerader Positionen
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
Der Übergang lautet daher
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
mit Multiplizität \(\binom{s+c}{c}D_{w,c}(\rho)\). Dieser Binomialfaktor ist nötig, weil die Ausgangsobjekte geordnete Tupel sind: Die neu gewählten Schalter des Gewichts \(w\) können in \(\binom{s+c}{c}\) Weisen zwischen die bereits gewählten schwereren Schalter eingeflochten werden, solange die Reihenfolge innerhalb jeder Gruppe erhalten bleibt.
Sind alle Gewichte abgearbeitet, dann müssen die verbleibenden \(m-s\) Einträge Zahlen sein. Das Einflechten dieser Zahlen zwischen die \(s\) Schalter liefert einen weiteren Faktor \(\binom{m}{s}\). Trägt der numerische Teil die Summe \(\sigma\) bei, so definiert man
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
Ist \(s\) gerade, dann ist das Gesamtspiel die Zahl \(T\), und Left gewinnt genau für \(T>0\). Ist \(s\) ungerade, dann ist das Gesamtspiel der Schalter \(\{T\mid T-w_s\}\), also hat Left einen Zug nach \(T\) und gewinnt für \(T\ge 0\). Zusammen ergibt das die Endregel
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
Für \(W=4\) entstehen aus den zulässigen Tripeln genau vier Werte:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
Der Katalog ist also \(\{0,\{0\mid 0\},1,-1\}\). Die für Left gewinnenden geordneten Paare sind
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
Folglich
$$ S(2,4)=7, $$
genau wie im Prüfwert des Solvers.
Die Implementierungen in C++ und Java durchlaufen alle \(a\) und \(b\). Für feste \(a\) und \(b\) wird eine dreidimensionale Tabelle über \((k,i,j)\) rückwärts gefüllt, sodass jede linke und rechte Option bereits konstruiert ist, wenn der aktuelle Zustand reduziert wird. Damit wird die Treppenrekursion direkt umgesetzt.
Nachdem jede Komponente \(G_{a,b,k}(0,0)\) kanonisch reduziert wurde, berechnen die Implementierungen ihr Stop-Paar. Numerische Komponenten werden nach ihrem ganzzahligen Wert gezählt. Nichtnumerische Komponenten müssen genau eine linke und eine rechte Option besitzen, beide Zahlen, sodass sie als Schalter \(X(R,w)\) über rechten Endpunkt \(R\) und Gewicht \(w\) gespeichert werden können.
Aus diesen Häufigkeitstabellen werden geordnete Faltungen für Zahlen und für jedes Schaltergewicht vorab berechnet. Danach läuft die Sparse-DP über absteigende Gewichte, und zum Schluss wird jeder erreichbare Schalterzustand mit der passenden Zahlenverteilung kombiniert. Die Python-Implementierung baut den Spielkern nicht selbst nach, sondern delegiert an den kompilierten Solver und liefert dessen ausgewertetes Ergebnis zurück.
Der strukturelle Engpass ist die Katalogerzeugung. Für feste \(a\) und \(b\) hat die temporäre Tabelle \((K+1)ab\) Zustände, wobei \(K=W-a-b\). Aufsummiert über alle zulässigen Paare ergibt das
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
Diese Phase benötigt \(O(W^3)\) temporären Speicher für jeweils eine Treppen-Familie sowie zusätzliche Memoisierung für kanonische Spielwerte. Die Zählphase ist polynomial in \(m\) und in den Stützgrößen der Zahlenverteilungen, Schalterverteilungen und erreichbaren Sparse-DP-Zustände. Praktisch funktioniert \(S(8,64)\) also deshalb, weil nicht Tupel, sondern nur ihre Frequenzmuster gezählt werden.
\(a+b+k\le W\) koşulunu sağlayan her pozitif \((a,b,k)\) üçlüsü, Young's Game B'nin bir basamak bileşenini tanımlar. Her bileşen kısa bir partizan oyundur ve \(S(m,W)\), ayrık toplamı Left için kazanç olan sıralı \(m\)-lileri sayar. Sonuç \(10^9+7\) modunda alınır.
Aranan değer \(S(8,64)\)'tür. Derlenmiş uygulamalar önce \(S(2,4)=7\) ve \(S(3,9)=315319\) kontrol noktalarını doğrular, ardından aynı yaklaşımı ana durum için kullanır.
Çözüm iki ayrı katmandan oluşur. Önce her basamak bileşeni çok dar bir kanonik oyun ailesine indirgenir. Sonra sıralı \(m\)-liler tek tek üretilmez; bunun yerine frekans dağılımları ve seyrek bir dinamik programlama ile sayım yapılır.
Pozitif \(a\), \(b\) ve \(k\) sabit olsun. \(0\le i\lt a\) ve \(0\le j\lt b\) için \(G_{a,b,k}(i,j)\), \(i\). satır, \(j\). sütun ve \(k\). katmandaki oyun durumu olsun. Left \(j\) yönünde, Right ise \(i\) yönünde ilerler. Bir hamle sınırı aşacak olursa oyun bir alt katmana düşer.
Böylece
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
ve
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
ile
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
Sorudaki bileşen her zaman sol üst durumdur: \(G_{a,b,k}=G_{a,b,k}(0,0)\). \(a,b,k\ge 1\) ve \(a+b+k\le W\) olan tüm üçlüler gezildiğinde tam bileşen kataloğu elde edilir.
Her ham oyun, kısa partizan oyunların standart kurallarıyla indirgenir: baskın seçenekler kaldırılır, geri döndürülebilir hamleler atlanır ve eğer geriye kalan sol ve sağ seçeneklerin hepsi sayıysa ve arada boşluk varsa oyun o aralıktaki en basit dyadik rasyonel sayıyla değiştirilir. Yani indirgeme motoru, bu problemde sonunda gerçekten ihtiyaç duyulandan daha genel bir yapı destekler.
İndirgeme tamamlandıktan sonra çözücü sol ve sağ stop değerlerini özyinelemeli olarak hesaplar:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
Bu problem için belirleyici değişmez şudur: Her basamak bileşeni sonunda yalnızca şu iki biçimden birine düşer:
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
Yani sayısal olmayan bileşenler her zaman tamsayı stoplara sahip tek bir switch olur. Bu sadece sezgisel bir gözlem değildir; derlenmiş uygulamalar bunu açıkça kontrol eder ve bu ailenin dışına çıkan bir bileşen görülürse işlemi durdurur.
Şöyle yazalım:
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
Bu durumda bütün katalog iki frekans tablosuyla özetlenebilir:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
ve her ağırlık \(w\) için
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
Bundan sonra problem artık tek tek \((a,b,k)\) üçlüleriyle ilgili değildir; ağırlık ve sağ uç değerine göre sınıflandırılmış sayılarla switch'lerin kaç kez oluştuğunu sayma problemine dönüşür.
Toplamın sayısal olmayan kısmı temel switch'lerin \(U_w\) toplamıdır. \(w_1\ge w_2\) olduğunda kanonik toplama
$$ U_{w_1}+U_{w_2}\equiv w_1 $$
verir. Dolayısıyla seçilen ağırlıklar büyükten küçüğe sıralanırsa
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
ilk iki switch \(w_1\)'e, sonraki iki switch \(w_3\)'e ve bu şekilde devam ederek çöker. Sağ uçlar \(R_1,\dots,R_s\) ise
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots $$
tanımlarını yaparız. O zaman tüm switch katkısı
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
Sayım aşamasındaki temel sadeleşme budur: ağırlığa göre sıraladıktan sonra switch kısmından geriye yalnızca \(s\), sağ uç toplamı ve tek konumlardaki ağırlıkların toplamı kalır.
Salt sayısal bileşenler için uygulamalar şu sıralı konvolüsyon tablolarını kurar:
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
yani toplamı \(\sigma\) olan sıralı \(n\)-li sayı bileşeni sayısı.
Sabit bir \(w\) switch ağırlığı için de
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
hesaplanır; bu da sağ uçları toplamı \(\rho\) olan sıralı \(c\) adet ağırlık-\(w\) switch sayısıdır.
Seyrek DP, ağırlıkları büyükten küçüğe işler. Bir durum
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
şeklindedir. Burada \(s\) seçilen switch sayısı, \(\Sigma_R\) sağ uçların birikimli toplamı, \(\Sigma_{\mathrm{odd}}\) ise tek konum katkısıdır. Ağırlığı \(w\) olan \(c\) yeni switch daha önce işlenmiş daha ağır switch'lerin arkasına eklenirse, yeni işgal edilen tek konum sayısı
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
olur. Geçiş de
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr) $$
şeklindedir ve çokluk katsayısı \(\binom{s+c}{c}D_{w,c}(\rho)\)'dir. Bu binom katsayısı gerekir, çünkü asıl nesneler sıralı dizilerdir: yeni seçilen ağırlık-\(w\) switch'ler, daha önce seçilmiş daha ağır switch'lerin arasına \(\binom{s+c}{c}\) farklı biçimde yerleştirilebilir; her grubun kendi iç sırası korunur.
Tüm ağırlıklar işlendiğinde kalan \(m-s\) giriş tamsayı olmak zorundadır. Bu tamsayıların \(s\) switch ile iç içe geçirilmesi ayrıca \(\binom{m}{s}\) çarpanını getirir. Sayısal kısım \(\sigma\) katkısı veriyorsa
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma $$
tanımlanır. \(s\) çiftse toplam oyun tamsayı \(T\)'dir ve Left tam olarak \(T>0\) iken kazanır. \(s\) tekse toplam oyun \(\{T\mid T-w_s\}\) switch'idir; Left buradan \(T\)'ye hamle yapabildiği için \(T\ge 0\) iken kazanır. İki durum birleştirildiğinde son ölçüt
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr) $$
olur.
\(W=4\) için izin verilen üçlüler tam olarak dört değer üretir:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
Dolayısıyla katalog \(\{0,\{0\mid 0\},1,-1\}\) olur. Left için kazanç olan sıralı ikililer şunlardır:
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
Böylece
$$ S(2,4)=7, $$
ve bu da çözücünün önce doğruladığı değerle aynıdır.
C++ ve Java uygulamaları bütün \(a\) ve \(b\) değerlerini dolaşır. Sabit \(a\) ve \(b\) için \((k,i,j)\) üzerinde üç boyutlu bir tabloyu tersten doldururlar; böylece mevcut durum indirgenirken sol ve sağ seçeneklerin tamamı önceden oluşturulmuş olur. Bu, yukarıdaki basamak özyinelemesini doğrudan uygular.
Her \(G_{a,b,k}(0,0)\) kanonik biçime indirgendikten sonra uygulamalar onun stop çiftini hesaplar. Sayısal bileşenler tamsayı değerlerine göre sayılır. Sayısal olmayan bileşenlerin ise tam olarak bir sol ve bir sağ seçeneğe sahip olması gerekir; her ikisi de sayı olduğundan bileşen, sağ uç \(R\) ve ağırlık \(w\) ile \(X(R,w)\) biçiminde kaydedilir.
Bu frekans tablolarından sonra uygulamalar tamsayılar ve her switch ağırlığı için sıralı konvolüsyonları önceden hesaplar, sonra azalan ağırlıklar üzerinde seyrek DP çalıştırır ve en sonda her erişilebilir switch durumunu uygun sayısal dağılımla birleştirir. Python uygulaması oyun motorunu baştan kurmaz; derlenmiş çözücüyü çağırır ve onun sonucunu döndürür.
Yapısal darboğaz katalog üretimidir. Sabit \(a\) ve \(b\) için geçici tablonun \((K+1)ab\) durumu vardır; burada \(K=W-a-b\). Tüm uygun çiftler üzerinde toplam
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5) $$
eder. Bu aşama her seferinde bir basamak ailesi için \(O(W^3)\) geçici bellek ve buna ek olarak kanonik oyun değerleri için memoizasyon depoları kullanır. Sayım aşaması ise \(m\)'de ve tamsayı dağılımlarının, switch dağılımlarının ve erişilebilir seyrek-DP durumlarının destek büyüklüklerinde polinomiktir. Pratikte \(S(8,64)\)'ün mümkün olmasının nedeni, devasa sayıda sıralı \(m\)-liyi tek tek üretmek yerine yalnızca frekans örüntülerinin sayılmasıdır.
Para cada terna positiva \((a,b,k)\) con \(a+b+k\le W\), el problema define una componente escalonada de Young's Game B. Cada componente es un juego partizano corto, y \(S(m,W)\) cuenta las \(m\)-tuplas ordenadas de componentes cuya suma disyunta es ganadora para Left. El resultado final se toma módulo \(10^9+7\).
El objetivo es \(S(8,64)\). Las implementaciones compiladas verifican antes los puntos de control \(S(2,4)=7\) y \(S(3,9)=315319\), y después aplican exactamente la misma maquinaria al caso principal.
La solución separa el problema en dos etapas. Primero, cada componente escalonada se reduce a una familia muy pequeña de valores canónicos. Después, las \(m\)-tuplas ordenadas no se enumeran explícitamente: se cuentan mediante distribuciones de frecuencia y una programación dinámica dispersa.
Fijemos enteros positivos \(a\), \(b\) y \(k\). Para \(0\le i\lt a\) y \(0\le j\lt b\), sea \(G_{a,b,k}(i,j)\) el estado del juego en la fila \(i\), la columna \(j\) y la capa \(k\). Left se mueve en la dirección \(j\), mientras que Right se mueve en la dirección \(i\). Si un movimiento rebasa el borde, el juego desciende a la capa inmediatamente inferior.
Así,
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
con
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
y
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
La componente asociada a la terna \((a,b,k)\) es siempre el estado superior izquierdo \(G_{a,b,k}=G_{a,b,k}(0,0)\). Al recorrer todas las ternas con \(a,b,k\ge 1\) y \(a+b+k\le W\), se obtiene el catálogo completo de componentes.
Cada juego bruto se reduce con las reglas habituales para juegos cortos: se eliminan opciones dominadas, se suprimen jugadas reversibles y, si todas las opciones sobrevivientes a izquierda y derecha son números con un hueco entre ellas, el juego se reemplaza por el racional diádico más simple dentro de ese intervalo. Por tanto, el motor de reducción es más general que la estructura final que acaba apareciendo en esta familia.
Una vez reducida la posición, el solucionador calcula recursivamente el left stop y el right stop:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
El invariante decisivo de este problema es que toda componente escalonada acaba en una de solo dos formas:
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
Es decir, las componentes no numéricas siempre son switches simples con stops enteros. No se trata de una intuición vaga: las implementaciones compiladas lo comprueban de manera explícita y abortan si alguna componente escalonada cae fuera de esa familia.
Escribimos
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
Con eso, dos tablas de frecuencias bastan para describir todo el catálogo:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
y, para cada peso \(w\),
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
El problema deja entonces de ser una suma sobre ternas individuales \((a,b,k)\) y pasa a ser un problema de conteo sobre enteros y switches clasificados por su peso y por su extremo derecho.
La parte no numérica de cualquier suma es una suma de switches básicos \(U_w\). Si \(w_1\ge w_2\), la suma canónica cumple
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
Por eso, si los pesos elegidos se ordenan de mayor a menor,
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
los dos primeros switches colapsan al entero \(w_1\), los dos siguientes a \(w_3\), y así sucesivamente. Si los extremos derechos son \(R_1,\dots,R_s\), definimos
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
Entonces toda la contribución de los switches se reduce a
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
Esa es la simplificación central de la fase de conteo: una vez ordenados por peso, los switches solo dejan tres datos relevantes, a saber, \(s\), la suma de los extremos derechos y la suma de los pesos situados en posiciones impares.
Para las componentes numéricas puras, las implementaciones construyen las convoluciones ordenadas
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
que cuentan las \(n\)-tuplas ordenadas de enteros con suma total \(\sigma\).
Para un peso fijo \(w\), construyen también
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
el número de \(c\)-tuplas ordenadas de switches de peso \(w\) cuyos extremos derechos suman \(\rho\).
La DP dispersa procesa los pesos de mayor a menor. Un estado guarda
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
donde \(s\) es el número de switches elegidos, \(\Sigma_R\) la suma acumulada de extremos derechos y \(\Sigma_{\mathrm{odd}}\) la contribución acumulada de las posiciones impares. Si se añaden \(c\) nuevos switches de peso \(w\) después de los pesos mayores ya procesados, el número de nuevas posiciones impares es
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
Por tanto, la transición es
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
con multiplicidad \(\binom{s+c}{c}D_{w,c}(\rho)\). Ese factor binomial es indispensable porque las tuplas originales son ordenadas: los nuevos switches de peso \(w\) pueden intercalarse entre los switches más pesados ya elegidos de \(\binom{s+c}{c}\) maneras, preservando el orden interno de cada grupo.
Una vez procesados todos los pesos, los \(m-s\) elementos restantes deben ser enteros. Intercalarlos con los \(s\) switches aporta además el factor \(\binom{m}{s}\). Si la parte numérica suma \(\sigma\), definimos
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
Si \(s\) es par, el juego total es el entero \(T\), y Left gana exactamente cuando \(T>0\). Si \(s\) es impar, el juego total es el switch \(\{T\mid T-w_s\}\), así que Left puede mover a \(T\) y gana cuando \(T\ge 0\). Juntando ambos casos se obtiene el criterio final
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
Cuando \(W=4\), las ternas admisibles producen exactamente cuatro valores:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
Por tanto, el catálogo es \(\{0,\{0\mid 0\},1,-1\}\). Los pares ordenados ganadores para Left son
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
En consecuencia,
$$ S(2,4)=7, $$
justo el valor de control que el solucionador comprueba antes de pasar a instancias mayores.
Las implementaciones en C++ y Java recorren todos los valores de \(a\) y \(b\). Para cada pareja fija, rellenan hacia atrás una tabla tridimensional sobre \((k,i,j)\), de modo que todas las opciones izquierda y derecha ya estén construidas cuando toca reducir el estado actual. Eso implementa directamente la recurrencia escalonada anterior.
Tras reducir canónicamente cada componente \(G_{a,b,k}(0,0)\), las implementaciones calculan su par de stops. Las componentes numéricas se cuentan por su valor entero. Las no numéricas deben tener exactamente una opción izquierda y una derecha, ambas numéricas, y así se registran como un switch \(X(R,w)\) mediante su extremo derecho \(R\) y su peso \(w\).
Una vez comprimido el catálogo en frecuencias, las implementaciones precalculan las convoluciones ordenadas para enteros y para cada peso de switch, ejecutan la DP dispersa sobre pesos decrecientes y, al final, combinan cada estado alcanzable de switches con la distribución numérica apropiada. La implementación en Python no reconstruye el motor de juego; delega en el solucionador compilado y devuelve el resultado ya interpretado.
El cuello de botella estructural es la generación del catálogo. Para \(a\) y \(b\) fijos, la tabla temporal tiene \((K+1)ab\) estados, donde \(K=W-a-b\). Sumando sobre todos los pares admisibles se obtiene
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
Esta etapa usa \(O(W^3)\) de memoria temporal para una sola familia escalonada cada vez, más almacenamiento memoizado para los valores canónicos. La fase de conteo es polinómica en \(m\) y en los tamaños de soporte de las distribuciones numéricas, de las distribuciones de switches y de los estados alcanzables de la DP dispersa. En la práctica, \(S(8,64)\) es factible porque el programa cuenta patrones de frecuencia en lugar de enumerar todas las \(m\)-tuplas ordenadas.
对每个满足 \(a+b+k\le W\) 的正整数三元组 \((a,b,k)\)，题目都会定义 Young's Game B 的一个阶梯型部件。每个部件都是一个短偏置组合博弈，而 \(S(m,W)\) 统计的是所有有序 \(m\) 元组中，其析取和对 Left 获胜的方案数，最终结果对 \(10^9+7\) 取模。
目标值是 \(S(8,64)\)。在真正计算这一目标之前，编译型实现会先验证两个较小的检查点：\(S(2,4)=7\) 和 \(S(3,9)=315319\)，然后再用同一套方法处理主问题。
整个解法分成两个层次。第一层先把每个阶梯部件约化到一个非常受限的规范值族；第二层在这个规范目录之上做计数，不再显式枚举所有有序 \(m\) 元组，而是通过频率分布和稀疏动态规划完成统计。
固定正整数 \(a\)、\(b\)、\(k\)。对所有 \(0\le i\lt a\)、\(0\le j\lt b\)，记 \(G_{a,b,k}(i,j)\) 为位于第 \(i\) 行、第 \(j\) 列、第 \(k\) 层的游戏状态。Left 沿 \(j\) 方向移动，Right 沿 \(i\) 方向移动；一旦某一方的走法越过边界，游戏就掉到下一层。
因此有
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
其中
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
而
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
与三元组 \((a,b,k)\) 对应的部件始终取左上角状态 \(G_{a,b,k}=G_{a,b,k}(0,0)\)。把所有满足 \(a,b,k\ge 1\) 且 \(a+b+k\le W\) 的三元组全部枚举出来，就得到了完整的部件目录。
每个原始游戏都会按短博弈的标准规则做约化：删去被支配选项，消去可逆走法；如果剩下的左右选项全都是数并且中间存在空隙，就把该游戏替换为该区间中最简单的 dyadic 有理数。因此，约化引擎本身其实比这道题最终真正出现的结构要更一般。
约化后，求解器还会递归计算 left stop 与 right stop：
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
本题最关键的不变量是：每个阶梯部件最终都只会落在以下两种形式之一：
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
也就是说，所有非数值部件在规范化后都会变成一个左右 stop 都是整数的单开关。这里并不是泛泛而谈的经验判断；编译型实现会显式检查这一点，如果某个阶梯部件不属于这个族，就直接报错停止。
把开关写成
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
这样一来，整个目录只需要两类频率信息：
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
以及对每个权重 \(w\)
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
问题因此不再是逐个处理三元组 \((a,b,k)\)，而是转化成按权重和右端点分类的整数与开关的计数问题。
任意元组和中的非数值部分，本质上都是若干个基本开关 \(U_w\) 的和。若 \(w_1\ge w_2\)，则规范加法满足
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
因此，只要把选中的权重按从大到小排序，
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
前两个开关就会塌缩成整数 \(w_1\)，再接下来的两个塌缩成 \(w_3\)，依此类推。如果这些开关的右端点为 \(R_1,\dots,R_s\)，定义
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
那么整个开关部分会约化成
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
这正是计数阶段的核心简化：一旦按权重排好序，开关部分真正留下来的信息只有三项，即开关个数 \(s\)、右端点总和 \(R_\Sigma\)，以及落在奇数位置上的权重和 \(W_{\mathrm{odd}}\)。
对于纯整数部件，程序先构造有序卷积分布
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
它表示按顺序取出 \(n\) 个整数部件、且总和为 \(\sigma\) 的方案数。
对固定权重 \(w\) 的开关，程序同样构造
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
表示按顺序取出 \(c\) 个权重为 \(w\) 的开关、且它们右端点之和为 \(\rho\) 的方案数。
接下来用一个按权重从大到小推进的稀疏 DP。一个状态记为
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
其中 \(s\) 是已经选入的开关个数，\(\Sigma_R\) 是右端点累计和，\(\Sigma_{\mathrm{odd}}\) 是奇数位置权重的累计贡献。若在当前状态后面再加入 \(c\) 个权重为 \(w\) 的新开关，则这些新开关中落在奇数位置的个数为
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
因此转移写成
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
并带有乘法因子 \(\binom{s+c}{c}D_{w,c}(\rho)\)。这里的二项式系数来自“有序”这一要求：新加入的权重 \(w\) 开关，可以与之前已经选出的更大权重开关做 \(\binom{s+c}{c}\) 种交错排列，同时保持每一组内部的相对顺序。
所有开关权重都处理完后，剩下的 \(m-s\) 个位置只能填整数。把这些整数与 \(s\) 个开关交错排列，还要再乘一个 \(\binom{m}{s}\)。若整数部分的总和为 \(\sigma\)，定义
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
当 \(s\) 为偶数时，总博弈就是整数 \(T\)，因此 Left 当且仅当 \(T>0\) 获胜；当 \(s\) 为奇数时，总博弈是开关 \(\{T\mid T-w_s\}\)，Left 可以先手走到 \(T\)，因此当且仅当 \(T\ge 0\) 获胜。两种情况合并后，得到最终判定
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
当 \(W=4\) 时，所有合法三元组只产生四种部件值：
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
因此目录就是 \(\{0,\{0\mid 0\},1,-1\}\)。把上面的胜负规则应用到所有有序二元组，Left 获胜的恰好是
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
于是
$$ S(2,4)=7, $$
这与求解器在进入大规模输入前使用的检查值完全一致。
C++ 和 Java 实现会遍历所有 \(a\) 与 \(b\)。对固定的一组 \(a,b\)，它们按逆序填充 \((k,i,j)\) 三维表，这样在约化当前状态时，所有左、右后继都已经构造完成，从而直接实现上面的阶梯递推。
每个 \(G_{a,b,k}(0,0)\) 做完规范化之后，程序都会计算它的 stop 对。数值部件按整数值计数；非数值部件则必须恰好有一个左选项和一个右选项，而且两者都必须是数，这样才能用右端点 \(R\) 和权重 \(w\) 把它登记为 \(X(R,w)\)。
得到这些频率表之后，实现会预先计算整数和每个开关权重的有序卷积，随后在降序权重上运行稀疏 DP，最后再把每个可达的开关状态与相应的整数分布合并。Python 实现并不会重写整个博弈引擎；它只是调用编译好的求解器并返回解析后的结果。
结构性的瓶颈在于目录生成。对固定 \(a,b\)，临时表的状态数是 \((K+1)ab\)，其中 \(K=W-a-b\)。对所有允许的 \((a,b)\) 求和可得
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
这一阶段对每个阶梯家族使用 \(O(W^3)\) 的临时空间，另外还需要保存规范博弈值的记忆化存储。计数阶段则在 \(m\) 以及整数分布、开关分布和可达稀疏 DP 状态的支撑规模上是多项式级别。换句话说，\(S(8,64)\) 之所以可算，是因为程序统计的是频率模式，而不是显式枚举天文数量的有序 \(m\) 元组。
Для каждой положительной тройки \((a,b,k)\), удовлетворяющей условию \(a+b+k\le W\), задача задает одну ступенчатую компоненту Young's Game B. Каждая такая компонента является короткой партизанской игрой, а \(S(m,W)\) считает число упорядоченных \(m\)-кортежей компонент, чья дизъюнктивная сумма выигрышна для Left. Ответ берется по модулю \(10^9+7\).
Нужно найти \(S(8,64)\). Перед главным вычислением компилируемые реализации проверяют контрольные значения \(S(2,4)=7\) и \(S(3,9)=315319\), а затем применяют ту же схему к основному случаю.
Решение естественно распадается на два этапа. Сначала каждая ступенчатая компонента приводится к очень узкому семейству канонических игровых значений. Затем упорядоченные \(m\)-кортежи уже не перебираются явно: вместо этого выполняется подсчет по частотным распределениям и разреженной динамике.
Зафиксируем положительные целые \(a\), \(b\) и \(k\). Для \(0\le i\lt a\) и \(0\le j\lt b\) обозначим через \(G_{a,b,k}(i,j)\) игровое состояние в строке \(i\), столбце \(j\) и слое \(k\). Left ходит в направлении \(j\), Right в направлении \(i\). Если ход выходит за границу, игра опускается на следующий меньший слой.
Тем самым
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
где
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
и
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
Компонента, соответствующая тройке \((a,b,k)\), это всегда левый верхний узел \(G_{a,b,k}=G_{a,b,k}(0,0)\). Перебор всех троек с \(a,b,k\ge 1\) и \(a+b+k\le W\) дает полный каталог компонент.
Каждая исходная игра редуцируется по стандартным правилам коротких игр: удаляются доминируемые варианты, обходятся обратимые ходы, а если все оставшиеся левые и правые варианты являются числами и между ними есть зазор, игра заменяется простейшим диадическим рациональным числом внутри этого интервала. Иными словами, сам движок редукции устроен существенно общнее, чем та структура, которая реально появляется в этой задаче.
После редукции решатель рекурсивно вычисляет левый и правый stop:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
Ключевой инвариант здесь таков: каждая ступенчатая компонента в итоге попадает ровно в одну из двух форм
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
То есть все ненумерические компоненты оказываются одиночными переключателями с целыми stop-значениями. Это не просто удобная гипотеза: компилируемые реализации явно проверяют это свойство и аварийно завершаются, если хоть одна ступенчатая компонента выходит за пределы такого семейства.
Запишем
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
Тогда весь каталог описывается двумя частотными таблицами:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
и для каждого веса \(w\)
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
После этого задача перестает быть перебором отдельных троек \((a,b,k)\) и превращается в задачу о подсчете целых чисел и переключателей, классифицированных по весу и правому концу.
Ненумерическая часть суммы состоит из базовых переключателей \(U_w\). При \(w_1\ge w_2\) каноническое сложение дает
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
Значит, если выбранные веса упорядочены по невозрастанию,
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
то первые два переключателя схлопываются в целое \(w_1\), следующие два в \(w_3\) и так далее. Если их правые концы равны \(R_1,\dots,R_s\), обозначим
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
Тогда весь вклад переключателей сводится к
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
Именно это является главным упрощением для подсчета: после сортировки по весу от переключательной части остаются только \(s\), сумма правых концов и сумма весов, стоящих на нечетных позициях.
Для чисто числовых компонент реализации строят упорядоченные свертки
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
то есть число упорядоченных \(n\)-кортежей целых компонент с суммой \(\sigma\).
Для фиксированного веса \(w\) строится также
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
число упорядоченных \(c\)-кортежей переключателей веса \(w\), у которых сумма правых концов равна \(\rho\).
Разреженная динамика обрабатывает веса от больших к меньшим. Состояние имеет вид
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
где \(s\) это число уже выбранных переключателей, \(\Sigma_R\) накопленная сумма правых концов, а \(\Sigma_{\mathrm{odd}}\) накопленный вклад нечетных позиций. Если к уже обработанным большим весам добавить \(c\) новых переключателей веса \(w\), то число новых нечетных позиций равно
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
Отсюда переход
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
с кратностью \(\binom{s+c}{c}D_{w,c}(\rho)\). Биномиальный множитель нужен потому, что исходные объекты являются упорядоченными кортежами: новые переключатели веса \(w\) можно вплести между уже выбранными более тяжелыми переключателями \(\binom{s+c}{c}\) способами при сохранении внутреннего порядка каждой группы.
После обработки всех весов оставшиеся \(m-s\) позиций должны быть числами. Их переплетение с \(s\) переключателями дает дополнительный множитель \(\binom{m}{s}\). Если числовая часть вносит сумму \(\sigma\), положим
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
При четном \(s\) итоговая игра это число \(T\), и Left выигрывает ровно при \(T>0\). При нечетном \(s\) итоговая игра это переключатель \(\{T\mid T-w_s\}\), так что Left имеет ход в \(T\) и выигрывает при \(T\ge 0\). В совокупности получаем критерий
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
При \(W=4\) допустимые тройки дают ровно четыре значения компонент:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
Следовательно, каталог равен \(\{0,\{0\mid 0\},1,-1\}\). Выигрышные для Left упорядоченные пары таковы:
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
Отсюда
$$ S(2,4)=7, $$
что в точности совпадает с контрольной проверкой, выполняемой решателем перед большим запуском.
Реализации на C++ и Java перебирают все \(a\) и \(b\). Для фиксированной пары они в обратном порядке заполняют трехмерную таблицу по \((k,i,j)\), так что к моменту редукции текущего состояния все его левые и правые варианты уже построены. Тем самым напрямую реализуется описанная выше ступенчатая рекурсия.
После канонической редукции каждой компоненты \(G_{a,b,k}(0,0)\) реализации вычисляют ее stop-пару. Числовые компоненты считаются по их целому значению. Ненумерические компоненты обязаны иметь ровно один левый и один правый вариант, причем оба числовые, и потому записываются как переключатели \(X(R,w)\) по правому концу \(R\) и весу \(w\).
После сжатия каталога в частотные таблицы реализации заранее строят упорядоченные свертки для чисел и для каждого веса переключателя, затем запускают разреженную DP по убывающим весам, а в конце комбинируют каждое достижимое переключательное состояние с подходящим числовым распределением. Реализация на Python не повторяет весь игровой движок, а просто вызывает скомпилированный решатель и возвращает разобранный результат.
Главный структурный расход дает построение каталога. При фиксированных \(a\) и \(b\) временная таблица содержит \((K+1)ab\) состояний, где \(K=W-a-b\). Суммирование по всем допустимым парам дает
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
Эта стадия использует \(O(W^3)\) временной памяти для одной ступенчатой семьи за раз, плюс мемоизацию канонических игровых значений. Этап подсчета полиномиален по \(m\) и по размерам носителей числовых распределений, распределений переключателей и достижимых состояний разреженной DP. На практике вычисление \(S(8,64)\) становится возможным именно потому, что программа считает частотные шаблоны, а не перечисляет астрономическое число упорядоченных кортежей.
لكل ثلاثية موجبة \((a,b,k)\) تحقق الشرط \(a+b+k\le W\)، تعرّف المسألة مكوّنا سلميّا من Young's Game B. كل مكوّن هو لعبة تحيزية قصيرة، والكمية \(S(m,W)\) تعدّ عدد التراتيب المرتبة ذات الطول \(m\) التي يكون مجموعها المنفصل رابحا لـ Left، مع أخذ الجواب بترديد \(10^9+7\).
القيمة المطلوبة هي \(S(8,64)\). وتتحقق التطبيقات المترجمة أولا من نقطتي الفحص \(S(2,4)=7\) و\(S(3,9)=315319\)، ثم تستخدم البنية نفسها للحالة الرئيسية.
ينقسم الحل إلى مرحلتين واضحتين. في المرحلة الأولى يُختزل كل مكوّن سلمي إلى عائلة صغيرة جدا من القيم القانونية. وفي المرحلة الثانية لا يجري تعداد جميع التراتيب المرتبة ذات الطول \(m\) صراحة، بل يتم العد عبر توزيعات التكرار وبرمجة ديناميكية متناثرة.
لنثبت أعدادا صحيحة موجبة \(a\) و\(b\) و\(k\). لكل \(0\le i\lt a\) و\(0\le j\lt b\)، نرمز بـ \(G_{a,b,k}(i,j)\) إلى حالة اللعب في الصف \(i\) والعمود \(j\) والطبقة \(k\). يتحرك Left في اتجاه \(j\)، بينما يتحرك Right في اتجاه \(i\). وإذا خرجت الحركة عن الحد، هبطت اللعبة إلى الطبقة الأصغر التالية.
وعليه فإن
$$ G_{a,b,k}(i,j)=\{L_{a,b,k}(i,j)\mid R_{a,b,k}(i,j)\}, $$
حيث
$$ L_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i,j+1), & j\lt b-1,\\ G_{a,b,k-1}(i,0), & j=b-1,\ k>1,\\ \varnothing, & j=b-1,\ k=1, \end{cases} $$
و
$$ R_{a,b,k}(i,j)= \begin{cases} G_{a,b,k}(i+1,j), & i\lt a-1,\\ G_{a,b,k-1}(0,j), & i=a-1,\ k>1,\\ \varnothing, & i=a-1,\ k=1. \end{cases} $$
والمكوّن المرتبط بالثلاثية \((a,b,k)\) هو دائما الحالة العليا اليسرى \(G_{a,b,k}=G_{a,b,k}(0,0)\). وعند تعداد جميع الثلاثيات التي تحقق \(a,b,k\ge 1\) و\(a+b+k\le W\)، نحصل على الفهرس الكامل للمكوّنات.
كل لعبة خام تُختزل بقواعد الألعاب القصيرة المعتادة: إزالة الخيارات المهيمن عليها، تجاوز النقلات القابلة للعكس، وإذا كانت الخيارات الباقية على الجهتين كلها أعدادا ويوجد بينها فراغ، تستبدل اللعبة بأبسط عدد dyadic يقع داخل ذلك المجال. لذلك فإن محرك الاختزال أعمّ بكثير من البنية النهائية التي تظهر فعلا في هذه العائلة.
بعد الاختزال يحسب الحل stop الأيسر وstop الأيمن بصورة عودية:
$$ L^{*}(G)=\max_{G^L} R^{*}(G^L), \qquad R^{*}(G)=\min_{G^R} L^{*}(G^R). $$
أما الثابت الحاسم في هذه المسألة فهو أن كل مكوّن سلمي ينتهي بعد الاختزال إلى واحدة فقط من الصيغتين الآتيتين:
$$ n\in\mathbb{Z}, \qquad\text{or}\qquad X(R,w)=\{R+w\mid R\}, \quad R\in\mathbb{Z},\ w\in\mathbb{Z}_{\ge 0}. $$
أي إن جميع المكوّنات غير العددية تصبح switches مفردة ذات stopات صحيحة. وهذه ليست ملاحظة حدسية فحسب؛ فالنسخ المترجمة تتحقق منها صراحة وتتوقف إذا ظهر مكوّن خارج هذه العائلة.
نكتب
$$ X(R,w)=R+U_w, \qquad U_w=\{w\mid 0\}. $$
وعندئذ يكفي جدولان من التكرارات لوصف الفهرس كله:
$$ f_{\mathrm{num}}(n)=\#\{\text{components equal to }n\}, $$
ولكل وزن \(w\)
$$ f_w(R)=\#\{\text{components equal to }X(R,w)\}. $$
بهذا تتحول المسألة من تعداد ثلاثيات منفردة \((a,b,k)\) إلى مسألة عدّ على أعداد صحيحة وswitches مصنفة بحسب الوزن والنهاية اليمنى.
الجزء غير العددي من أي مجموع هو مجموع switches أساسية من الشكل \(U_w\). وإذا كان \(w_1\ge w_2\)، فإن الجمع القانوني يعطي
$$ U_{w_1}+U_{w_2}\equiv w_1. $$
ولذلك إذا رتبنا الأوزان المختارة ترتيبا تنازليا،
$$ w_1\ge w_2\ge \cdots \ge w_s, $$
فإن أول switchين ينهاران إلى العدد \(w_1\)، والزوج التالي إلى \(w_3\)، وهكذا. وإذا كانت النهايات اليمنى هي \(R_1,\dots,R_s\)، نعرّف
$$ R_\Sigma=\sum_{t=1}^{s}R_t, \qquad W_{\mathrm{odd}}=w_1+w_3+w_5+\cdots. $$
وعندئذ يختزل كامل إسهام الـ switches إلى
$$ \sum_{t=1}^{s}X(R_t,w_t)\equiv \begin{cases} R_\Sigma+W_{\mathrm{odd}}, & s\equiv 0 \pmod 2,\\ \{R_\Sigma+W_{\mathrm{odd}}\mid R_\Sigma+W_{\mathrm{odd}}-w_s\}, & s\equiv 1 \pmod 2. \end{cases} $$
وهذه هي الفكرة الأساسية في مرحلة العد: بعد الفرز بحسب الوزن لا يبقى من جزء الـ switches إلا ثلاث كميات، وهي \(s\)، ومجموع النهايات اليمنى، ومجموع الأوزان الواقعة في المواقع الفردية.
بالنسبة إلى المكوّنات العددية الخالصة، تبني التطبيقات توزيعات التفاف مرتبة:
$$ N_n(\sigma)=\sum_{x_1+\cdots+x_n=\sigma}\prod_{t=1}^{n}f_{\mathrm{num}}(x_t), $$
وهي عدد التراتيب المرتبة ذات الطول \(n\) من الأعداد التي يكون مجموعها \(\sigma\).
ولوزن switch ثابت \(w\)، تبني كذلك
$$ D_{w,c}(\rho)=\sum_{R_1+\cdots+R_c=\rho}\prod_{t=1}^{c}f_w(R_t), $$
أي عدد التراتيب المرتبة ذات الطول \(c\) من switches وزنها \(w\) ومجموع نهاياتها اليمنى \(\rho\).
تعالج البرمجة الديناميكية المتناثرة الأوزان من الأكبر إلى الأصغر. وتمثل الحالة بالرباعي
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}), \qquad \pi=s\bmod 2, $$
حيث \(s\) عدد الـ switches المختارة، و\(\Sigma_R\) مجموع النهايات اليمنى المتراكم، و\(\Sigma_{\mathrm{odd}}\) مساهمة الأوزان في المواقع الفردية. وإذا أضفنا \(c\) switches جديدة ذات وزن \(w\) بعد الأوزان الأكبر التي عولجت سابقا، فإن عدد المواقع الفردية الجديدة يساوي
$$ \ell(c,\pi)= \begin{cases} \left\lceil\dfrac{c}{2}\right\rceil, & \pi=0,\\[4pt] \left\lfloor\dfrac{c}{2}\right\rfloor, & \pi=1. \end{cases} $$
ومن ثم يصبح الانتقال
$$ (s,\pi,\Sigma_R,\Sigma_{\mathrm{odd}}) \longrightarrow \bigl(s+c,\ \pi\oplus(c\bmod 2),\ \Sigma_R+\rho,\ \Sigma_{\mathrm{odd}}+\ell(c,\pi)w\bigr), $$
وبمعامل تعدد \(\binom{s+c}{c}D_{w,c}(\rho)\). ويظهر هذا العامل لأن المطلوب هو التراتيب المرتبة: فالـ switches الجديدة ذات الوزن \(w\) يمكن إدراجها بين الـ switches الأثقل المختارة سابقا بعدد \(\binom{s+c}{c}\) من الصور، مع الحفاظ على الترتيب الداخلي لكل مجموعة.
وبعد الانتهاء من جميع الأوزان، يجب أن تكون العناصر المتبقية وعددها \(m-s\) أعدادا صحيحة. وإقحام هذه الأعداد بين \(s\) switches يعطي عاملا إضافيا هو \(\binom{m}{s}\). وإذا ساهم الجزء العددي بمجموع \(\sigma\)، نضع
$$ T=\Sigma_R+\Sigma_{\mathrm{odd}}+\sigma. $$
فإذا كان \(s\) زوجيا كانت المحصلة النهائية هي العدد \(T\)، وعندها يفوز Left تماما عندما \(T>0\). وإذا كان \(s\) فرديا كانت المحصلة النهائية هي الـ switch \(\{T\mid T-w_s\}\)، وبما أن Left يستطيع أن ينتقل إلى \(T\)، فإنه يفوز عندما \(T\ge 0\). وبجمع الحالتين نحصل على القاعدة النهائية
$$ \text{Left wins}\iff \bigl(T>0\bigr)\lor\bigl(T=0\land s\equiv 1 \pmod 2\bigr). $$
عندما \(W=4\)، تعطي الثلاثيات المسموح بها أربع قيم فقط:
$$ G_{1,1,1}=0,\qquad G_{1,1,2}=\{0\mid 0\},\qquad G_{1,2,1}=1,\qquad G_{2,1,1}=-1. $$
إذن يصبح الفهرس \(\{0,\{0\mid 0\},1,-1\}\). والأزواج المرتبة الرابحة لـ Left هي
$$ (0,\{0\mid0\}),\ (\{0\mid0\},0),\ (0,1),\ (1,0),\ (1,\{0\mid0\}),\ (\{0\mid0\},1),\ (1,1). $$
ومن ثم
$$ S(2,4)=7, $$
وهو بالضبط مقدار الفحص الذي يتحقق منه الحل قبل الانتقال إلى المدخلات الأكبر.
يدور تنفيذا C++ وJava على جميع قيم \(a\) و\(b\). ولكل زوج ثابت منهما يملآن جدولا ثلاثي الأبعاد على المؤشرات \((k,i,j)\) بترتيب عكسي، بحيث تكون جميع الخيارات اليسرى واليمنى قد بُنيت بالفعل عندما يحين وقت اختزال الحالة الحالية. وبهذا تُنفذ العودية السلمية السابقة مباشرة.
بعد الاختزال القانوني لكل مكوّن \(G_{a,b,k}(0,0)\)، تحسب التطبيقات stop-pair الخاص به. وتُحصى المكوّنات العددية بحسب قيمتها الصحيحة، بينما تُشترط في المكوّنات غير العددية بنية مكونة من خيار أيسر واحد وخيار أيمن واحد وكلاهما عدد، وعندها تسجل على صورة switch من الشكل \(X(R,w)\) بواسطة النهاية اليمنى \(R\) والوزن \(w\).
بعد ضغط الفهرس في جداول تكرار، تحسب التطبيقات مسبقا التفافات مرتبة للأعداد ولكل وزن من أوزان الـ switches، ثم تشغّل البرمجة الديناميكية المتناثرة على الأوزان تنازليا، وفي النهاية تدمج كل حالة switch قابلة للوصول مع التوزيع العددي المناسب. أما تنفيذ Python فلا يعيد بناء محرك اللعبة، بل يستدعي الحل المترجم ويرجع نتيجته بعد تحليلها.
عنق الزجاجة البنيوي هو مرحلة بناء الفهرس. فعند تثبيت \(a\) و\(b\)، يكون عدد الحالات في الجدول المؤقت هو \((K+1)ab\) حيث \(K=W-a-b\). وبالجمع على جميع الأزواج المسموح بها نحصل على
$$ \sum_{a=1}^{W-2}\sum_{b=1}^{W-a-1}ab(W-a-b)=\Theta(W^5). $$
وتستخدم هذه المرحلة مساحة مؤقتة من رتبة \(O(W^3)\) لعائلة سلمية واحدة في كل مرة، بالإضافة إلى ذاكرة حفظ للقيم القانونية. أما مرحلة العد فمتعددة الحدود في \(m\) وفي أحجام دعم التوزيعات العددية وتوزيعات الـ switches والحالات القابلة للوصول في الـ DP المتناثر. ولهذا يصبح حساب \(S(8,64)\) ممكنا عمليا: فالبرنامج يعدّ أنماط التكرار، لا جميع التراتيب المرتبة على نحو صريح.