For a sheet of size \(w \times h\), a legal move chooses an interior grid point \((i,j)\) with \(1 \le i \lt w\) and \(1 \le j \lt h\), then cuts through that point both vertically and horizontally. The current position therefore breaks into four independent rectangles of sizes \(i \times j\), \((w-i) \times j\), \(i \times (h-j)\), and \((w-i) \times (h-j)\).
The solver tracks two quantities for every rectangle: its Sprague-Grundy value \(g_w(h)\), and the number \(c_w(h)\) of legal cuts whose resulting xor is zero. The target quantity is
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
with the final computation using \(W=123\) and \(H=1{,}234{,}567\). A direct evaluation would inspect an enormous number of cuts, so the whole solution depends on recognizing that, for fixed width, the height behavior eventually stabilizes.
The computation proceeds width by width. Once every smaller width has been reduced to a short explicit prefix plus a constant tail, the next width can be solved by combining those earlier tails instead of exploring every large height separately.
If a \(w \times h\) sheet is cut at \((i,j)\), the four subrectangles are independent impartial subgames, so the child nimber is
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]
Therefore
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]
and the companion count is
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]
The symmetry \(j \leftrightarrow h-j\) is immediate: replacing the top pair of rectangles by the bottom pair does not change the xor. The implementation uses that symmetry to process only half of the horizontal cuts explicitly.
For fixed width \(w\) and fixed vertical split \(i\), define
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]
Then the four-rectangle xor simplifies to
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]
This is the key reduction in the solver. Instead of rebuilding four subrectangles for every cut, it first precomputes the sequences \(a_i(t)\), and then each height \(h\) is handled by pairing the entries at \(j\) and \(h-j\).
One immediate consequence is that if \(h\) is even and \(j=h/2\), then
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
So every vertical split contributes at least one zero-xor move on the center line whenever the height is even.
Assume that for each smaller width \(u \lt w\) there is a threshold \(T_u\) and a constant tail nimber \(g_u^{(\infty)}\) such that
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
For a fixed split \(i\), put
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]
Then \(a_i(t)=\alpha_i\) for all \(t\ge \tau_i\). Now suppose \(h\ge 2\tau_i+1\). The two numbers \(j\) and \(h-j\) cannot both be \(\lt \tau_i\), because their sum is \(h\). Hence every cut for this split falls into one of two classes:
\[ x_{i,j}(h)=0 \quad \text{if both } j,h-j \ge \tau_i, \]
or
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{for a unique boundary value } t \lt \tau_i. \]
So once \(h\) is large enough, the set of reachable nimbers contributed by split \(i\) no longer depends on \(h\). Taking the maximum over all vertical splits gives the safe bound
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]
For every \(h\ge B_w\), the full move set of the \(w \times h\) position is identical, so the Grundy value is constant on that tail. Write the constant as \(g_w^{(\infty)}\). The true first stable height \(T_w\) may be smaller than \(B_w\), but \(B_w\) is the point where the proof becomes unconditional.
For one fixed split \(i\) and one height \(h\ge 2\tau_i+1\), the zero-xor cuts can be counted exactly.
The middle band \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) has length \(h-2\tau_i+1\), and every cut in that band satisfies \(a_i(j)=a_i(h-j)=\alpha_i\), so it contributes xor \(0\).
Boundary cuts come in symmetric pairs \(j=t\) and \(j=h-t\) with \(1\le t \lt \tau_i\). Such a pair contributes xor \(0\) exactly when \(a_i(t)=\alpha_i\). If we define
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]
then the contribution of split \(i\) is
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]
Summing over all \(i=1,2,\dots,w-1\) yields the linear tail formula
\[ c_w(h)=(w-1)h+\beta_w, \]
where
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
This identity is the main reason the problem is tractable for a huge height bound: once \(B_w\) is reached, the remaining contribution of width \(w\) is just an arithmetic progression.
The small case \(w=5\), \(h=3\) is useful because it already shows the true four-rectangle recurrence. The only horizontal cuts are \(j=1\) and \(j=2\), and those are symmetric. From smaller widths we have
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
For the split \(i=1\) (and symmetrically \(i=4\)),
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]
For the split \(i=2\) (and symmetrically \(i=3\)),
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]
Because \(j=1\) and \(j=2\) give the same xor, the four cuts with \(i=2\) or \(i=3\) are exactly the zero-xor moves. Hence
\[ c_5(3)=4. \]
The reachable nimbers are \(\{0,1\}\), so
\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]
This is one of the small configurations checked by the solver before the full target sum is accumulated.
The C++, Python, and Java implementations all expose the same mathematical pipeline. The C++ implementation performs the dynamic program directly, while the Python and Java front ends invoke that same compiled computation, so the logic below is the shared algorithmic core.
For each width \(w\), the implementation stores only three pieces of permanent information: a short prefix of explicit Grundy values, the first height \(T_w\) from which the tail is known to be constant, and the tail nimber \(g_w^{(\infty)}\). Any query \(g_w(h)\) is answered by reading the prefix if \(h \lt T_w\), and by returning \(g_w^{(\infty)}\) otherwise.
This is why the memory usage depends on the stabilization lengths rather than on the full target height \(H\).
When width \(w\) is being solved, the implementation first computes the safe bound \(B_w\). It then builds the auxiliary tables \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) for all \(1\le i \lt w\) and all heights up to \(B_w\).
For each \(h\le B_w\), it scans all vertical splits \(i\) and only half of the horizontal cuts \(j\), using the symmetry \(j \leftrightarrow h-j\) to mark reachable nimbers and to count zero-xor moves. Disjoint ranges of heights are assigned to worker threads, so a whole width layer is filled in parallel without changing the mathematics.
After the explicit prefix has been computed, the implementation constructs the stable move set from the boundary values \(t \lt \tau_i\), recovers \(g_w^{(\infty)}\), and computes the intercept \(\beta_w\) in the linear formula \(c_w(h)=(w-1)h+\beta_w\). It verifies those tail formulas against the last explicitly computed height before trusting them.
The true stabilization point \(T_w\) is then found by scanning backward inside the explicit prefix until the values stop differing from \(g_w^{(\infty)}\). Finally, the answer contribution of width \(w\) is split into two parts: the explicit prefix \(2\le h \lt B_w\), and the arithmetic-series tail
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
Before the final \(D(123,1{,}234{,}567)\) run, the implementation also checks a smaller benchmark and the sample count \(c_5(3)=4\).
If every rectangle up to height \(H\) were treated directly, then evaluating one state \(w \times h\) would inspect \((w-1)(h-1)\) cuts, and the total work would behave like \(O(W^2H^2)\). That is far too large for the target height.
With stabilization, width \(w\) is evaluated explicitly only up to \(B_w\). Building its prefix costs \(O(wB_w^2)\) time, because the solver processes all heights up to \(B_w\) and for each of them scans all width splits and roughly half of the horizontal cuts. After that, the entire tail contributes in \(O(1)\) time through the arithmetic-series formula. Permanent memory is \(O\!\left(\sum_{w=1}^{W} T_w\right)\) for the stored prefixes, plus \(O(wB_w)\) temporary workspace while the current width is being solved. Parallel threads reduce wall-clock time, but the crucial mathematical improvement is the replacement of dependence on the full \(H\) by dependence on the much smaller stabilization bounds.
Bei einem Blatt der Größe \(w \times h\) wählt ein legaler Zug einen inneren Gitterpunkt \((i,j)\) mit \(1 \le i \lt w\) und \(1 \le j \lt h\) und schneidet dort sowohl vertikal als auch horizontal durch. Dadurch zerfällt die Position in vier unabhängige Rechtecke der Größen \(i \times j\), \((w-i) \times j\), \(i \times (h-j)\) und \((w-i) \times (h-j)\).
Der Solver verfolgt für jedes Rechteck zwei Größen: den Sprague-Grundy-Wert \(g_w(h)\) und die Anzahl \(c_w(h)\) der legalen Schnitte, deren resultierendes xor gleich null ist. Gesucht ist
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
wobei in der Endrechnung \(W=123\) und \(H=1{,}234{,}567\) eingesetzt werden. Eine direkte Auswertung würde eine riesige Zahl von Schnitten untersuchen; deshalb beruht die Lösung darauf, dass sich das Verhalten für feste Breite in der Höhe schließlich stabilisiert.
Die Berechnung läuft Breite für Breite. Sobald jede kleinere Breite als kurzer expliziter Prefix plus konstanter Tail beschrieben ist, kann die nächste Breite aus diesen bereits bekannten Tails zusammengesetzt werden, statt jede große Höhe einzeln zu behandeln.
Wird ein \(w \times h\)-Rechteck bei \((i,j)\) geschnitten, entstehen vier unabhängige Teilspiele, also ist der Kind-Nimber
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]
Daher gilt
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]
und parallel dazu
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]
Die Symmetrie \(j \leftrightarrow h-j\) ist sofort sichtbar: Vertauscht man obere und untere Rechteckreihe, ändert sich das xor nicht. Deshalb verarbeitet die Implementierung nur die halbe Zahl horizontaler Schnittpositionen explizit.
Für feste Breite \(w\) und festen vertikalen Schnitt \(i\) definiert man
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]
Dann vereinfacht sich das xor der vier Teilrechtecke zu
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]
Genau diese Umformung ist der zentrale Kompressionsschritt im Solver. Statt für jeden Zug vier Teilrechtecke neu aufzubauen, werden zuerst die Folgen \(a_i(t)\) vorbereitet, und danach wird jede Höhe \(h\) durch das Paaren der Einträge bei \(j\) und \(h-j\) behandelt.
Eine unmittelbare Folge ist: Ist \(h\) gerade und \(j=h/2\), dann gilt
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
Also liefert jede vertikale Schnittposition bei gerader Höhe auf der Mittellinie mindestens einen Null-xor-Zug.
Nehmen wir an, dass es für jede kleinere Breite \(u \lt w\) eine Schwelle \(T_u\) und einen konstanten Tail-Nimber \(g_u^{(\infty)}\) gibt mit
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
Für einen festen Schnitt \(i\) setzen wir
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]
Dann ist \(a_i(t)=\alpha_i\) für alle \(t\ge \tau_i\). Gilt nun \(h\ge 2\tau_i+1\), so können die beiden Zahlen \(j\) und \(h-j\) nicht gleichzeitig \(\lt \tau_i\) sein, denn ihre Summe ist \(h\). Jeder Zug dieses Splits fällt also in eine von zwei Klassen:
\[ x_{i,j}(h)=0 \quad \text{falls } j,h-j \ge \tau_i, \]
oder
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{für genau einen Randwert } t \lt \tau_i. \]
Sobald \(h\) groß genug ist, hängt die von Split \(i\) erzeugte Menge erreichbarer Nimber also nicht mehr von \(h\) ab. Nimmt man das Maximum über alle vertikalen Splits, erhält man die sichere Schranke
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]
Für jedes \(h\ge B_w\) ist die vollständige Zugmenge der Position \(w \times h\) identisch; damit ist auch der Grundy-Wert auf diesem Tail konstant. Wir bezeichnen diesen Wert mit \(g_w^{(\infty)}\). Die tatsächliche erste stabile Höhe \(T_w\) kann kleiner als \(B_w\) sein, aber bei \(B_w\) greift der Beweis in voller Allgemeinheit.
Für einen festen Split \(i\) und eine Höhe \(h\ge 2\tau_i+1\) lässt sich die Zahl der Null-xor-Züge exakt bestimmen.
Das mittlere Band \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) hat Länge \(h-2\tau_i+1\), und jeder dieser Schnitte erfüllt \(a_i(j)=a_i(h-j)=\alpha_i\); sein xor ist also \(0\).
Die Randfälle kommen in symmetrischen Paaren \(j=t\) und \(j=h-t\) mit \(1\le t \lt \tau_i\). Ein solches Paar liefert genau dann xor \(0\), wenn \(a_i(t)=\alpha_i\) gilt. Definiert man
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]
dann ist der Beitrag dieses Splits
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]
Über alle \(i=1,2,\dots,w-1\) summiert folgt die lineare Tail-Formel
\[ c_w(h)=(w-1)h+\beta_w, \]
wobei
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
Gerade diese Identität macht das Problem für eine riesige Höhengrenze beherrschbar: Ab \(B_w\) ist der restliche Beitrag der Breite \(w\) nur noch eine arithmetische Folge.
Der kleine Fall \(w=5\), \(h=3\) zeigt bereits die echte Rekurrenz mit vier Teilrechtecken. Als horizontale Schnitte kommen nur \(j=1\) und \(j=2\) in Frage, und diese beiden Fälle sind symmetrisch. Aus kleineren Breiten kennt man
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
Für den Split \(i=1\) (symmetrisch auch \(i=4\)) gilt
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]
Für den Split \(i=2\) (symmetrisch auch \(i=3\)) gilt
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]
Da \(j=1\) und \(j=2\) dasselbe xor liefern, sind genau die vier Schnitte mit \(i=2\) oder \(i=3\) Null-xor-Züge. Also
\[ c_5(3)=4. \]
Die erreichbaren Nimber sind \(\{0,1\}\), also
\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]
Dies ist eine der kleinen Konfigurationen, die der Solver vor der Endsumme überprüft.
Die Implementierungen in C++, Python und Java stellen alle dieselbe mathematische Pipeline bereit. Die dynamische Programmierung selbst läuft in C++, während Python und Java dieselbe kompilierte Berechnung aufrufen; der folgende Ablauf ist also der gemeinsame algorithmische Kern.
Für jede Breite \(w\) speichert die Implementierung dauerhaft nur drei Informationen: einen kurzen Prefix expliziter Grundy-Werte, die erste Höhe \(T_w\), ab der der Tail sicher konstant ist, und den Tail-Nimber \(g_w^{(\infty)}\). Eine Anfrage \(g_w(h)\) wird daher durch Zugriff auf den Prefix beantwortet, falls \(h \lt T_w\), und sonst durch Rückgabe von \(g_w^{(\infty)}\).
Deshalb hängt der Speicherbedarf von den Stabilisierungslängen ab und nicht von der vollen Zielhöhe \(H\).
Wenn Breite \(w\) gelöst wird, bestimmt die Implementierung zunächst die sichere Schranke \(B_w\). Danach baut sie die Hilfstabellen \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) für alle \(1\le i \lt w\) und alle Höhen bis \(B_w\) auf.
Für jedes \(h\le B_w\) werden dann alle vertikalen Splits \(i\) und nur die halbe Zahl horizontaler Schnitte \(j\) durchlaufen; die Symmetrie \(j \leftrightarrow h-j\) dient sowohl zum Markieren der erreichbaren Nimber als auch zum Zählen der Null-xor-Züge. Getrennte Höhenbereiche werden verschiedenen Worker-Threads zugewiesen, sodass eine komplette Breitenebene parallel berechnet wird, ohne die Mathematik zu verändern.
Nach der expliziten Prefix-Berechnung konstruiert die Implementierung aus den Randwerten \(t \lt \tau_i\) die stabile Zugmenge, bestimmt daraus \(g_w^{(\infty)}\) und berechnet den Achsenabschnitt \(\beta_w\) in der linearen Formel \(c_w(h)=(w-1)h+\beta_w\). Diese Tail-Formeln werden noch am letzten explizit berechneten Höhenwert gegengeprüft, bevor sie verwendet werden.
Danach wird der echte Stabilisierungspunkt \(T_w\) durch Rückwärtssuche im Prefix gefunden. Der Beitragsanteil der Breite \(w\) zerfällt schließlich in zwei Teile: den expliziten Prefix \(2\le h \lt B_w\) und den Tail als arithmetische Reihe
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
Vor der endgültigen Rechnung für \(D(123,1{,}234{,}567)\) überprüft die Implementierung außerdem einen kleineren Benchmark und den Musterwert \(c_5(3)=4\).
Würde man jedes Rechteck bis Höhe \(H\) direkt behandeln, müsste für einen Zustand \(w \times h\) jeder der \((w-1)(h-1)\) Schnitte betrachtet werden; insgesamt ergäbe sich also ein Aufwand in der Größenordnung \(O(W^2H^2)\). Für die Zielhöhe wäre das unbrauchbar.
Mit Stabilisierung wird Breite \(w\) nur bis \(B_w\) explizit ausgewertet. Der Aufbau dieses Prefix kostet \(O(wB_w^2)\) Zeit, weil alle Höhen bis \(B_w\) berechnet werden und für jede Höhe alle Breitenaufteilungen sowie ungefähr die halbe Zahl horizontaler Schnitte geprüft werden. Danach kostet der gesamte Tail nur noch \(O(1)\) Zeit dank der Formel für die arithmetische Reihe. Der permanente Speicherbedarf ist \(O\!\left(\sum_{w=1}^{W} T_w\right)\) für die gespeicherten Prefixe, dazu kommt \(O(wB_w)\) temporärer Arbeitsraum für die aktuell behandelte Breite. Parallele Threads verkürzen die Laufzeit in der Praxis, aber die entscheidende mathematische Verbesserung ist die Ersetzung der Abhängigkeit von der vollen Höhe \(H\) durch die wesentlich kleineren Stabilisierungsschranken.
\(w \times h\) boyutlu bir kağıtta legal hamle, \(1 \le i \lt w\) ve \(1 \le j \lt h\) koşullarını sağlayan iç bir ızgara noktası \((i,j)\) seçip o noktadan hem dikey hem yatay tam kesim yapmaktır. Böylece konum, boyutları sırasıyla \(i \times j\), \((w-i) \times j\), \(i \times (h-j)\) ve \((w-i) \times (h-j)\) olan dört bağımsız dikdörtgene ayrılır.
Çözücü her dikdörtgen için iki büyüklük tutar: Sprague-Grundy değeri \(g_w(h)\) ve sonucu xor bakımından sıfır yapan legal kesim sayısı \(c_w(h)\). İstenen toplam
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
olup nihai hesapta \(W=123\) ve \(H=1{,}234{,}567\) kullanılır. Doğrudan yaklaşım, çok büyük sayıda kesimi tek tek incelemeyi gerektirir; bu yüzden çözümün kalbi, sabit genişlik için yükseklik davranışının bir noktadan sonra kararlı hale geldiğini fark etmektir.
Hesaplama genişlik bazında ilerler. Daha küçük her genişlik, kısa bir açık prefix ve sabit bir kuyruk değerine indirgendikten sonra, sıradaki genişlik büyük yükseklikleri tek tek dolaşmadan bu önceden bilinen kuyruklardan üretilebilir.
\(w \times h\) boyutlu bir kağıt \((i,j)\) noktasından kesildiğinde ortaya çıkan dört parça birbirinden bağımsız tarafsız alt oyunlardır. Bu nedenle çocuk nimber
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j) \]
olur. Buradan
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\} \]
ve eşzamanlı olarak
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\} \]
tanımları gelir. \(j \leftrightarrow h-j\) simetrisi açıktır: üstteki iki parçayla alttaki iki parçayı yer değiştirmek xoru değiştirmez. Uygulama bu yüzden yatay kesimlerin yalnızca yarısını açıkça işler.
Sabit \(w\) ve sabit dikey bölme \(i\) için
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t) \]
tanımını yapalım. O zaman dört parçanın xoru
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j) \]
şekline iner. Çözücüdeki temel sıkıştırma tam olarak budur. Her hamlede dört alt dikdörtgeni baştan kurmak yerine önce \(a_i(t)\) dizileri hazırlanır, sonra her yükseklik \(h\), \(j\) ile \(h-j\) çiftlenerek çözülür.
Bunun hemen görülen bir sonucu da şudur: \(h\) çift ve \(j=h/2\) ise
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
Yani yükseklik çift olduğunda, her dikey bölme merkez çizgisinde en az bir sıfır-xor hamlesi üretir.
Her küçük genişlik \(u \lt w\) için bir eşik \(T_u\) ve bir sabit kuyruk nimberi \(g_u^{(\infty)}\) bulunduğunu varsayalım:
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
Sabit bir bölme \(i\) için
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)} \]
olsun. O halde \(t\ge \tau_i\) için \(a_i(t)=\alpha_i\) olur. Şimdi \(h\ge 2\tau_i+1\) kabul edelim. Bu durumda \(j\) ile \(h-j\) aynı anda \(\lt \tau_i\) olamaz; çünkü toplamları \(h\)'dir. Dolayısıyla bu bölme için her hamle iki sınıftan birine düşer:
\[ x_{i,j}(h)=0 \quad \text{eğer } j,h-j \ge \tau_i, \]
ya da
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{burada } t \lt \tau_i \text{ olan tek bir sınır değeri vardır.} \]
Demek ki \(h\) yeterince büyüdüğünde, \(i\) bölmesinin ürettiği erişilebilir nimber kümesi artık \(h\)'ye bağlı değildir. Bunu tüm dikey bölmeler için aynı anda güvenceye alan üst sınır
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1) \]
şeklindedir. \(h\ge B_w\) için \(w \times h\) konumunun tüm hamle kümesi sabit olur; dolayısıyla Grundy değeri de kuyrukta sabittir. Bu sabite \(g_w^{(\infty)}\) diyelim. Gerçek ilk kararlı yükseklik \(T_w\), \(B_w\)'den daha küçük olabilir; fakat kanıtın koşulsuz çalıştığı nokta \(B_w\)'dir.
Sabit bir \(i\) bölmesi ve \(h\ge 2\tau_i+1\) yüksekliği için sıfır-xor hamleleri tam olarak sayabiliriz.
Orta bant \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) uzunluk olarak \(h-2\tau_i+1\) eder ve bu banttaki her kesim için \(a_i(j)=a_i(h-j)=\alpha_i\) olduğundan xor sıfırdır.
Sınır bölgesindeki kesimler \(1\le t \lt \tau_i\) için \(j=t\) ve \(j=h-t\) biçiminde simetrik çiftlerdir. Böyle bir çift, ancak ve ancak \(a_i(t)=\alpha_i\) ise sıfır xor verir. O halde
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\} \]
tanımıyla, bu bölmenin katkısı
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i \]
olur. Tüm \(i=1,2,\dots,w-1\) üzerinden toplayınca lineer kuyruk formülü gelir:
\[ c_w(h)=(w-1)h+\beta_w, \]
burada
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
Devasa bir yükseklik sınırı için problemi çözülebilir yapan esas nokta budur: \(B_w\)'den sonra genişlik \(w\)'nin geri kalan tüm katkısı yalnızca bir aritmetik dizi toplamıdır.
Küçük \(w=5\), \(h=3\) örneği, gerçekten dört alt dikdörtgenli özyinelemeyi kullandığımızı açıkça gösterir. Yatay kesimler sadece \(j=1\) ve \(j=2\) olabilir; bunlar da simetriktir. Daha küçük genişliklerden şu değerler bilinir:
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
\(i=1\) bölmesi için (simetrik olarak \(i=4\) için de aynı şekilde)
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1 \]
olur. \(i=2\) bölmesi için (simetrik olarak \(i=3\) için de)
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0 \]
elde edilir. \(j=1\) ve \(j=2\) aynı xoru verdiği için, \(i=2\) veya \(i=3\) olan dört kesim tam olarak sıfır-xor hamleleridir. Bu yüzden
\[ c_5(3)=4. \]
Erişilebilen nimber kümesi \(\{0,1\}\) olduğundan
\[ g_5(3)=\operatorname{mex}\{0,1\}=2 \]
çıkar. Çözücü, tam hedef toplamına geçmeden önce bu küçük konfigürasyonu da kontrol eder.
C++, Python ve Java uygulamaları aynı matematiksel hattı dışarı verir. Dinamik programın kendisi C++ tarafında yürür; Python ve Java ise aynı derlenmiş hesabı çağırır. Bu nedenle aşağıdaki süreç üçü için de ortak algoritmik çekirdektir.
Her genişlik \(w\) için kalıcı olarak yalnızca üç bilgi saklanır: açıkça hesaplanmış kısa bir Grundy prefixi, kuyruğun sabit olduğunun bilindiği ilk yükseklik \(T_w\) ve kuyruk nimberi \(g_w^{(\infty)}\). Böylece \(g_w(h)\) sorgusu, \(h \lt T_w\) ise prefixten, aksi halde doğrudan \(g_w^{(\infty)}\) değerinden cevaplanır.
Belleğin tam \(H\) yerine yalnızca kararlılık uzunluklarına bağlı olmasının nedeni budur.
Genişlik \(w\) çözülürken önce güvenli sınır \(B_w\) hesaplanır. Daha sonra tüm \(1\le i \lt w\) için ve \(B_w\)'ye kadar olan yüksekliklerde \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) yardımcı tabloları kurulur.
Ardından her \(h\le B_w\) için bütün dikey bölmeler \(i\) ve yatay kesimlerin yalnızca yarısı dolaşılır; \(j \leftrightarrow h-j\) simetrisi hem erişilebilir nimberleri işaretlemek hem de sıfır-xor hamleleri saymak için kullanılır. Ayrık yükseklik aralıkları farklı iş parçacıklarına verildiği için, bir genişliğin tüm satırı matematik değişmeden paralel doldurulur.
Açık prefix tamamlandıktan sonra uygulama, \(t \lt \tau_i\) sınır değerlerinden kararlı hamle kümesini kurar, buradan \(g_w^{(\infty)}\) değerini ve \(c_w(h)=(w-1)h+\beta_w\) formülündeki \(\beta_w\) sabitini elde eder. Kuyruk formülleri kullanılmadan önce son açık yükseklikte doğrulanır.
Daha sonra prefix içinde geriye doğru gidilerek gerçek kararlılık noktası \(T_w\) bulunur. Genişlik \(w\)'nin nihai cevaba katkısı iki parçaya ayrılır: açık prefix \(2\le h \lt B_w\) ve aritmetik seri kuyruğu
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
Son \(D(123,1{,}234{,}567)\) hesabından önce uygulama daha küçük bir benchmarkı ve \(c_5(3)=4\) örnek sayımını da kontrol eder.
Eğer \(H\)'ye kadar olan her dikdörtgen doğrudan işlenseydi, tek bir \(w \times h\) durumunu değerlendirmek \((w-1)(h-1)\) kesimi incelemeyi gerektirirdi; toplam iş yükü de yaklaşık \(O(W^2H^2)\) olurdu. Bu, hedef yükseklik için aşırı büyüktür.
Kararlılık kullanıldığında genişlik \(w\) yalnızca \(B_w\)'ye kadar açıkça hesaplanır. Bu prefixin maliyeti \(O(wB_w^2)\) zamandır; çünkü \(B_w\)'ye kadar bütün yükseklikler çözülür ve her biri için tüm genişlik bölmeleri ile yatay kesimlerin yaklaşık yarısı taranır. Sonrasında tüm kuyruk, aritmetik seri formülü sayesinde \(O(1)\) zamanda toplanır. Kalıcı bellek, saklanan prefixler için \(O\!\left(\sum_{w=1}^{W} T_w\right)\), o anda çözülen genişlik için geçici çalışma alanı olarak da \(O(wB_w)\) düzeyindedir. Paralel iş parçacıkları duvar saati süresini düşürür; fakat esas matematiksel kazanım, tam \(H\)'ye bağlılığı çok daha küçük kararlılık sınırlarına indirgemektir.
Para una hoja de tamaño \(w \times h\), un movimiento legal elige un punto interior de la retícula \((i,j)\) con \(1 \le i \lt w\) y \(1 \le j \lt h\), y corta completamente por ese punto tanto en dirección vertical como horizontal. La posición se divide entonces en cuatro rectángulos independientes de tamaños \(i \times j\), \((w-i) \times j\), \(i \times (h-j)\) y \((w-i) \times (h-j)\).
El solucionador sigue dos cantidades para cada rectángulo: su valor de Sprague-Grundy \(g_w(h)\) y el número \(c_w(h)\) de cortes legales cuyo xor resultante es cero. La magnitud pedida es
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
y en el cálculo final se usan \(W=123\) y \(H=1{,}234{,}567\). Una evaluación directa revisaría una cantidad enorme de cortes, así que toda la solución depende de detectar que, para un ancho fijo, el comportamiento en altura termina estabilizándose.
El cálculo avanza ancho por ancho. Cuando cada ancho menor ya ha sido reducido a un prefijo explícito corto y una cola constante, el siguiente ancho puede resolverse combinando esas colas previas en vez de explorar una por una todas las alturas grandes.
Si una hoja \(w \times h\) se corta en \((i,j)\), los cuatro subrectángulos forman juegos imparciales independientes, así que el nimber hijo es
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]
Por tanto,
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]
y además
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]
La simetría \(j \leftrightarrow h-j\) es inmediata: intercambiar la pareja superior de rectángulos por la pareja inferior no altera el xor. Por eso la implementación solo procesa explícitamente la mitad de los cortes horizontales.
Para ancho fijo \(w\) y partición vertical fija \(i\), definimos
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]
Entonces el xor de los cuatro subrectángulos se simplifica a
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]
Esta es la compresión clave del algoritmo. En vez de reconstruir cuatro subrectángulos en cada movimiento, primero se precalculan las sucesiones \(a_i(t)\), y luego cada altura \(h\) se maneja emparejando los términos en \(j\) y \(h-j\).
Una consecuencia inmediata es que si \(h\) es par y \(j=h/2\), entonces
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
Así, toda partición vertical aporta al menos un movimiento de xor cero sobre la línea central cuando la altura es par.
Supongamos que para cada ancho menor \(u \lt w\) existe un umbral \(T_u\) y un nimber de cola constante \(g_u^{(\infty)}\) tales que
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
Para una partición fija \(i\), escribimos
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]
Entonces \(a_i(t)=\alpha_i\) para todo \(t\ge \tau_i\). Si ahora \(h\ge 2\tau_i+1\), los números \(j\) y \(h-j\) no pueden ser ambos \(\lt \tau_i\), porque su suma es \(h\). Por tanto, cada corte de esta partición cae en una de dos clases:
\[ x_{i,j}(h)=0 \quad \text{si } j,h-j \ge \tau_i, \]
o bien
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{para un valor de borde único } t \lt \tau_i. \]
Cuando \(h\) es suficientemente grande, el conjunto de nimbers alcanzables aportado por la partición \(i\) deja de depender de \(h\). Tomando el máximo sobre todas las particiones verticales se obtiene la cota segura
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]
Para todo \(h\ge B_w\), el conjunto completo de movimientos del estado \(w \times h\) es idéntico, así que el valor de Grundy es constante en esa cola. Denotemos esa constante por \(g_w^{(\infty)}\). La primera altura realmente estable \(T_w\) puede ser menor que \(B_w\), pero \(B_w\) es el punto donde la demostración ya funciona sin excepciones.
Para una partición fija \(i\) y una altura \(h\ge 2\tau_i+1\), el número de movimientos de xor cero se puede contar exactamente.
La banda central \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) tiene longitud \(h-2\tau_i+1\), y todos esos cortes cumplen \(a_i(j)=a_i(h-j)=\alpha_i\), así que su xor es \(0\).
Los cortes de borde aparecen en pares simétricos \(j=t\) y \(j=h-t\) con \(1\le t \lt \tau_i\). Un par así da xor \(0\) exactamente cuando \(a_i(t)=\alpha_i\). Si definimos
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]
entonces la contribución de esa partición es
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]
Sumando sobre todos los \(i=1,2,\dots,w-1\) se obtiene la fórmula lineal de la cola
\[ c_w(h)=(w-1)h+\beta_w, \]
donde
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
Esta identidad es la razón principal por la que el problema se vuelve tratable con una cota enorme de altura: una vez alcanzado \(B_w\), toda la contribución restante del ancho \(w\) es simplemente una progresión aritmética.
El caso pequeño \(w=5\), \(h=3\) ya muestra la verdadera recurrencia de cuatro subrectángulos. Los únicos cortes horizontales son \(j=1\) y \(j=2\), y son simétricos. De anchos menores se conocen los valores
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
Para la partición \(i=1\) (y simétricamente \(i=4\)),
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]
Para la partición \(i=2\) (y simétricamente \(i=3\)),
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]
Como \(j=1\) y \(j=2\) producen el mismo xor, los cuatro cortes con \(i=2\) o \(i=3\) son exactamente los movimientos de xor cero. Por lo tanto,
\[ c_5(3)=4. \]
Los nimbers alcanzables son \(\{0,1\}\), así que
\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]
Esta es una de las configuraciones pequeñas que el solucionador verifica antes de acumular la suma objetivo completa.
Las implementaciones en C++, Python y Java exponen la misma tubería matemática. La programación dinámica completa se ejecuta en C++, mientras que los frentes de Python y Java invocan ese mismo cálculo compilado; por eso el proceso siguiente es el núcleo algorítmico compartido.
Para cada ancho \(w\), la implementación guarda de forma permanente solo tres piezas de información: un prefijo corto de valores de Grundy explícitos, la primera altura \(T_w\) a partir de la cual la cola es constante, y el nimber de cola \(g_w^{(\infty)}\). Así, una consulta \(g_w(h)\) se responde leyendo el prefijo si \(h \lt T_w\), o devolviendo \(g_w^{(\infty)}\) en caso contrario.
Por eso el uso de memoria depende de las longitudes de estabilización y no de la altura total \(H\).
Cuando se resuelve el ancho \(w\), la implementación calcula primero la cota segura \(B_w\). Luego construye las tablas auxiliares \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) para todos los \(1\le i \lt w\) y todas las alturas hasta \(B_w\).
Para cada \(h\le B_w\), recorre todas las particiones verticales \(i\) y solo la mitad de los cortes horizontales \(j\), usando la simetría \(j \leftrightarrow h-j\) tanto para marcar nimbers alcanzables como para contar movimientos de xor cero. Rangos disjuntos de alturas se reparten entre hilos de trabajo, de modo que una capa completa de ancho se rellena en paralelo sin alterar la matemática.
Una vez calculado el prefijo explícito, la implementación construye el conjunto estable de movimientos a partir de los valores de borde \(t \lt \tau_i\), recupera \(g_w^{(\infty)}\) y calcula la ordenada \(\beta_w\) en la fórmula lineal \(c_w(h)=(w-1)h+\beta_w\). Esas fórmulas de cola se comprueban contra la última altura calculada explícitamente antes de utilizarlas.
Después, el verdadero punto de estabilización \(T_w\) se obtiene retrocediendo dentro del prefijo hasta el primer lugar en que ya no aparecen diferencias respecto a \(g_w^{(\infty)}\). Por último, la contribución del ancho \(w\) a la respuesta se divide en dos partes: el prefijo explícito \(2\le h \lt B_w\) y la cola como serie aritmética
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
Antes de ejecutar \(D(123,1{,}234{,}567)\), la implementación también comprueba un benchmark menor y el valor de muestra \(c_5(3)=4\).
Si se tratara cada rectángulo hasta altura \(H\) de forma directa, evaluar un estado \(w \times h\) exigiría inspeccionar \((w-1)(h-1)\) cortes, y el trabajo total crecería como \(O(W^2H^2)\). Eso es demasiado grande para la altura objetivo.
Con estabilización, el ancho \(w\) solo se evalúa explícitamente hasta \(B_w\). Construir ese prefijo cuesta \(O(wB_w^2)\) tiempo, porque el algoritmo procesa todas las alturas hasta \(B_w\) y para cada una revisa todas las particiones verticales y aproximadamente la mitad de los cortes horizontales. Después de eso, toda la cola aporta en tiempo \(O(1)\) mediante la fórmula de la progresión aritmética. La memoria permanente es \(O\!\left(\sum_{w=1}^{W} T_w\right)\) para los prefijos guardados, más \(O(wB_w)\) de espacio temporal mientras se resuelve el ancho actual. Los hilos reducen el tiempo de pared, pero la mejora matemática crucial es sustituir la dependencia de la altura total \(H\) por la dependencia de cotas de estabilización mucho más pequeñas.
对于一个 \(w \times h\) 的纸片，合法操作是选取一个内部格点 \((i,j)\)，其中 \(1 \le i \lt w\)、\(1 \le j \lt h\)，然后沿着经过该点的竖线和横线各切一次。这样当前局面就会分裂成四个彼此独立的矩形，尺寸分别是 \(i \times j\)、\((w-i) \times j\)、\(i \times (h-j)\) 和 \((w-i) \times (h-j)\)。
求解器对每个矩形同时跟踪两个量：Sprague-Grundy 值 \(g_w(h)\)，以及使得结果 xor 为零的合法切法个数 \(c_w(h)\)。题目要求的总量是
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
而最终计算使用的是 \(W=123\)、\(H=1{,}234{,}567\)。如果直接暴力，就必须检查海量切法，因此整套方法的核心在于：对固定宽度来说，高度方向上的行为最终会稳定下来。
整个计算按宽度递推。只要所有更小宽度都已经被压缩成“一个显式短前缀加一个常数尾部”，那么下一个宽度就可以借助这些已有尾部来求解，而不需要把所有大高度逐个展开。
如果一个 \(w \times h\) 的纸片在 \((i,j)\) 处被切开，那么得到的四个子矩形是四个独立的 impartial 子游戏，因此子局面的 nimber 是
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]
于是有
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]
并且同时定义
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]
这里立刻可以看到 \(j \leftrightarrow h-j\) 的对称性：把上面的两块与下面的两块互换，不会改变 xor。实现正是利用这个对称性，只显式枚举一半的水平切点。
固定宽度 \(w\) 以及一条竖向分割 \(i\)，定义
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]
那么四块矩形的 xor 就可以化简为
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]
这是程序中的关键压缩。它不再为每个切法重新构造四个子矩形，而是先预处理出所有 \(a_i(t)\)，然后在每个高度 \(h\) 上只需要把 \(j\) 与 \(h-j\) 配对即可。
一个直接推论是：如果 \(h\) 为偶数并且 \(j=h/2\)，那么
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
因此当高度为偶数时，每一条竖向分割都会在中线位置贡献至少一个 xor 为零的切法。
设对每个更小的宽度 \(u \lt w\)，都已经存在一个阈值 \(T_u\) 和一个常数尾部 nimber \(g_u^{(\infty)}\)，使得
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
对固定分割 \(i\)，记
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]
于是当 \(t\ge \tau_i\) 时，就有 \(a_i(t)=\alpha_i\)。现在若 \(h\ge 2\tau_i+1\)，则 \(j\) 与 \(h-j\) 不可能同时小于 \(\tau_i\)，因为它们的和就是 \(h\)。所以对这条分割而言，每个切法只会落入两类之一：
\[ x_{i,j}(h)=0 \quad \text{当 } j,h-j \ge \tau_i, \]
或者
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{其中 } t \lt \tau_i \text{ 是唯一的边界高度。} \]
这说明：一旦 \(h\) 足够大，分割 \(i\) 所能产生的可达 nimber 集合就不再依赖于 \(h\)。对所有竖向分割同时取最大值，就得到安全界
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]
当 \(h\ge B_w\) 时，\(w \times h\) 这个局面的完整合法后继集合已经固定，因此 Grundy 值也在这条尾部上变成常数。把这个常数记作 \(g_w^{(\infty)}\)。真正的首次稳定高度 \(T_w\) 可能比 \(B_w\) 更小，但 \(B_w\) 是证明无条件成立的安全起点。
对固定分割 \(i\) 和任意 \(h\ge 2\tau_i+1\)，可以把 xor 为零的切法精确数出来。
中间带状区域 \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) 的长度是 \(h-2\tau_i+1\)，其中每个切法都满足 \(a_i(j)=a_i(h-j)=\alpha_i\)，所以 xor 全都为 \(0\)。
边界部分由对称的切法对 \(j=t\) 与 \(j=h-t\) 组成，其中 \(1\le t \lt \tau_i\)。这对切法只有在 \(a_i(t)=\alpha_i\) 时才会贡献 xor \(0\)。如果定义
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]
那么这一条分割的贡献就是
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]
再对所有 \(i=1,2,\dots,w-1\) 求和，就得到线性尾部公式
\[ c_w(h)=(w-1)h+\beta_w, \]
其中
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
这正是问题之所以能在极大高度上仍可计算的关键原因：一旦到达 \(B_w\)，宽度 \(w\) 的剩余贡献就只是一个等差数列求和。
小例子 \(w=5\)、\(h=3\) 很有代表性，因为它已经能看出真正使用的是四矩形递推。此时只有两个水平切点 \(j=1\) 和 \(j=2\)，而且它们是对称的。由更小宽度可知
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
对于分割 \(i=1\)（对称地 \(i=4\) 也是一样），
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]
对于分割 \(i=2\)（对称地 \(i=3\) 也是一样），
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]
由于 \(j=1\) 和 \(j=2\) 给出的 xor 相同，所以所有 \(i=2\) 或 \(i=3\) 的四种切法恰好就是 xor 为零的切法。因此
\[ c_5(3)=4. \]
可达 nimber 集合是 \(\{0,1\}\)，于是
\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]
程序在进入最终目标和之前，就会先检查这个小规模构型。
C++、Python 和 Java 三个实现对外呈现的是同一条数学计算链。真正的动态规划在 C++ 中执行，而 Python 与 Java 前端调用的是同一个编译后的计算核心，因此下面描述的就是三者共享的算法流程。
对每个宽度 \(w\)，实现永久保存的只有三部分信息：一个显式算出的短 Grundy 前缀、尾部已经确定为常数的起始高度 \(T_w\)，以及尾部 nimber \(g_w^{(\infty)}\)。因此查询 \(g_w(h)\) 时，如果 \(h \lt T_w\) 就直接读前缀，否则返回 \(g_w^{(\infty)}\)。
这就是为什么内存消耗取决于稳定长度，而不是取决于完整目标高度 \(H\)。
当程序处理宽度 \(w\) 时，先计算安全界 \(B_w\)，再建立所有辅助表 \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\)，其中 \(1\le i \lt w\)，而 \(t\) 只需要到 \(B_w\) 为止。
对每个 \(h\le B_w\)，程序遍历所有竖向分割 \(i\)，并且只扫描一半水平切点 \(j\)，利用 \(j \leftrightarrow h-j\) 的对称性同时完成“标记可达 nimber”和“统计 xor 为零的切法数”这两件事。不同的高度区间分配给不同工作线程，因此一整层宽度可以并行填充，而且不会改变任何数学结果。
显式前缀算完后，实现会从边界值 \(t \lt \tau_i\) 构造稳定的后继集合，求出 \(g_w^{(\infty)}\)，并计算线性公式 \(c_w(h)=(w-1)h+\beta_w\) 里的截距 \(\beta_w\)。在正式信任这些尾部公式之前，程序还会把它们与最后一个显式高度上的结果做核对。
随后，它在显式前缀里向后回扫，找出真正的稳定起点 \(T_w\)。最后，宽度 \(w\) 对总答案的贡献被拆成两段：一段是显式前缀 \(2\le h \lt B_w\)，另一段是等差数列尾部
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
在执行最终的 \(D(123,1{,}234{,}567)\) 之前，实现还会检查一个较小的基准例子以及样例值 \(c_5(3)=4\)。
如果对所有高度直到 \(H\) 的矩形都直接处理，那么评价一个 \(w \times h\) 状态需要检查 \((w-1)(h-1)\) 个切法，总工作量会呈现 \(O(W^2H^2)\) 的规模。对于目标高度来说，这显然过大。
有了稳定尾部之后，宽度 \(w\) 只需要显式算到 \(B_w\)。构造这段前缀的时间代价是 \(O(wB_w^2)\)，因为程序要处理所有不超过 \(B_w\) 的高度，并且对每个高度扫描所有竖向分割与大约一半的水平切点。此后整段尾部都可以用等差数列公式在 \(O(1)\) 时间内加入答案。永久内存是保存前缀所需的 \(O\!\left(\sum_{w=1}^{W} T_w\right)\)，再加上当前宽度求解时用到的 \(O(wB_w)\) 临时工作空间。多线程降低的是实际墙钟时间；真正关键的数学改进，是把对完整 \(H\) 的依赖替换成了对远小得多的稳定界的依赖。
Для листа размера \(w \times h\) допустимый ход выбирает внутреннюю точку решетки \((i,j)\), где \(1 \le i \lt w\) и \(1 \le j \lt h\), а затем делает через нее полный вертикальный и полный горизонтальный разрез. В результате позиция распадается на четыре независимых прямоугольника размеров \(i \times j\), \((w-i) \times j\), \(i \times (h-j)\) и \((w-i) \times (h-j)\).
Решатель отслеживает для каждого прямоугольника две величины: значение Спрага-Гранди \(g_w(h)\) и число \(c_w(h)\) допустимых разрезов, у которых результирующий xor равен нулю. Требуется вычислить
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
причем в финальном запуске используются \(W=123\) и \(H=1{,}234{,}567\). Прямой перебор потребовал бы проверять колоссальное количество разрезов, поэтому весь метод опирается на тот факт, что при фиксированной ширине зависимость от высоты в конце концов стабилизируется.
Вычисление идет по ширинам. Когда каждая меньшая ширина уже сведена к короткому явному префиксу и постоянному хвосту, следующую ширину можно строить из этих уже известных хвостов, а не просчитывать по отдельности все большие высоты.
Если лист \(w \times h\) разрезан в точке \((i,j)\), получаются четыре независимые беспристрастные подигры, поэтому nimber дочерней позиции равен
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]
Следовательно,
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]
а также
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]
Симметрия \(j \leftrightarrow h-j\) здесь очевидна: если поменять местами верхнюю пару прямоугольников с нижней, xor не изменится. Поэтому реализация явно просматривает только половину горизонтальных разрезов.
Для фиксированной ширины \(w\) и фиксированного вертикального разбиения \(i\) введем
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]
Тогда xor четырех подпрямоугольников упрощается до
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]
Именно это преобразование и является главным сжатием в решателе. Вместо того чтобы заново собирать четыре подпрямоугольника для каждого хода, программа сначала подготавливает последовательности \(a_i(t)\), а потом для каждой высоты \(h\) просто сопоставляет значения в точках \(j\) и \(h-j\).
Немедленное следствие: если \(h\) четно и \(j=h/2\), то
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
То есть при четной высоте каждое вертикальное разбиение гарантированно дает хотя бы один нулевой по xor ход на центральной линии.
Предположим, что для каждой меньшей ширины \(u \lt w\) уже существует порог \(T_u\) и постоянный хвостовой nimber \(g_u^{(\infty)}\), такие что
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
Для фиксированного разбиения \(i\) положим
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]
Тогда \(a_i(t)=\alpha_i\) для всех \(t\ge \tau_i\). Теперь пусть \(h\ge 2\tau_i+1\). Числа \(j\) и \(h-j\) не могут одновременно быть меньше \(\tau_i\), потому что их сумма равна \(h\). Следовательно, каждый ход для этого разбиения попадает в один из двух типов:
\[ x_{i,j}(h)=0 \quad \text{если } j,h-j \ge \tau_i, \]
или
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{для единственного граничного значения } t \lt \tau_i. \]
Значит, как только \(h\) становится достаточно большим, множество достижимых nimber-ов, возникающих от разбиения \(i\), перестает зависеть от \(h\). Беря максимум по всем вертикальным разбиениям, получаем надежную границу
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]
Для каждого \(h\ge B_w\) полное множество ходов позиции \(w \times h\) уже одинаково, а значит и значение Гранди на этом хвосте постоянно. Обозначим эту константу через \(g_w^{(\infty)}\). Настоящая первая стабильная высота \(T_w\) может оказаться меньше \(B_w\), но именно \(B_w\) является точкой, начиная с которой доказательство работает безусловно.
Для фиксированного разбиения \(i\) и высоты \(h\ge 2\tau_i+1\) число нулевых по xor ходов можно посчитать точно.
Средняя полоса \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) имеет длину \(h-2\tau_i+1\), и каждый такой разрез удовлетворяет равенству \(a_i(j)=a_i(h-j)=\alpha_i\), так что xor равен нулю.
Граничные разрезы образуют симметричные пары \(j=t\) и \(j=h-t\) при \(1\le t \lt \tau_i\). Такая пара дает xor \(0\) тогда и только тогда, когда \(a_i(t)=\alpha_i\). Если определить
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]
то вклад этого разбиения равен
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]
Суммируя по всем \(i=1,2,\dots,w-1\), получаем линейную хвостовую формулу
\[ c_w(h)=(w-1)h+\beta_w, \]
где
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
Именно это тождество и делает задачу выполнимой при огромной верхней границе по высоте: после достижения \(B_w\) весь оставшийся вклад ширины \(w\) сводится к сумме арифметической прогрессии.
Малый случай \(w=5\), \(h=3\) полезен тем, что уже демонстрирует настоящую рекурсию с четырьмя подпрямоугольниками. Горизонтальные разрезы здесь только два: \(j=1\) и \(j=2\), и они симметричны. Из меньших ширин известны значения
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
Для разбиения \(i=1\) (симметрично и для \(i=4\)) имеем
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]
Для разбиения \(i=2\) (симметрично и для \(i=3\)) имеем
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]
Поскольку \(j=1\) и \(j=2\) дают одинаковый xor, четыре разреза с \(i=2\) или \(i=3\) и есть все нулевые по xor ходы. Следовательно,
\[ c_5(3)=4. \]
Множество достижимых nimber-ов равно \(\{0,1\}\), поэтому
\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]
Это одна из малых конфигураций, которые решатель проверяет перед полным итоговым запуском.
Реализации на C++, Python и Java предоставляют один и тот же математический конвейер. Сама динамика выполняется в C++, а интерфейсы Python и Java вызывают то же скомпилированное вычисление, поэтому описанный ниже процесс является общим алгоритмическим ядром.
Для каждой ширины \(w\) программа хранит постоянно только три вещи: короткий префикс явно вычисленных значений Гранди, первую высоту \(T_w\), начиная с которой хвост гарантированно постоянен, и хвостовой nimber \(g_w^{(\infty)}\). Поэтому запрос \(g_w(h)\) обрабатывается так: если \(h \lt T_w\), читается префикс, иначе возвращается \(g_w^{(\infty)}\).
Именно поэтому потребление памяти зависит от длин стабилизации, а не от полной целевой высоты \(H\).
Когда решается ширина \(w\), сначала вычисляется надежная граница \(B_w\). Затем строятся вспомогательные таблицы \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) для всех \(1\le i \lt w\) и для всех высот до \(B_w\).
Для каждого \(h\le B_w\) программа перебирает все вертикальные разбиения \(i\) и только половину горизонтальных разрезов \(j\), используя симметрию \(j \leftrightarrow h-j\) одновременно и для отметки достижимых nimber-ов, и для подсчета нулевых по xor ходов. Непересекающиеся диапазоны высот распределяются между рабочими потоками, так что целый слой по ширине заполняется параллельно без изменения результата.
После вычисления явного префикса реализация строит стабильное множество ходов из граничных значений \(t \lt \tau_i\), восстанавливает \(g_w^{(\infty)}\) и вычисляет коэффициент \(\beta_w\) в линейной формуле \(c_w(h)=(w-1)h+\beta_w\). Перед тем как полагаться на эти хвостовые формулы, программа сверяет их с последней высотой, посчитанной явно.
Затем настоящий момент стабилизации \(T_w\) находится обратным просмотром явного префикса. Вклад ширины \(w\) в ответ распадается на две части: явный префикс \(2\le h \lt B_w\) и хвост как арифметическая прогрессия
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
Перед финальным запуском для \(D(123,1{,}234{,}567)\) реализация также проверяет меньший контрольный пример и значение \(c_5(3)=4\).
Если бы каждый прямоугольник до высоты \(H\) обрабатывался напрямую, то для состояния \(w \times h\) пришлось бы проверять \((w-1)(h-1)\) разрезов, а общий объем работы рос бы как \(O(W^2H^2)\). Для целевой высоты это слишком дорого.
Благодаря стабилизации ширина \(w\) явно вычисляется только до \(B_w\). Построение этого префикса требует \(O(wB_w^2)\) времени, потому что программа проходит все высоты до \(B_w\), а для каждой из них перебирает все вертикальные разбиения и примерно половину горизонтальных разрезов. После этого весь хвост добавляется за \(O(1)\) времени по формуле арифметической прогрессии. Постоянная память составляет \(O\!\left(\sum_{w=1}^{W} T_w\right)\) для сохраненных префиксов, плюс \(O(wB_w)\) временного рабочего пространства при обработке текущей ширины. Потоки уменьшают реальное время выполнения, но главный математический выигрыш состоит в замене зависимости от полного \(H\) зависимостью от гораздо меньших границ стабилизации.
لدينا ورقة بحجم \(w \times h\). الحركة القانونية تختار نقطة شبكية داخلية \((i,j)\) بحيث \(1 \le i \lt w\) و\(1 \le j \lt h\)، ثم تُجرى عبرها قطعتان كاملتان: واحدة رأسية وأخرى أفقية. وبهذا تنقسم الوضعية إلى أربعة مستطيلات مستقلة أحجامها \(i \times j\)، و\((w-i) \times j\)، و\(i \times (h-j)\)، و\((w-i) \times (h-j)\).
يتتبع الحل لكل مستطيل مقدارين معًا: قيمة Sprague-Grundy وهي \(g_w(h)\)، وعدد القطوع القانونية التي يكون xor الناتج عنها مساويًا للصفر، وهو \(c_w(h)\). والكمية المطلوبة هي
\[ D(W,H)=\sum_{w=2}^{W}\sum_{h=2}^{H} c_w(h), \]
وفي الحساب النهائي نستخدم \(W=123\) و\(H=1{,}234{,}567\). التقييم المباشر سيفحص عددًا هائلًا من القطوع، لذلك تقوم الفكرة كلها على ملاحظة أن السلوك بالنسبة للارتفاع، عند تثبيت العرض، يستقر بعد حد معين.
يسير الحساب عرضًا بعد عرض. ما إن تختزل كل العروض الأصغر إلى بادئة صريحة قصيرة وذيل ثابت، حتى يمكن حل العرض التالي بالاعتماد على تلك الذيول المعروفة بدلًا من معالجة كل ارتفاع كبير على حدة.
إذا قُطعت ورقة \(w \times h\) عند \((i,j)\)، فإن المستطيلات الأربعة الناتجة تمثل ألعابًا محايدة مستقلة، ولذلك يكون nimber الابن مساويًا لـ
\[ x_{i,j}(h)=g_i(j)\oplus g_{w-i}(j)\oplus g_i(h-j)\oplus g_{w-i}(h-j). \]
ومن ثم
\[ g_w(h)=\operatorname{mex}\{x_{i,j}(h):1\le i \lt w,\ 1\le j \lt h\}, \]
كما نعرّف في الوقت نفسه
\[ c_w(h)=\#\{(i,j):1\le i \lt w,\ 1\le j \lt h,\ x_{i,j}(h)=0\}. \]
إن التناظر \(j \leftrightarrow h-j\) واضح هنا: تبديل الزوج العلوي من المستطيلات بالزوج السفلي لا يغيّر قيمة xor. ولهذا السبب تعالج الشيفرة نصف مواضع القطع الأفقية فقط بشكل صريح.
لثبات \(w\) وثبات التقسيم الرأسي \(i\)، نعرّف
\[ a_i(t)=g_i(t)\oplus g_{w-i}(t). \]
وعندها يتبسط xor المستطيلات الأربعة إلى
\[ x_{i,j}(h)=a_i(j)\oplus a_i(h-j). \]
هذا هو الاختزال الأساسي الذي يستخدمه الحل. فبدلًا من إعادة بناء أربعة مستطيلات فرعية في كل حركة، تُحسب أولًا المتتاليات \(a_i(t)\)، ثم يُعالج كل ارتفاع \(h\) من خلال مزاوجة الحدين عند \(j\) و\(h-j\).
ومن النتائج المباشرة لذلك أنه إذا كان \(h\) زوجيًا و\(j=h/2\)، فإن
\[ x_{i,h/2}(h)=a_i(h/2)\oplus a_i(h/2)=0. \]
أي إن كل تقسيم رأسي يقدّم حركة واحدة على الأقل ذات xor صفري على خط المنتصف عندما يكون الارتفاع زوجيًا.
افترض أنه لكل عرض أصغر \(u \lt w\) يوجد عتبة \(T_u\) وقيمة ذيل ثابتة \(g_u^{(\infty)}\) بحيث
\[ g_u(t)=g_u^{(\infty)} \qquad (t\ge T_u). \]
ولكل تقسيم ثابت \(i\) نضع
\[ \tau_i=\max(T_i,T_{w-i}), \qquad \alpha_i=g_i^{(\infty)}\oplus g_{w-i}^{(\infty)}. \]
وعندئذ يكون \(a_i(t)=\alpha_i\) لكل \(t\ge \tau_i\). الآن إذا كان \(h\ge 2\tau_i+1\)، فلا يمكن أن يكون كل من \(j\) و\(h-j\) أصغر من \(\tau_i\) في الوقت نفسه لأن مجموعهما يساوي \(h\). لذلك فكل حركة لهذا التقسيم تقع في إحدى حالتين:
\[ x_{i,j}(h)=0 \quad \text{إذا كان } j,h-j \ge \tau_i, \]
أو
\[ x_{i,j}(h)=a_i(t)\oplus \alpha_i \quad \text{لقيمة حدية وحيدة } t \lt \tau_i. \]
إذن عندما يكبر \(h\) بما يكفي، فإن مجموعة nimberات الممكنة الناتجة عن التقسيم \(i\) لا تعود تعتمد على \(h\). وإذا أخذنا الحد الأقصى على جميع التقسيمات الرأسية نحصل على الحد الآمن
\[ B_w=\max_{1\le i \lt w}(2\tau_i+1). \]
ولكل \(h\ge B_w\) تصبح مجموعة الحركات الكاملة للحالة \(w \times h\) ثابتة، وبالتالي تصبح قيمة Grundy نفسها ثابتة على هذا الذيل. نرمز إلى هذه القيمة الثابتة بـ \(g_w^{(\infty)}\). وقد يكون أول ارتفاع مستقر فعلًا، أي \(T_w\)، أصغر من \(B_w\)، لكن \(B_w\) هو الموضع الذي يبدأ عنده البرهان المضمون.
بالنسبة إلى تقسيم ثابت \(i\) وارتفاع \(h\ge 2\tau_i+1\)، يمكن عدّ الحركات ذات xor الصفري بدقة.
الشريط الأوسط \(j=\tau_i,\tau_i+1,\dots,h-\tau_i\) طوله \(h-2\tau_i+1\)، وكل قطع داخله يحقق \(a_i(j)=a_i(h-j)=\alpha_i\)، ومن ثم يكون xor مساويًا للصفر.
أما القطوع الحدّية فتأتي في أزواج متناظرة من الشكل \(j=t\) و\(j=h-t\) حيث \(1\le t \lt \tau_i\). ويساهم هذا الزوج في xor صفري إذا وفقط إذا كان \(a_i(t)=\alpha_i\). فإذا عرّفنا
\[ z_i=\#\{t:1\le t \lt \tau_i,\ a_i(t)=\alpha_i\}, \]
فإن مساهمة هذا التقسيم تساوي
\[ c_{w,i}(h)=h-2\tau_i+1+2z_i. \]
وبجمع ذلك على جميع \(i=1,2,\dots,w-1\) نحصل على صيغة الذيل الخطية
\[ c_w(h)=(w-1)h+\beta_w, \]
حيث
\[ \beta_w=\sum_{i=1}^{w-1}(-2\tau_i+1+2z_i). \]
وهذه الهوية هي السبب الرئيسي في أن المسألة تصبح قابلة للحساب مع حد ارتفاع ضخم: ما إن نصل إلى \(B_w\)، حتى تتحول مساهمة العرض \(w\) المتبقية إلى مجموع متتابعة حسابية فقط.
الحالة الصغيرة \(w=5\) و\(h=3\) مفيدة لأنها تُظهر مباشرة أن العودية الحقيقية تقوم على أربعة مستطيلات فرعية. لا توجد هنا إلا قطعتان أفقيتان، هما \(j=1\) و\(j=2\)، وهما متناظرتان. ومن العروض الأصغر نعرف أن
\[ g_1(1)=g_1(2)=0,\qquad g_2(1)=0,\ g_2(2)=1,\qquad g_3(1)=0,\ g_3(2)=1,\qquad g_4(1)=0,\ g_4(2)=1. \]
بالنسبة إلى التقسيم \(i=1\) (وبالتناظر أيضًا \(i=4\)) نحصل على
\[ x_{1,1}(3)=g_1(1)\oplus g_4(1)\oplus g_1(2)\oplus g_4(2)=0\oplus 0\oplus 0\oplus 1=1. \]
أما بالنسبة إلى التقسيم \(i=2\) (وبالتناظر أيضًا \(i=3\)) فنحصل على
\[ x_{2,1}(3)=g_2(1)\oplus g_3(1)\oplus g_2(2)\oplus g_3(2)=0\oplus 0\oplus 1\oplus 1=0. \]
وبما أن \(j=1\) و\(j=2\) يعطيان xor نفسه، فإن القطوع الأربعة التي يكون فيها \(i=2\) أو \(i=3\) هي بالضبط الحركات ذات xor الصفري. وبالتالي
\[ c_5(3)=4. \]
أما nimberات الوصول فهي \(\{0,1\}\)، ومن ثم
\[ g_5(3)=\operatorname{mex}\{0,1\}=2. \]
وهذه إحدى الحالات الصغيرة التي يفحصها الحل قبل الانتقال إلى المجموع النهائي الكامل.
تُظهر تطبيقات C++ وPython وJava المسار الرياضي نفسه. التنفيذ الكامل للبرمجة الديناميكية يتم في C++، بينما تستدعي واجهتا Python وJava الحساب المترجم نفسه، لذلك فإن المخطط الآتي هو القلب الخوارزمي المشترك بينها جميعًا.
لكل عرض \(w\)، تخزن الشيفرة دائمًا ثلاث معلومات فقط: بادئة قصيرة من قيم Grundy المحسوبة صراحة، وأول ارتفاع \(T_w\) يصبح بعده الذيل ثابتًا، وقيمة الذيل \(g_w^{(\infty)}\). ولذلك فإن الاستعلام عن \(g_w(h)\) يُجاب عنه من البادئة إذا كان \(h \lt T_w\)، ومن قيمة الذيل مباشرة بخلاف ذلك.
ولهذا السبب يرتبط استهلاك الذاكرة بأطوال الاستقرار لا بالارتفاع الكلي \(H\).
عند حل العرض \(w\)، تحسب الشيفرة أولًا الحد الآمن \(B_w\). ثم تبني الجداول المساعدة \(a_i(t)=g_i(t)\oplus g_{w-i}(t)\) لكل \(1\le i \lt w\) ولكل ارتفاع حتى \(B_w\).
بعد ذلك، ولكل \(h\le B_w\)، تمر الشيفرة على جميع التقسيمات الرأسية \(i\) وعلى نصف مواضع القطع الأفقية \(j\) فقط، مستفيدة من التناظر \(j \leftrightarrow h-j\) في وسم nimberات الوصول وفي عدّ الحركات ذات xor الصفري معًا. وتوزَّع مجالات الارتفاع المختلفة على خيوط عمل منفصلة، بحيث تُملأ طبقة عرض كاملة بالتوازي من غير أن تتغير النتيجة الرياضية.
بعد اكتمال البادئة الصريحة، تبني الشيفرة مجموعة الحركات المستقرة من القيم الحدية \(t \lt \tau_i\)، وتستخرج منها \(g_w^{(\infty)}\)، وتحسب الثابت \(\beta_w\) في الصيغة الخطية \(c_w(h)=(w-1)h+\beta_w\). ثم تتحقق من هذه الصيغ الذيلية بمقارنتها مع آخر ارتفاع حُسب صراحة قبل الاعتماد عليها.
بعد ذلك يُعثر على نقطة الاستقرار الحقيقية \(T_w\) بالرجوع إلى الخلف داخل البادئة المحسوبة. وأخيرًا تُقسم مساهمة العرض \(w\) في الجواب إلى جزأين: البادئة الصريحة \(2\le h \lt B_w\)، ثم ذيل المتتابعة الحسابية
\[ \sum_{h=B_w}^{H} c_w(h) =(w-1)\sum_{h=B_w}^{H} h+\beta_w(H-B_w+1). \]
وقبل تنفيذ الحساب النهائي لـ \(D(123,1{,}234{,}567)\)، تفحص الشيفرة أيضًا معيارًا أصغر والقيمة النموذجية \(c_5(3)=4\).
لو عولج كل مستطيل حتى الارتفاع \(H\) مباشرة، لكان تقييم الحالة \(w \times h\) يتطلب فحص \((w-1)(h-1)\) قطعًا، وبالتالي كان حجم العمل الكلي سينمو على نحو \(O(W^2H^2)\). وهذا ضخم جدًا بالنسبة إلى الارتفاع المستهدف.
مع وجود الاستقرار، لا يُحسب العرض \(w\) صراحة إلا حتى \(B_w\). وتكلفة بناء هذه البادئة هي \(O(wB_w^2)\) زمنيًا، لأن الحل يمر على جميع الارتفاعات حتى \(B_w\)، ولكل ارتفاع يفحص جميع التقسيمات الرأسية ونحو نصف القطوع الأفقية. بعد ذلك يُضاف الذيل كله في زمن \(O(1)\) باستعمال صيغة المتتابعة الحسابية. أما الذاكرة الدائمة فهي \(O\!\left(\sum_{w=1}^{W} T_w\right)\) للبادئات المخزنة، إضافة إلى \(O(wB_w)\) من مساحة العمل المؤقتة أثناء حل العرض الحالي. الخيوط المتوازية تقلل زمن التنفيذ الفعلي، لكن التحسن الرياضي الحاسم هو استبدال الاعتماد على \(H\) الكامل بالاعتماد على حدود استقرار أصغر بكثير.