Let \(P(N)\) denote the number of winning opening moves in the \(N\times N\) Flipping Game. The implementations validate the method with
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
and the real target is \(P(10^6)\). The key observation is that a legal rectangle is determined by a triangular height and a square width, so the board can be analyzed through two coupled one-dimensional impartial games.
For a board of size \(N\), define the legal height and width families by
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$$
A move is therefore a pair consisting of one allowed vertical interval and one allowed horizontal interval. The solution first analyzes each axis separately and then combines them with nimber multiplication.
Fix one length family \(\mathcal L\), either \(\mathcal T_N\) or \(\mathcal S_N\). Let \(g_i\) be the Grundy number of the size-\(i\) component on that axis, and let
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$$
The recursive structure used by the implementations implies that a legal choice of length \(\ell\in\mathcal L\) with \(\ell\le i\) leads to a child position whose nimber is
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$$
Therefore
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$$
This recurrence is the core of the whole solution.
Without the prefix values \(x_i\), each child nimber would require xoring a whole interval of earlier Grundy values. The identity
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
compresses that interval into two array accesses and one xor. Since every legal pair \((i,\ell)\) is visited exactly once, the one-dimensional pass is efficient enough even when \(N=10^6\).
Once \(g_i\) is known, a move from the size-\(i\) component to a child nimber \(y_{i,\ell}\) changes that component by
$$m_{i,\ell}=g_i\oplus y_{i,\ell}.$$
This is the move nimber contributed by that axis. If we count how often each value appears, we obtain a histogram
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$$
The total nimber of the whole axis is simply
$$X_{\mathcal L}=x_N.$$
Let \(X_{\mathcal T}\) be the total nimber of the triangular-height axis and \(X_{\mathcal S}\) the total nimber of the square-width axis. The full board nimber is
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$$
where \(\otimes\) denotes nimber multiplication. Likewise, if a row move has nimber \(a\) and a column move has nimber \(b\), the corresponding rectangle move has nimber
$$a\otimes b.$$
Under normal play, an opening move is winning exactly when it moves to nimber \(0\), which here is equivalent to
$$a\otimes b=\Gamma.$$
If \(\Gamma=0\), nimber multiplication has no zero divisors, so
$$a\otimes b=0 \iff a=0 \text{ or } b=0.$$
Hence the number of winning openings is
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$$
If \(\Gamma\neq 0\), every nonzero \(a\) determines a unique partner
$$b=a^{-1}\otimes \Gamma,$$
so the answer becomes
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$$
The implementations compute inverses inside a sufficiently large finite nimber field, using \(a^{-1}=a^{q-2}\) for a field size \(q\) larger than every nimber that occurs.
For \(N=5\), the legal lengths are
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$$
On the triangular side, the recurrence gives
$$g_1=g_2=g_3=g_4=g_5=1,$$
so the total axis nimber is \(X_{\mathcal T}=1\). There are \(5+3=8\) legal row intervals, and each one has move nimber \(1\), hence
$$c_{\mathcal T}(1)=8.$$
On the square side, the recurrence yields
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$$
so
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
The column histogram is
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$$
Therefore the board nimber is
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$$
Because the only row move nimber is \(a=1\), the winning condition forces
$$b=1^{-1}\otimes 2=2.$$
There are \(8\) such row moves and exactly \(1\) matching column move, so
$$P(5)=8\cdot 1=8,$$
which matches the checkpoint used by the implementations.
The C++, Python, and Java implementations generate all triangular heights and square widths up to \(N\). For each family they sweep from \(1\) to \(N\), maintain the prefix-xor table \(x_i\), evaluate every reachable child nimber \(y_{i,\ell}\), take the mex to obtain the next Grundy number, and update a histogram of move nimbers \(m_{i,\ell}\).
To keep the mex step fast, the implementation uses temporary frequency storage for the child nimbers that occur at the current size \(i\), then clears only the touched entries. It also starts with a moderate nimber-table size and doubles that size if a larger nimber appears, recomputing only when necessary.
After both axis histograms are known, the implementation computes the total board nimber \(\Gamma\) with memoized recursive nimber multiplication based on Fermat 2-power decomposition. It then applies the counting formulas above: inclusion-exclusion when \(\Gamma=0\), and multiplicative inversion when \(\Gamma\neq 0\). The Python implementation uses the same underlying computation, so the mathematical method is identical across languages.
Let \(t=|\mathcal T_N|\) and \(s=|\mathcal S_N|\). Since \(t=\Theta(\sqrt N)\) and \(s=\Theta(\sqrt N)\), the two one-dimensional passes cost
$$O(Nt)+O(Ns)=O(N^{3/2}).$$
The final histogram pairing is linear in the nimber-table size actually needed, which is small compared with the \(O(N^{3/2})\) sweep. Memory usage is \(O(N)\) for the prefix data plus the move histograms and temporary frequency tables, so the overall space complexity is linear in \(N\).
Sei \(P(N)\) die Anzahl gewinnender erster Züge im \(N\times N\)-Flipping-Game. Die Implementierungen prüfen die Methode mit
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
und das eigentliche Ziel ist \(P(10^6)\). Entscheidend ist, dass ein legaler Zug durch eine dreieckige Höhe und eine quadratische Breite bestimmt wird. Dadurch lässt sich das Brett über zwei gekoppelte eindimensionale imparziale Spiele analysieren.
Für ein Brett der Größe \(N\) definieren wir die erlaubten Höhen- und Breitenmengen durch
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$$
Ein Zug ist also ein Paar aus einem erlaubten vertikalen Intervall und einem erlaubten horizontalen Intervall. Die Lösung analysiert zunächst jede Achse separat und verbindet beide danach mit Nimber-Multiplikation.
Fixiere eine Längenfamilie \(\mathcal L\), also entweder \(\mathcal T_N\) oder \(\mathcal S_N\). Sei \(g_i\) die Grundy-Zahl der Komponente der Größe \(i\) auf dieser Achse, und setze
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$$
Die von den Implementierungen benutzte rekursive Struktur besagt: Eine legale Wahl der Länge \(\ell\in\mathcal L\) mit \(\ell\le i\) führt zu einer Kindposition mit Nimber
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$$
Daher gilt
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$$
Diese Rekurrenz ist der Kern der gesamten Methode.
Ohne die Präfixwerte \(x_i\) müsste man für jeden Kindnimber ein ganzes Intervall früherer Grundy-Werte xoren. Die Identität
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
komprimiert dieses Intervall auf zwei Arrayzugriffe und ein XOR. Da jedes legale Paar \((i,\ell)\) genau einmal besucht wird, bleibt der eindimensionale Durchlauf selbst für \(N=10^6\) schnell genug.
Sobald \(g_i\) bekannt ist, ändert ein Zug von der Größe-\(i\)-Komponente zu einem Kindnimber \(y_{i,\ell}\) diese Komponente um
$$m_{i,\ell}=g_i\oplus y_{i,\ell}.$$
Das ist der von dieser Achse gelieferte Zugnimber. Zählt man alle Vorkommen eines Wertes, erhält man das Histogramm
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$$
Der Gesamtnimber der ganzen Achse ist einfach
$$X_{\mathcal L}=x_N.$$
Sei \(X_{\mathcal T}\) der Gesamtnimber der Dreieckshöhen-Achse und \(X_{\mathcal S}\) der Gesamtnimber der Quadratbreiten-Achse. Der Nimber des gesamten Bretts ist
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$$
wobei \(\otimes\) die Nimber-Multiplikation bezeichnet. Hat ein Zeilenzug den Nimber \(a\) und ein Spaltenzug den Nimber \(b\), so besitzt das entsprechende Rechteck den Zugnimber
$$a\otimes b.$$
Unter Normalspiel ist ein Eröffnungszug genau dann gewinnend, wenn er zu Nimber \(0\) führt, also äquivalent zu
$$a\otimes b=\Gamma.$$
Falls \(\Gamma=0\), hat die Nimber-Multiplikation keine Nullteiler, also
$$a\otimes b=0 \iff a=0 \text{ oder } b=0.$$
Damit ist die Anzahl gewinnender Eröffnungen
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$$
Falls \(\Gamma\neq 0\), bestimmt jedes nichtverschwindende \(a\) genau einen Partner
$$b=a^{-1}\otimes \Gamma,$$
und damit
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$$
Die Implementierungen berechnen Inversen in einem hinreichend großen endlichen Nimber-Körper und verwenden dazu \(a^{-1}=a^{q-2}\) für eine Körpergröße \(q\), die größer ist als jeder auftretende Nimber.
Für \(N=5\) sind die erlaubten Längen
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$$
Auf der Dreiecksseite liefert die Rekurrenz
$$g_1=g_2=g_3=g_4=g_5=1,$$
also ist der Gesamtnimber der Achse \(X_{\mathcal T}=1\). Es gibt \(5+3=8\) legale Zeilenintervalle, und jedes hat den Zugnimber \(1\). Daher
$$c_{\mathcal T}(1)=8.$$
Auf der Quadratseite ergibt die Rekurrenz
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$$
somit
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
Das Spaltenhistogramm lautet
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$$
Folglich ist der Brettnimber
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$$
Da auf der Zeilenseite nur \(a=1\) vorkommt, erzwingt die Gewinnbedingung
$$b=1^{-1}\otimes 2=2.$$
Es gibt \(8\) solche Zeilenzüge und genau \(1\) passende Spaltenwahl. Also
$$P(5)=8\cdot 1=8,$$
genau wie im Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen erzeugen zunächst alle Dreieckshöhen und Quadratbreiten bis \(N\). Für jede Familie durchlaufen sie die Größen von \(1\) bis \(N\), pflegen die Präfix-XOR-Tabelle \(x_i\), berechnen alle erreichbaren Kindnimber \(y_{i,\ell}\), bestimmen per mex die nächste Grundy-Zahl und aktualisieren ein Histogramm der Zugnimber \(m_{i,\ell}\).
Damit die mex-Suche schnell bleibt, verwendet die Implementierung für die bei der aktuellen Größe \(i\) auftretenden Kindnimber einen temporären Frequenzspeicher und leert anschließend nur die tatsächlich berührten Einträge. Außerdem startet sie mit einer moderaten Nimber-Tabellengröße und verdoppelt diese, falls ein größerer Nimber auftaucht, sodass nur bei Bedarf neu gerechnet wird.
Sobald beide Achsenhistogramme vorliegen, berechnet die Implementierung den Gesamtnimber \(\Gamma\) per memoisiertem rekursivem Nimber-Produkt auf Basis der Fermat-2-Potenz-Zerlegung. Danach werden die obigen Zählformeln angewandt: Inklusion-Exklusion für \(\Gamma=0\) und multiplikative Inversion für \(\Gamma\neq 0\). Die Python-Implementierung verwendet dieselbe zugrunde liegende Berechnung, daher ist die Mathematik in allen drei Sprachen identisch.
Seien \(t=|\mathcal T_N|\) und \(s=|\mathcal S_N|\). Da \(t=\Theta(\sqrt N)\) und \(s=\Theta(\sqrt N)\) gilt, kosten die beiden eindimensionalen Durchläufe
$$O(Nt)+O(Ns)=O(N^{3/2}).$$
Das abschließende Paaren der Histogramme ist linear in der tatsächlich benötigten Nimber-Tabellengröße und damit kleiner als der \(O(N^{3/2})\)-Hauptdurchlauf. Der Speicherbedarf beträgt \(O(N)\) für Präfixdaten sowie Zughistogramme und temporäre Frequenzfelder; insgesamt ist die Methode also linear im Speicher.
\(P(N)\), \(N\times N\) boyutlu Flipping Game'de kazandıran ilk hamlelerin sayısı olsun. Uygulamalar yöntemi şu kontrol değerleriyle doğrular:
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
ve asıl hedef \(P(10^6)\)'dır. Kritik gözlem şudur: Geçerli bir dikdörtgen, üçgensel bir yükseklik ve karesel bir genişlik ile belirlenir. Bu yüzden tahta, birbirine bağlı iki tek boyutlu tarafsız oyuna ayrılarak incelenebilir.
\(N\) boyutlu tahta için izin verilen yükseklik ve genişlik ailelerini
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}$$
olarak tanımlayalım. Böylece bir hamle, izin verilen bir dikey aralık ile izin verilen bir yatay aralığın eşleşmesidir. Çözüm önce her ekseni ayrı çözer, sonra ikisini nimber çarpımıyla birleştirir.
\(\mathcal L\) adlı tek bir uzunluk ailesi seçelim; bu ya \(\mathcal T_N\) ya da \(\mathcal S_N\) olacaktır. Bu eksendeki boyutu \(i\) olan bileşenin Grundy değeri \(g_i\) olsun ve
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i$$
tanımını yapalım. Uygulamaların kullandığı özyinelemeli yapı şunu verir: \(\ell\in\mathcal L\) ve \(\ell\le i\) olacak şekilde seçilen her yasal uzunluk, nimberi
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
olan bir çocuk konuma gider. Dolayısıyla
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}$$
olur. Bütün yöntemin omurgası bu bağıntıdır.
Prefix değerleri \(x_i\) olmasaydı, her çocuk nimber için daha önceki Grundy değerlerinin bir aralığını tek tek xor'lamak gerekirdi. Şu özdeşlik
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
bu aralığı iki dizi erişimi ve bir xor işlemine indirger. Her yasal \((i,\ell)\) çifti tam bir kez işlendiği için, \(N=10^6\) olduğunda bile tek boyutlu geçiş yeterince hızlı kalır.
\(g_i\) belirlendikten sonra, boyutu \(i\) olan bileşenden nimberi \(y_{i,\ell}\) olan bir çocuk konuma giden hamle bu bileşeni
$$m_{i,\ell}=g_i\oplus y_{i,\ell}$$
miktarı kadar değiştirir. Bu, o eksenin katkı verdiği hamle nimber'ıdır. Her değerin kaç kez oluştuğunu sayarsak
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}$$
histogramını elde ederiz. Eksenin toplam nimber'ı ise
$$X_{\mathcal L}=x_N$$
olur.
\(X_{\mathcal T}\) üçgensel yükseklik ekseninin, \(X_{\mathcal S}\) ise karesel genişlik ekseninin toplam nimber'ı olsun. Tahtanın tam nimber'ı
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}$$
şeklindedir; burada \(\otimes\) nimber çarpımını gösterir. Eğer bir satır hamlesinin nimber'ı \(a\), bir sütun hamlesinin nimber'ı \(b\) ise, karşılık gelen dikdörtgen hamlenin nimber'ı
$$a\otimes b$$
olur. Normal oyunda bir açılış hamlesi, ancak ve ancak nimberi \(0\)'a götürüyorsa kazandırır; burada bu koşul
$$a\otimes b=\Gamma$$
ile eşdeğerdir.
Eğer \(\Gamma=0\) ise, nimber çarpımında sıfır böleni yoktur; dolayısıyla
$$a\otimes b=0 \iff a=0 \text{ veya } b=0.$$
Bu durumda kazandıran açılış sayısı
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0)$$
olur. Eğer \(\Gamma\neq 0\) ise, sıfır olmayan her \(a\) için tek bir eş
$$b=a^{-1}\otimes \Gamma$$
vardır ve sonuç
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right)$$
şeklini alır. Uygulamalar tersleri, ortaya çıkan tüm nimber'lardan daha büyük bir sonlu nimber alanında \(a^{-1}=a^{q-2}\) bağıntısıyla hesaplar.
\(N=5\) için yasal uzunluklar
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}$$
olur. Üçgensel tarafta bağıntı
$$g_1=g_2=g_3=g_4=g_5=1$$
sonucunu verir; yani toplam eksen nimber'ı \(X_{\mathcal T}=1\)'dir. \(5+3=8\) adet yasal satır aralığı vardır ve bunların her birinin hamle nimber'ı \(1\)'dir. Dolayısıyla
$$c_{\mathcal T}(1)=8.$$
Karesel tarafta ise bağıntı
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1$$
verir; bu yüzden
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
Sütun histogramı
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2$$
şeklindedir. Böylece tahta nimber'ı
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2$$
olur. Satır tarafında yalnızca \(a=1\) görüldüğünden, kazanç koşulu
$$b=1^{-1}\otimes 2=2$$
olmasını zorlar. Bu tipten \(8\) satır hamlesi ve tam \(1\) uygun sütun hamlesi vardır. Sonuç olarak
$$P(5)=8\cdot 1=8,$$
ki bu da uygulamaların kullandığı kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce \(N\)'ye kadar olan tüm üçgensel yükseklikleri ve karesel genişlikleri üretir. Her aile için \(1\)'den \(N\)'ye kadar ilerler, prefix-xor tablosu \(x_i\)'yi günceller, ulaşılabilen çocuk nimber'ları \(y_{i,\ell}\) hesaplar, mex ile sonraki Grundy değerini bulur ve hamle nimber'ları \(m_{i,\ell}\) için bir histogram oluşturur.
Mex adımını hızlı tutmak için, uygulama o anda incelenen \(i\) boyutunda ortaya çıkan çocuk nimber'lar için geçici bir frekans yapısı kullanır ve sonra yalnızca gerçekten dokunulan girişleri temizler. Ayrıca nimber tablosu için orta büyüklükte bir başlangıç seçer; daha büyük bir değer görülürse tablo boyutunu iki katına çıkarıp yalnızca gerektiğinde yeniden hesaplar.
İki eksenin histogramı hazır olduktan sonra, uygulama Fermat tipi \(2\)-kuvvet ayrışımına dayalı, önbellekli özyinelemeli nimber çarpımıyla toplam tahta nimber'ı \(\Gamma\)'yı hesaplar. Ardından yukarıdaki sayım formüllerini uygular: \(\Gamma=0\) için dahil et-çıkar, \(\Gamma\neq 0\) içinse çarpımsal ters kullanılır. Python uygulaması aynı temel hesabı kullandığından, üç dilde de matematik aynıdır.
\(t=|\mathcal T_N|\) ve \(s=|\mathcal S_N|\) olsun. \(t=\Theta(\sqrt N)\) ve \(s=\Theta(\sqrt N)\) olduğundan, iki tek boyutlu geçişin maliyeti
$$O(Nt)+O(Ns)=O(N^{3/2})$$
olur. Son histogram eşleştirmesi, gerçekten ihtiyaç duyulan nimber tablosu boyutunda doğrusaldır ve \(O(N^{3/2})\) ana geçişe göre daha küçüktür. Bellek kullanımı prefix verileri, hamle histogramları ve geçici frekans yapıları için \(O(N)\) düzeyindedir; dolayısıyla toplam alan karmaşıklığı lineerdir.
Sea \(P(N)\) el número de movimientos iniciales ganadores en el Flipping Game sobre un tablero \(N\times N\). Las implementaciones validan el método con
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
y el objetivo real es \(P(10^6)\). La observación decisiva es que un rectángulo legal queda determinado por una altura triangular y una anchura cuadrada, así que el tablero puede analizarse mediante dos juegos imparciales unidimensionales acoplados.
Para un tablero de tamaño \(N\), definimos las familias legales de alturas y anchuras por
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$$
Por tanto, un movimiento es un par formado por un intervalo vertical permitido y un intervalo horizontal permitido. La solución estudia primero cada eje por separado y después los combina mediante multiplicación de nimbers.
Fijemos una familia de longitudes \(\mathcal L\), ya sea \(\mathcal T_N\) o \(\mathcal S_N\). Sea \(g_i\) el número de Grundy del componente de tamaño \(i\) en ese eje, y definamos
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$$
La estructura recursiva utilizada por las implementaciones implica que una elección legal de longitud \(\ell\in\mathcal L\) con \(\ell\le i\) lleva a una posición hija cuyo nimber es
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$$
En consecuencia,
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$$
Esta recurrencia es el núcleo de todo el procedimiento.
Sin los valores prefijo \(x_i\), cada nimber hijo exigiría hacer xor sobre un intervalo completo de valores de Grundy anteriores. La identidad
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
condensa ese intervalo en dos accesos a arreglo y un xor. Como cada par legal \((i,\ell)\) se procesa exactamente una vez, el barrido unidimensional sigue siendo suficientemente rápido incluso para \(N=10^6\).
Una vez conocido \(g_i\), un movimiento desde el componente de tamaño \(i\) hacia un hijo de nimber \(y_{i,\ell}\) modifica ese componente en
$$m_{i,\ell}=g_i\oplus y_{i,\ell}.$$
Ese es el nimber de movimiento aportado por ese eje. Si contamos cuántas veces aparece cada valor, obtenemos el histograma
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$$
El nimber total del eje completo es simplemente
$$X_{\mathcal L}=x_N.$$
Sea \(X_{\mathcal T}\) el nimber total del eje de alturas triangulares y \(X_{\mathcal S}\) el del eje de anchuras cuadradas. El nimber del tablero completo es
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$$
donde \(\otimes\) denota la multiplicación de nimbers. Del mismo modo, si un movimiento de filas tiene nimber \(a\) y uno de columnas tiene nimber \(b\), el rectángulo correspondiente tiene nimber
$$a\otimes b.$$
Bajo juego normal, un primer movimiento es ganador exactamente cuando deja nimber \(0\), lo cual aquí equivale a
$$a\otimes b=\Gamma.$$
Si \(\Gamma=0\), la multiplicación de nimbers no tiene divisores de cero, por lo que
$$a\otimes b=0 \iff a=0 \text{ o } b=0.$$
Así, el número de aperturas ganadoras es
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$$
Si \(\Gamma\neq 0\), cada \(a\neq 0\) determina un único compañero
$$b=a^{-1}\otimes \Gamma,$$
y por tanto
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$$
Las implementaciones calculan las inversas dentro de un cuerpo finito de nimbers suficientemente grande, usando \(a^{-1}=a^{q-2}\) para un tamaño de cuerpo \(q\) mayor que cualquier nimber que aparezca.
Para \(N=5\), las longitudes legales son
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$$
En el lado triangular, la recurrencia da
$$g_1=g_2=g_3=g_4=g_5=1,$$
de modo que el nimber total del eje es \(X_{\mathcal T}=1\). Hay \(5+3=8\) intervalos legales de fila, y todos tienen nimber de movimiento \(1\). Luego
$$c_{\mathcal T}(1)=8.$$
En el lado cuadrado, la recurrencia produce
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$$
por lo que
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
El histograma de columnas es
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$$
Por tanto, el nimber del tablero es
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$$
Como el único nimber de movimiento de filas es \(a=1\), la condición ganadora obliga a
$$b=1^{-1}\otimes 2=2.$$
Hay \(8\) movimientos de fila de ese tipo y exactamente \(1\) movimiento de columna compatible. Entonces
$$P(5)=8\cdot 1=8,$$
en perfecto acuerdo con el punto de comprobación de las implementaciones.
Las implementaciones en C++, Python y Java generan primero todas las alturas triangulares y anchuras cuadradas hasta \(N\). Para cada familia recorren los tamaños desde \(1\) hasta \(N\), mantienen la tabla de XOR prefijo \(x_i\), evalúan todos los nimbers hijos alcanzables \(y_{i,\ell}\), toman el mex para obtener el siguiente valor de Grundy y actualizan un histograma de nimbers de movimiento \(m_{i,\ell}\).
Para que el paso del mex sea rápido, la implementación usa almacenamiento temporal de frecuencias para los nimbers hijos que aparecen en el tamaño actual \(i\), y después limpia solo las entradas realmente tocadas. También comienza con un tamaño moderado para la tabla de nimbers y lo duplica si aparece un nimber mayor, recomputando únicamente cuando hace falta.
Una vez conocidos ambos histogramas, la implementación calcula el nimber total del tablero \(\Gamma\) mediante multiplicación recursiva memoizada de nimbers basada en la descomposición de potencias de \(2\) de tipo Fermat. Después aplica las fórmulas anteriores: inclusión-exclusión cuando \(\Gamma=0\) e inversión multiplicativa cuando \(\Gamma\neq 0\). La implementación en Python usa el mismo cálculo subyacente, así que la matemática es la misma en los tres lenguajes.
Sean \(t=|\mathcal T_N|\) y \(s=|\mathcal S_N|\). Como \(t=\Theta(\sqrt N)\) y \(s=\Theta(\sqrt N)\), los dos barridos unidimensionales cuestan
$$O(Nt)+O(Ns)=O(N^{3/2}).$$
El emparejamiento final de histogramas es lineal en el tamaño de la tabla de nimbers realmente necesaria, por lo que es menor que el barrido dominante \(O(N^{3/2})\). El uso de memoria es \(O(N)\) para los datos prefijo, los histogramas de movimientos y las tablas temporales de frecuencias; en conjunto, la complejidad espacial es lineal.
记 \(P(N)\) 为 \(N\times N\) 的 Flipping Game 中先手必胜首步的个数。实现先用下面几个检验值验证方法：
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
真正要求的是 \(P(10^6)\)。关键观察在于，一个合法矩形完全由“三角数高度”和“平方数宽度”决定，因此整块棋盘可以拆成两个相互耦合的一维公平博弈，再用 Sprague-Grundy 理论重新组合。
对大小为 \(N\) 的棋盘，定义允许的高度集合与宽度集合为
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$$
于是一次合法操作就是“选一个允许的纵向区间”与“选一个允许的横向区间”组成的有序对。解法先分别处理两个方向的一维结构，再用 nimber 乘法把它们合并。
固定一个长度族 \(\mathcal L\)，它可以是 \(\mathcal T_N\) 或 \(\mathcal S_N\)。记该方向上大小为 \(i\) 的一维分量的 Grundy 数为 \(g_i\)，并定义前缀 xor
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$$
实现中使用的递归结构表明：如果选择一个合法长度 \(\ell\in\mathcal L\) 且 \(\ell\le i\)，那么得到的子局面 nimber 为
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$$
因此
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$$
这条递推就是整个算法的核心。
如果没有前缀值 \(x_i\)，那么每次都要对一整段历史 Grundy 数做 xor。恒等式
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
把这件事压缩成两次数组访问和一次 xor。由于每个合法二元组 \((i,\ell)\) 只会被处理一次，所以即使 \(N=10^6\)，整个一维扫描仍然可行。
当 \(g_i\) 已知时，从大小为 \(i\) 的分量走到子局面 \(y_{i,\ell}\) 的那一步，会让该分量发生的 nimber 变化量为
$$m_{i,\ell}=g_i\oplus y_{i,\ell}.$$
这就是这一维贡献出来的“操作 nimber”。把所有同值操作累计起来，就得到直方图
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$$
整条轴的总 nimber 则直接等于
$$X_{\mathcal L}=x_N.$$
记三角高度方向的总 nimber 为 \(X_{\mathcal T}\)，平方宽度方向的总 nimber 为 \(X_{\mathcal S}\)。整个棋盘的 nimber 是
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$$
其中 \(\otimes\) 表示 nimber 乘法。类似地，如果某个纵向操作的 nimber 是 \(a\)，某个横向操作的 nimber 是 \(b\)，那么对应矩形操作的 nimber 就是
$$a\otimes b.$$
在正常博弈规则下，首步必胜当且仅当走完之后局面 nimber 变成 \(0\)。在这里这等价于
$$a\otimes b=\Gamma.$$
如果 \(\Gamma=0\)，由于 nimber 乘法没有零因子，所以
$$a\otimes b=0 \iff a=0 \text{ 或 } b=0.$$
因此必胜首步总数为
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$$
如果 \(\Gamma\neq 0\)，那么每个非零 \(a\) 都唯一对应一个
$$b=a^{-1}\otimes \Gamma,$$
于是答案变成
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$$
实现会在一个足够大的有限 nimber 域中计算逆元；若域大小为 \(q\)，则对任意非零元素使用
$$a^{-1}=a^{q-2}.$$
当 \(N=5\) 时，合法长度为
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$$
在三角高度这一侧，递推给出
$$g_1=g_2=g_3=g_4=g_5=1,$$
所以该轴总 nimber 为 \(X_{\mathcal T}=1\)。合法纵向区间共有 \(5+3=8\) 个，而且每一个的操作 nimber 都是 \(1\)，因此
$$c_{\mathcal T}(1)=8.$$
在平方宽度这一侧，递推得到
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$$
于是
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
横向操作的直方图为
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$$
因此整块棋盘的 nimber 是
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$$
由于纵向只出现 \(a=1\) 这一种操作 nimber，必胜条件强制
$$b=1^{-1}\otimes 2=2.$$
这样的纵向操作有 \(8\) 个，而匹配的横向操作恰好只有 \(1\) 个，所以
$$P(5)=8\cdot 1=8,$$
与实现中的校验值完全一致。
C++、Python 和 Java 实现都会先生成不超过 \(N\) 的所有三角数高度与平方数宽度。对每个长度族，它们从 \(1\) 扫到 \(N\)，维护前缀 xor 表 \(x_i\)，求出所有可达子局面的 nimber \(y_{i,\ell}\)，对这些值取 mex 得到新的 Grundy 数，再把对应的操作 nimber \(m_{i,\ell}\) 累计到直方图中。
为了让 mex 计算足够快，实现会为当前大小 \(i\) 上实际出现过的子局面 nimber 建立临时频率记录，随后只清理那些确实被访问过的条目。实现还会先采用一个适中的 nimber 表规模；如果运行中发现更大的 nimber，就把表规模翻倍并重新执行，这样无需事先猜测上界。
在两个方向的直方图都构造完之后，实现用带记忆化的递归 nimber 乘法计算总棋盘 nimber \(\Gamma\)。该乘法基于 Fermat 型 \(2\) 次幂分解。随后直接套用上面的计数公式：\(\Gamma=0\) 时用容斥，\(\Gamma\neq 0\) 时用乘法逆元。Python 实现调用的是同一套底层计算逻辑，因此三种语言对应的是完全相同的数学方案。
设 \(t=|\mathcal T_N|\)、\(s=|\mathcal S_N|\)。因为 \(t=\Theta(\sqrt N)\)、\(s=\Theta(\sqrt N)\)，所以两个一维扫描的总时间为
$$O(Nt)+O(Ns)=O(N^{3/2}).$$
最后的直方图配对只与实际需要的 nimber 表大小成线性关系，相比 \(O(N^{3/2})\) 的主扫描更轻。空间方面，前缀数据、操作直方图和临时频率表一共是 \(O(N)\) 级别，因此总体空间复杂度是线性的。
Обозначим через \(P(N)\) число выигрышных первых ходов в игре Flipping Game на доске \(N\times N\). Реализации проверяют метод на значениях
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
а настоящая цель состоит в вычислении \(P(10^6)\). Главная идея в том, что допустимый прямоугольник задаётся треугольной высотой и квадратной шириной, поэтому всю позицию можно разложить на две связанные одномерные беспристрастные игры.
Для доски размера \(N\) определим множества допустимых высот и ширин:
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$$
Тем самым ход представляет собой пару: разрешённый вертикальный интервал и разрешённый горизонтальный интервал. Решение сначала изучает каждую ось отдельно, а затем объединяет их с помощью умножения нимберов.
Зафиксируем семейство длин \(\mathcal L\), то есть либо \(\mathcal T_N\), либо \(\mathcal S_N\). Пусть \(g_i\) обозначает число Гранди компоненты размера \(i\) на данной оси, и положим
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$$
Рекурсивная структура, использованная в реализациях, даёт следующее: выбор допустимой длины \(\ell\in\mathcal L\) при \(\ell\le i\) приводит к дочерней позиции с нимбером
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$$
Следовательно,
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$$
Именно эта рекурсия является основой всего решения.
Без префиксных значений \(x_i\) пришлось бы для каждого дочернего нимбера брать xor по целому интервалу предыдущих чисел Гранди. Формула
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
сжимает эту операцию до двух обращений к массиву и одного xor. Поскольку каждая допустимая пара \((i,\ell)\) рассматривается ровно один раз, одномерный проход остаётся достаточно быстрым даже при \(N=10^6\).
Когда \(g_i\) уже найдено, ход из компоненты размера \(i\) в дочернюю позицию с нимбером \(y_{i,\ell}\) изменяет эту компоненту на величину
$$m_{i,\ell}=g_i\oplus y_{i,\ell}.$$
Это и есть нимбер хода, который даёт данная ось. Подсчитав число появлений каждого значения, получаем гистограмму
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$$
Полный нимбер всей оси равен просто
$$X_{\mathcal L}=x_N.$$
Пусть \(X_{\mathcal T}\) обозначает полный нимбер оси треугольных высот, а \(X_{\mathcal S}\) — оси квадратных ширин. Тогда нимбер всей доски равен
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$$
где \(\otimes\) означает умножение нимберов. Аналогично, если нимбер вертикального хода равен \(a\), а горизонтального — \(b\), то соответствующий прямоугольный ход имеет нимбер
$$a\otimes b.$$
При обычном правиле игры первый ход выигрышен тогда и только тогда, когда после него получается нимбер \(0\), а здесь это эквивалентно условию
$$a\otimes b=\Gamma.$$
Если \(\Gamma=0\), то у умножения нимберов нет делителей нуля, поэтому
$$a\otimes b=0 \iff a=0 \text{ или } b=0.$$
Отсюда число выигрышных первых ходов равно
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$$
Если \(\Gamma\neq 0\), то каждому ненулевому \(a\) соответствует единственный партнёр
$$b=a^{-1}\otimes \Gamma,$$
и потому
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$$
Обратные элементы реализации вычисляют в достаточно большом конечном поле нимберов, используя формулу \(a^{-1}=a^{q-2}\) для размера поля \(q\), превосходящего все встретившиеся нимберы.
При \(N=5\) допустимые длины таковы:
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$$
На стороне треугольных высот рекурсия даёт
$$g_1=g_2=g_3=g_4=g_5=1,$$
поэтому полный нимбер этой оси равен \(X_{\mathcal T}=1\). Имеется \(5+3=8\) допустимых вертикальных интервалов, и каждый из них имеет нимбер хода \(1\). Следовательно,
$$c_{\mathcal T}(1)=8.$$
На стороне квадратных ширин получаем
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$$
и значит
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
Гистограмма горизонтальных ходов имеет вид
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$$
Итак, нимбер всей доски равен
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$$
Поскольку на вертикальной стороне встречается только \(a=1\), условие выигрыша требует
$$b=1^{-1}\otimes 2=2.$$
Таких вертикальных ходов \(8\), а подходящий горизонтальный ход ровно один. Значит,
$$P(5)=8\cdot 1=8,$$
что точно совпадает с контрольным значением из реализаций.
Реализации на C++, Python и Java сначала строят все треугольные высоты и квадратные ширины, не превосходящие \(N\). Для каждого семейства они проходят размеры от \(1\) до \(N\), поддерживают таблицу префиксных xor \(x_i\), вычисляют все достижимые дочерние нимберы \(y_{i,\ell}\), берут mex для получения следующего числа Гранди и обновляют гистограмму нимберов ходов \(m_{i,\ell}\).
Чтобы шаг с mex работал быстро, реализация использует временное хранение частот только для тех дочерних нимберов, которые появились на текущем размере \(i\), а затем очищает лишь реально затронутые записи. Кроме того, она стартует с умеренного размера таблицы нимберов и удваивает его, если в ходе вычисления встречается большее значение, пересчитывая только тогда, когда это действительно нужно.
Когда обе гистограммы построены, реализация находит полный нимбер доски \(\Gamma\) с помощью мемоизированного рекурсивного умножения нимберов, основанного на разложении по ферматовым степеням двойки. После этого применяются приведённые выше формулы подсчёта: включение-исключение при \(\Gamma=0\) и мультипликативная инверсия при \(\Gamma\neq 0\). Python-реализация использует ту же базовую вычислительную схему, поэтому математика одинакова во всех трёх языках.
Пусть \(t=|\mathcal T_N|\) и \(s=|\mathcal S_N|\). Так как \(t=\Theta(\sqrt N)\) и \(s=\Theta(\sqrt N)\), два одномерных прохода стоят
$$O(Nt)+O(Ns)=O(N^{3/2}).$$
Финальное сопоставление гистограмм линейно по реально нужному размеру таблицы нимберов и потому меньше доминирующего прохода \(O(N^{3/2})\). Память составляет \(O(N)\) на префиксные данные, гистограммы ходов и временные таблицы частот, так что итоговая пространственная сложность линейна.
لتكن \(P(N)\) هي عدد النقلات الافتتاحية الرابحة في لعبة Flipping Game على لوح حجمه \(N\times N\). تقوم التطبيقات بالتحقق من المنهج عبر القيم
$$P(1)=1,\qquad P(2)=0,\qquad P(5)=8,\qquad P(100)=31395,$$
والهدف الفعلي هو حساب \(P(10^6)\). الملاحظة الحاسمة هي أن أي مستطيل قانوني يتحدد بارتفاع مثلثي وعرض مربعي، ولذلك يمكن تحليل اللوح عبر لعبتين أحاديتَي البعد مترابطتين من نوع الألعاب غير المتحيزة.
من أجل لوح حجمه \(N\)، نعرّف عائلتَي الأطوال المسموح بها كما يلي:
$$\mathcal T_N=\left\{\frac{k(k+1)}{2}:k\ge 1,\ \frac{k(k+1)}{2}\le N\right\},\qquad \mathcal S_N=\left\{k^2:k\ge 1,\ k^2\le N\right\}.$$
وبذلك تكون كل نقلة زوجًا مكوّنًا من مقطع رأسي مسموح ومقطع أفقي مسموح. يبدأ الحل بتحليل كل محور على حدة، ثم يدمجهما باستخدام ضرب النيمبر.
ثبّت عائلة أطوال \(\mathcal L\)، وهي إما \(\mathcal T_N\) أو \(\mathcal S_N\). ولتكن \(g_i\) قيمة Grundy للمكوّن ذي الحجم \(i\) على ذلك المحور، ولنعرف
$$x_0=0,\qquad x_i=g_1\oplus g_2\oplus\cdots\oplus g_i.$$
البنية العودية المستعملة في التطبيقات تعطي أن اختيار طول قانوني \(\ell\in\mathcal L\) مع \(\ell\le i\) يقود إلى وضع ابن له النيمبر
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}.$$
ومن ثم
$$g_i=\operatorname{mex}\left\{y_{i,\ell}:\ell\in\mathcal L,\ \ell\le i\right\}.$$
هذه العلاقة هي قلب الحل كله.
من دون القيم التراكمية \(x_i\)، سنحتاج في كل مرة إلى أخذ xor على فترة كاملة من قيم Grundy السابقة. الهوية
$$y_{i,\ell}=x_{i-1}\oplus x_{i-\ell}$$
تضغط تلك العملية إلى وصولين إلى المصفوفة وعملية xor واحدة. وبما أن كل زوج قانوني \((i,\ell)\) يُعالج مرة واحدة فقط، فإن المرور الأحادي البعد يبقى عمليًا حتى عندما يكون \(N=10^6\).
بعد معرفة \(g_i\)، فإن النقلة من المكوّن ذي الحجم \(i\) إلى ابن نيمبره \(y_{i,\ell}\) تغيّر ذلك المكوّن بمقدار
$$m_{i,\ell}=g_i\oplus y_{i,\ell}.$$
وهذا هو نيمبر النقلة الذي يساهم به ذلك المحور. وإذا أحصينا عدد مرات ظهور كل قيمة نحصل على المدرج التكراري
$$c_{\mathcal L}(a)=\#\left\{(i,\ell):\ell\in\mathcal L,\ \ell\le i,\ m_{i,\ell}=a\right\}.$$
أما النيمبر الكلي للمحور كله فهو ببساطة
$$X_{\mathcal L}=x_N.$$
ليكن \(X_{\mathcal T}\) هو النيمبر الكلي لمحور الارتفاعات المثلثية، و\(X_{\mathcal S}\) هو النيمبر الكلي لمحور العروض المربعة. عندئذ يكون نيمبر اللوح الكامل
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S},$$
حيث ترمز \(\otimes\) إلى ضرب النيمبر. وبالمثل، إذا كان نيمبر نقلة الصفوف هو \(a\) ونيمبر نقلة الأعمدة هو \(b\)، فإن نيمبر نقلة المستطيل المقابلة يساوي
$$a\otimes b.$$
وفق قاعدة اللعب العادي، تكون النقلة الافتتاحية رابحة إذا وفقط إذا نقلت الوضع إلى نيمبر \(0\)، وهو ما يكافئ هنا الشرط
$$a\otimes b=\Gamma.$$
إذا كان \(\Gamma=0\)، فإن ضرب النيمبر لا يملك قواسم صفرية، ولذلك
$$a\otimes b=0 \iff (a=0)\lor(b=0).$$
ومن ثم يكون عدد النقلات الافتتاحية الرابحة
$$c_{\mathcal T}(0)\sum_b c_{\mathcal S}(b)+c_{\mathcal S}(0)\sum_a c_{\mathcal T}(a)-c_{\mathcal T}(0)c_{\mathcal S}(0).$$
أما إذا كان \(\Gamma\neq 0\)، فإن كل \(a\neq 0\) يحدد شريكًا وحيدًا
$$b=a^{-1}\otimes \Gamma,$$
ومن ثم تصبح الإجابة
$$P(N)=\sum_{a\ne 0} c_{\mathcal T}(a)\,c_{\mathcal S}\!\left(a^{-1}\otimes \Gamma\right).$$
وتحسب التطبيقات المقلوبات داخل حقل نيمبر منتهٍ كبير بما يكفي، باستخدام العلاقة \(a^{-1}=a^{q-2}\) عندما يكون حجم الحقل \(q\) أكبر من جميع النيمبرات التي ظهرت.
عندما \(N=5\)، تكون الأطوال القانونية هي
$$\mathcal T_5=\{1,3\},\qquad \mathcal S_5=\{1,4\}.$$
على جهة الارتفاعات المثلثية تعطي العلاقة
$$g_1=g_2=g_3=g_4=g_5=1,$$
ومن ثم يكون النيمبر الكلي لذلك المحور \(X_{\mathcal T}=1\). يوجد \(5+3=8\) مقاطع صفوف قانونية، وكل واحد منها يملك نيمبر نقلة يساوي \(1\)، ولذلك
$$c_{\mathcal T}(1)=8.$$
أما على جهة العروض المربعة فتعطي العلاقة
$$g_1=1,\qquad g_2=1,\qquad g_3=1,\qquad g_4=2,\qquad g_5=1,$$
ولهذا
$$X_{\mathcal S}=1\oplus 1\oplus 1\oplus 2\oplus 1=2.$$
ويكون مدرج الأعمدة التكراري
$$c_{\mathcal S}(1)=4,\qquad c_{\mathcal S}(2)=1,\qquad c_{\mathcal S}(3)=2.$$
إذًا نيمبر اللوح هو
$$\Gamma=X_{\mathcal T}\otimes X_{\mathcal S}=1\otimes 2=2.$$
وبما أن جهة الصفوف لا تعطي إلا \(a=1\)، فإن شرط الفوز يفرض
$$b=1^{-1}\otimes 2=2.$$
يوجد \(8\) نقلات صفوف من هذا النوع ونقلة أعمدة مطابقة واحدة فقط، وبالتالي
$$P(5)=8\cdot 1=8,$$
وهو تمامًا مقدار التحقق المستعمل في التطبيقات.
تبدأ تطبيقات C++ وPython وJava بتوليد جميع الارتفاعات المثلثية والعروض المربعة التي لا تتجاوز \(N\). ولكل عائلة أطوال، تمر من \(1\) إلى \(N\)، وتحافظ على جدول xor التراكمي \(x_i\)، وتحسب جميع نيمبرات الأبناء الممكنة \(y_{i,\ell}\)، وتأخذ mex للحصول على قيمة Grundy التالية، ثم تحدّث مدرجًا تكراريًا لنيمبرات النقلات \(m_{i,\ell}\).
ولجعل خطوة mex سريعة، تستخدم الشيفرة تخزينًا تكراريًا مؤقتًا فقط للقيم التي ظهرت فعلًا عند الحجم الحالي \(i\)، ثم تنظّف العناصر التي لُمست فقط. كما تبدأ بحجم معتدل لجدول النيمبرات، وتضاعفه إذا ظهر نيمبر أكبر، فلا تعيد الحساب إلا عند الحاجة.
بعد اكتمال مدرجي المحورين، تحسب الشيفرة نيمبر اللوح الكلي \(\Gamma\) بواسطة ضرب نيمبر عودي مع حفظ نتائج، مبني على تفكيك قوى \(2\) من نمط فيرما. ثم تطبق صيغ العد السابقة مباشرة: شمول واستبعاد عندما \(\Gamma=0\)، واستعمال المقلوب الضربي عندما \(\Gamma\neq 0\). وتستخدم نسخة Python نفس الحساب الأساسي، لذلك فالمنهج الرياضي واحد في اللغات الثلاث.
لتكن \(t=|\mathcal T_N|\) و\(s=|\mathcal S_N|\). بما أن \(t=\Theta(\sqrt N)\) و\(s=\Theta(\sqrt N)\)، فإن المرورين الأحاديين البعد يكلفان
$$O(Nt)+O(Ns)=O(N^{3/2}).$$
أما المطابقة النهائية بين المدرجات التكرارية فهي خطية في حجم جدول النيمبر المطلوب فعلًا، ولذلك فهي أصغر من المرور الرئيسي ذي الكلفة \(O(N^{3/2})\). واستخدام الذاكرة هو \(O(N)\) لبيانات البادئات والمدرجات التكرارية والجداول المؤقتة، لذا فالتعقيد المكاني الكلي خطي.