Consider an \(n \times n\) board, indexed by coordinates \(0,1,\dots,n-1\) on each axis. A move decreases exactly one coordinate by one of the low primes \(2,3,5,7\), provided the result stays nonnegative. With \(c\) independent tokens, the whole position is an impartial normal-play sum, so it is losing exactly when the XOR of the token Grundy values is \(0\). The task is to count winning starting placements modulo \(10^9\).
The direct search space has size \((n^2)^c\), which is hopeless for the actual parameters. The key simplification is to solve the one-coordinate game first, then lift that information to one square, and finally combine \(c\) independent squares by XOR convolution.
Let \(s(i)\) be the Sprague-Grundy value of a single coordinate at position \(i\). Legal moves go to \(i-2\), \(i-3\), \(i-5\), and \(i-7\) whenever those positions exist, so
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\},$$
where invalid predecessors are ignored. The base cases are immediate:
$$s(0)=s(1)=0.$$
The next values are obtained mechanically from the recurrence:
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
Only four follower values are ever inspected, so the mex can never exceed \(4\). Therefore
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
A token on square \((x,y)\) is the disjunctive sum of two independent coordinate games, one on \(x\) and one on \(y\). By the Sprague-Grundy theorem, the square value is therefore
$$G(x,y)=s(x)\oplus s(y).$$
Now define the one-dimensional frequency table
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
Then the number of board squares with value \(t\) is
$$B_t=\sum_{a\oplus b=t} A_aA_b.$$
This is just the XOR convolution of the coordinate distribution with itself, and it satisfies
$$\sum_{t=0}^7 B_t=n^2.$$
Let \(D_j(u)\) denote the number of ways to place \(j\) tokens so that the XOR of their square values is \(u\). The empty placement has XOR \(0\), so
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
When one more token is added on a square of value \(t\), the total XOR changes from \(v\) to \(v\oplus t\). Hence
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t.$$
After \(c\) steps, the losing placements are exactly those with zero nim-sum:
$$L=D_c(0).$$
Each token independently chooses one of the \(n^2\) squares, so the total number of placements is
$$T=(n^2)^c.$$
Therefore the required answer is
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
The entire problem is now reduced to a small fixed-state dynamic program after the initial one-dimensional scan.
From Step 1, each coordinate Grundy value lies in \(\{0,1,2,3,4\}\). Therefore a square value \(s(x)\oplus s(y)\) can only lie in
$$\{0,1,2,3,4,5,6,7\}.$$
So both \(B_t\) and \(D_j(u)\) live in only eight states, regardless of how large \(n\) becomes. That is why the huge board size does not produce a huge state space.
For coordinates \(0,1,2\), the one-dimensional values are
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1,$$
so the frequency table is
$$A_0=2,\qquad A_1=1.$$
The board distribution becomes
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
and all other \(B_t\) are \(0\). For one token this already gives
$$D_1(0)=5,\qquad D_1(1)=4.$$
For two tokens, the zero-XOR count is
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41.$$
The total number of placements is
$$T=(3^2)^2=81,$$
so the winning count is
$$W(3,2)=81-41=40,$$
which matches the implementation checkpoint.
The C++, Python, and Java implementations first scan the coordinates \(0,1,\dots,n-1\) and compute the one-dimensional Grundy values directly from the mex recurrence. Because the recurrence only looks back \(2\), \(3\), \(5\), and \(7\) steps, the implementation keeps a rolling window of recent values instead of storing the whole sequence. During the same pass it accumulates the frequency table \(A_r\).
Next, the implementation forms the board distribution \(B_t\) by combining every pair of one-dimensional values with XOR. This is a tiny constant-size computation because only eight square states are relevant. It then performs a \(c\)-step dynamic program on those eight XOR states, reducing after every multiplication and addition modulo \(10^9\).
Finally, the implementation computes \((n^2)^c \bmod 10^9\) with fast modular exponentiation, subtracts the zero-XOR count, and formats the result as a nine-digit string. The small consistency checks \(W(3,1)=4\), \(W(3,2)=40\), and \(W(9,3)=450304\) agree with the derivation above.
Computing the one-dimensional Grundy sequence for \(n\) coordinates takes \(O(n)\) time. Building the board distribution is constant work because the set of square values has fixed size \(8\). The \(c\)-token dynamic program also runs over those same eight states, so it costs \(O(c)\) time with a small constant factor. Fast modular exponentiation adds \(O(\log c)\). For this fixed move set, the overall method is \(O(n+c)\) time and \(O(1)\) auxiliary memory.
Betrachte ein \(n \times n\)-Brett mit Koordinaten \(0,1,\dots,n-1\) auf jeder Achse. Ein Zug verringert genau eine Koordinate um eine der kleinen Primzahlen \(2,3,5,7\), sofern das Ergebnis nicht negativ wird. Bei \(c\) unabhängigen Steinen ist die Gesamtstellung eine unparteiische Normalspielsumme und damit genau dann verloren, wenn das XOR der einzelnen Grundy-Werte \(0\) ist. Gesucht ist die Anzahl der Gewinnstellungen modulo \(10^9\).
Der direkte Suchraum hat Größe \((n^2)^c\) und ist für die echten Parameter unbrauchbar. Die Lösung zerlegt das Problem deshalb in drei Ebenen: zuerst das eindimensionale Subtraktionsspiel, dann die Verteilung der Grundy-Werte auf einem einzelnen Brettfeld und schließlich die Kombination von \(c\) unabhängigen Feldern per XOR-Faltung.
Sei \(s(i)\) der Sprague-Grundy-Wert einer einzelnen Koordinate in Position \(i\). Erlaubte Züge führen nach \(i-2\), \(i-3\), \(i-5\) und \(i-7\), falls diese Positionen existieren. Also gilt
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\}.$$
Ungültige Vorgänger werden ignoriert. Die Anfangswerte sind sofort klar:
$$s(0)=s(1)=0.$$
Die ersten Werte lauten dann
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
Da höchstens vier Nachfolgerwerte betrachtet werden, kann der mex nie größer als \(4\) werden. Somit gilt
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
Ein Stein auf dem Feld \((x,y)\) ist die disjunktive Summe zweier unabhängiger Koordinatenspiele, eines auf \(x\) und eines auf \(y\). Nach dem Sprague-Grundy-Satz ist der Feldwert also
$$G(x,y)=s(x)\oplus s(y).$$
Definiere nun die eindimensionale Häufigkeitstabelle
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
Dann ist die Anzahl der Brettfelder mit Wert \(t\)
$$B_t=\sum_{a\oplus b=t} A_aA_b.$$
Das ist die XOR-Faltung der Koordinatenverteilung mit sich selbst, und es gilt
$$\sum_{t=0}^7 B_t=n^2.$$
Sei \(D_j(u)\) die Anzahl der Platzierungen von \(j\) Steinen, deren Gesamt-XOR den Wert \(u\) hat. Für die leere Platzierung gilt
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
Fügt man einen weiteren Stein auf einem Feld mit Wert \(t\) hinzu, so ändert sich das Gesamt-XOR von \(v\) nach \(v\oplus t\). Daher
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t.$$
Nach \(c\) Schritten sind genau die Platzierungen mit Null-XOR Verluststellungen:
$$L=D_c(0).$$
Jeder Stein wählt unabhängig eines der \(n^2\) Felder. Deshalb ist die Gesamtzahl aller Platzierungen
$$T=(n^2)^c.$$
Die gesuchte Antwort ist somit
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
Nach dem anfänglichen eindimensionalen Durchlauf bleibt also nur noch eine winzige Zustandsdynamik übrig.
Aus Schritt 1 folgt \(s(i)\in\{0,1,2,3,4\}\). Also kann ein Feldwert \(s(x)\oplus s(y)\) nur in
$$\{0,1,2,3,4,5,6,7\}$$
liegen. Deshalb benötigen sowohl \(B_t\) als auch \(D_j(u)\) nur acht Zustände, unabhängig von der Größe von \(n\).
Für die Koordinaten \(0,1,2\) sind die eindimensionalen Werte
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1,$$
also
$$A_0=2,\qquad A_1=1.$$
Damit ergibt sich für das Brett
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
und alle übrigen \(B_t\) verschwinden. Für einen Stein folgt
$$D_1(0)=5,\qquad D_1(1)=4.$$
Für zwei Steine ist die Anzahl der Null-XOR-Platzierungen
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41.$$
Die Gesamtzahl aller Platzierungen ist
$$T=(3^2)^2=81,$$
also
$$W(3,2)=81-41=40,$$
genau der Kontrollwert aus der Implementierung.
Die C++-, Python- und Java-Implementierungen durchlaufen zunächst die Koordinaten \(0,1,\dots,n-1\) und berechnen die eindimensionalen Grundy-Werte direkt aus der mex-Rekursion. Weil die Rekursion nur \(2\), \(3\), \(5\) und \(7\) Schritte zurückblickt, genügt ein rollierender Puffer für die letzten Werte; die gesamte Folge muss nicht gespeichert werden. Gleichzeitig wird die Häufigkeitstabelle \(A_r\) aufgebaut.
Anschließend bildet die Implementierung die Brettverteilung \(B_t\), indem sie alle Paare eindimensionaler Werte per XOR kombiniert. Das ist eine reine Konstantenarbeit, weil nur acht Feldzustände relevant sind. Danach läuft eine \(c\)-stufige Dynamik über diesen acht XOR-Zuständen, wobei nach jeder Multiplikation und Addition modulo \(10^9\) reduziert wird.
Zum Schluss berechnet die Implementierung \((n^2)^c \bmod 10^9\) per schneller modularer Exponentiation, zieht die Null-XOR-Anzahl ab und formatiert das Ergebnis als neunstellige Zeichenkette. Die Konsistenzprüfungen \(W(3,1)=4\), \(W(3,2)=40\) und \(W(9,3)=450304\) passen genau zur obigen Herleitung.
Die Berechnung der eindimensionalen Grundy-Folge für \(n\) Koordinaten kostet \(O(n)\) Zeit. Die Brettverteilung entsteht in konstanter Zeit, weil die Zahl der möglichen Feldwerte fest \(8\) ist. Das dynamische Programm für \(c\) Steine läuft ebenfalls nur über diese acht Zustände und benötigt daher \(O(c)\) Zeit mit kleinem konstantem Faktor. Die modulare Exponentiation trägt \(O(\log c)\) bei. Für diese feste Zugmenge ergibt sich insgesamt \(O(n+c)\) Zeit und \(O(1)\) Zusatzspeicher.
\(n \times n\) boyutlu bir tahta düşünelim; her eksen \(0,1,\dots,n-1\) ile indeksleniyor. Bir hamle, tam olarak bir koordinatı düşük asallardan biri olan \(2,3,5,7\) kadar azaltır ve sonuç negatif olamaz. \(c\) bağımsız taş birlikte ele alındığında oyun tarafsız normal oyundur; dolayısıyla konum, taşların Grundy değerlerinin XOR'u \(0\) ise kaybedendir. İstenen şey, kazanan başlangıç yerleşimlerinin sayısını \(10^9\) modunda bulmaktır.
Doğrudan arama uzayı \((n^2)^c\) büyüklüğündedir ve gerçek parametrelerde kullanılamaz. Çözüm önce tek koordinatlı oyunu çözer, sonra bunu tek bir kareye taşır ve en sonunda \(c\) bağımsız karenin dağılımını XOR konvolüsyonu ile birleştirir.
\(s(i)\), tek bir koordinatın \(i\) konumundaki Sprague-Grundy değeri olsun. Geçerli hamleler \(i-2\), \(i-3\), \(i-5\) ve \(i-7\) konumlarına gider. O halde
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\}$$
olur; geçersiz öncüller dikkate alınmaz. Başlangıç durumları hemen bulunur:
$$s(0)=s(1)=0.$$
İlk birkaç değer şunlardır:
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
Her adımda en fazla dört takipçi değerine bakıldığı için mex hiçbir zaman \(4\)'ü aşamaz. Dolayısıyla
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
\((x,y)\) karesindeki bir taş, \(x\) ve \(y\) koordinatları üzerindeki iki bağımsız oyunun ayrık toplamıdır. Sprague-Grundy teoremine göre karenin değeri
$$G(x,y)=s(x)\oplus s(y)$$
olur. Şimdi tek boyutlu frekans tablosunu tanımlayalım:
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
Buna göre değeri \(t\) olan kare sayısı
$$B_t=\sum_{a\oplus b=t} A_aA_b$$
şeklindedir. Bu, koordinat dağılımının kendisiyle XOR konvolüsyonudur ve
$$\sum_{t=0}^7 B_t=n^2$$
eşitliği sağlanır.
\(D_j(u)\), \(j\) taş yerleştirildiğinde toplam XOR değerinin \(u\) olma sayısı olsun. Boş yerleşim için
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
Yeni bir taş değeri \(t\) olan kareye geldiğinde toplam XOR, \(v\)'den \(v\oplus t\)'ye dönüşür. Bu nedenle geçiş
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t$$
şeklindedir. \(c\) adım sonunda kaybeden yerleşimler tam olarak sıfır nim-toplam verenlerdir:
$$L=D_c(0).$$
Her taş \(n^2\) kareden birini bağımsız seçtiği için toplam yerleşim sayısı
$$T=(n^2)^c$$
olur. Dolayısıyla aranan sonuç
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
Böylece problem, başlangıçtaki tek boyutlu taramadan sonra sabit büyüklükte bir dinamik programlamaya indirgenmiş olur.
Adım 1'den \(s(i)\in\{0,1,2,3,4\}\) olduğunu biliyoruz. O zaman kare değeri \(s(x)\oplus s(y)\) ancak
$$\{0,1,2,3,4,5,6,7\}$$
kümesinde olabilir. Bu yüzden hem \(B_t\) hem de \(D_j(u)\) yalnızca sekiz durum kullanır; \(n\) ne kadar büyürse büyüsün bu değişmez.
\(0,1,2\) koordinatları için tek boyutlu değerler
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1$$
olduğundan
$$A_0=2,\qquad A_1=1.$$
Tahta dağılımı şu olur:
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
ve diğer tüm \(B_t\) değerleri \(0\)'dır. Bir taş için
$$D_1(0)=5,\qquad D_1(1)=4.$$
İki taşta sıfır XOR sayısı
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41$$
çıkar. Toplam yerleşim sayısı
$$T=(3^2)^2=81$$
olduğundan
$$W(3,2)=81-41=40$$
elde edilir; bu da uygulamadaki kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce \(0,1,\dots,n-1\) koordinatlarını dolaşarak tek boyutlu Grundy değerlerini mex bağıntısından doğrudan hesaplar. Bağıntı yalnızca \(2\), \(3\), \(5\) ve \(7\) adım geriye baktığı için tüm dizi tutulmaz; yalnızca son değerleri içeren döngüsel bir pencere yeterlidir. Aynı geçiş sırasında \(A_r\) frekans tablosu da biriktirilir.
Daha sonra uygulama, tek boyutlu değer çiftlerini XOR ile birleştirerek tahta dağılımı \(B_t\)'yi kurar. Bu bölüm sabit maliyetlidir, çünkü yalnızca sekiz kare durumu vardır. Ardından aynı sekiz XOR durumu üzerinde \(c\) adımlı bir dinamik program çalıştırılır ve her toplama-çarpma sonrası sonuç \(10^9\) moduna indirilir.
Son aşamada \((n^2)^c \bmod 10^9\) hızlı modüler üs alma ile hesaplanır, sıfır XOR veren yerleşim sayısı çıkarılır ve sonuç dokuz haneli biçimde yazdırılır. \(W(3,1)=4\), \(W(3,2)=40\) ve \(W(9,3)=450304\) kontrolleri yukarıdaki matematikle tutarlıdır.
\(n\) koordinatı için tek boyutlu Grundy dizisini üretmek \(O(n)\) zaman alır. Tahta dağılımı, olası kare değerleri sabit olarak \(8\) tane olduğu için sabit zamanda kurulur. \(c\) taş için dinamik program da yine aynı sekiz durum üzerinde çalıştığından \(O(c)\) zaman gerektirir; sabit katsayısı küçüktür. Hızlı modüler üs alma \(O(\log c)\) ekler. Bu sabit hamle kümesi için toplam karmaşıklık \(O(n+c)\), ek bellek ise \(O(1)\)'dir.
Consideremos un tablero \(n \times n\), con coordenadas \(0,1,\dots,n-1\) en cada eje. Un movimiento reduce exactamente una coordenada en uno de los primos pequeños \(2,3,5,7\), siempre que el resultado no sea negativo. Con \(c\) fichas independientes, la posición completa es una suma imparcial en juego normal, así que es perdedora exactamente cuando el XOR de los valores de Grundy de las fichas vale \(0\). La tarea consiste en contar las posiciones iniciales ganadoras módulo \(10^9\).
El espacio de búsqueda directo tiene tamaño \((n^2)^c\), imposible para los parámetros reales. La solución lo descompone en tres capas: primero resuelve el juego de una sola coordenada, después obtiene la distribución de valores sobre una casilla del tablero y por último combina \(c\) casillas independientes mediante convolución XOR.
Sea \(s(i)\) el valor de Sprague-Grundy de una sola coordenada en la posición \(i\). Los movimientos legales llevan a \(i-2\), \(i-3\), \(i-5\) y \(i-7\) cuando esas posiciones existen, por lo que
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\}.$$
Los predecesores inválidos se ignoran. Los casos base son
$$s(0)=s(1)=0.$$
Los primeros términos quedan
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
Como en cada paso solo se miran cuatro valores sucesores, el mex nunca puede superar \(4\). En consecuencia,
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
Una ficha en la casilla \((x,y)\) es la suma disyunta de dos juegos de coordenada, uno sobre \(x\) y otro sobre \(y\). Por el teorema de Sprague-Grundy, el valor de la casilla es
$$G(x,y)=s(x)\oplus s(y).$$
Definimos la tabla de frecuencias unidimensional
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
Entonces el número de casillas con valor \(t\) es
$$B_t=\sum_{a\oplus b=t} A_aA_b.$$
Esta es la convolución XOR de la distribución de coordenadas consigo misma, y satisface
$$\sum_{t=0}^7 B_t=n^2.$$
Sea \(D_j(u)\) el número de formas de colocar \(j\) fichas de modo que el XOR total de sus valores sea \(u\). Para la colocación vacía se tiene
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
Si añadimos una ficha en una casilla de valor \(t\), el XOR total cambia de \(v\) a \(v\oplus t\). Por tanto,
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t.$$
Tras \(c\) pasos, las colocaciones perdedoras son exactamente las que tienen nim-suma cero:
$$L=D_c(0).$$
Cada ficha elige de manera independiente una de las \(n^2\) casillas, así que el número total de colocaciones es
$$T=(n^2)^c.$$
La cantidad buscada es entonces
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
Una vez construida la distribución unidimensional, todo lo que queda es una DP pequeña sobre un número fijo de estados.
Del Paso 1 se deduce que \(s(i)\in\{0,1,2,3,4\}\). Por eso el valor de una casilla \(s(x)\oplus s(y)\) solo puede pertenecer a
$$\{0,1,2,3,4,5,6,7\}.$$
Así, tanto \(B_t\) como \(D_j(u)\) viven en solo ocho estados, sin importar cuán grande sea \(n\).
Para las coordenadas \(0,1,2\), los valores unidimensionales son
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1,$$
de modo que
$$A_0=2,\qquad A_1=1.$$
La distribución sobre el tablero queda
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
y todos los demás \(B_t\) valen \(0\). Para una ficha obtenemos
$$D_1(0)=5,\qquad D_1(1)=4.$$
Para dos fichas, el número de colocaciones con XOR total cero es
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41.$$
El número total de colocaciones es
$$T=(3^2)^2=81,$$
así que
$$W(3,2)=81-41=40,$$
exactamente el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java recorren primero las coordenadas \(0,1,\dots,n-1\) y calculan los valores de Grundy unidimensionales directamente a partir de la recurrencia con mex. Como la recurrencia solo necesita mirar \(2\), \(3\), \(5\) y \(7\) pasos hacia atrás, la implementación conserva una ventana circular de valores recientes en lugar de guardar toda la secuencia. En el mismo recorrido acumula la tabla de frecuencias \(A_r\).
Después, la implementación construye la distribución del tablero \(B_t\) combinando por XOR todos los pares de valores unidimensionales. Esa parte es de tamaño constante, porque solo hay ocho estados de casilla relevantes. Luego ejecuta una programación dinámica de \(c\) pasos sobre esos ocho estados de XOR, reduciendo cada suma y cada producto módulo \(10^9\).
Por último, la implementación calcula \((n^2)^c \bmod 10^9\) mediante exponenciación modular rápida, resta la cantidad de posiciones con XOR cero y formatea la salida con nueve dígitos. Las comprobaciones \(W(3,1)=4\), \(W(3,2)=40\) y \(W(9,3)=450304\) concuerdan con la derivación matemática.
Calcular la secuencia unidimensional para \(n\) coordenadas cuesta \(O(n)\) tiempo. Construir la distribución del tablero cuesta tiempo constante porque el número de valores posibles de una casilla es el fijo \(8\). La programación dinámica para \(c\) fichas también trabaja solo con esos ocho estados, así que cuesta \(O(c)\) tiempo con una constante pequeña. La exponenciación modular rápida añade \(O(\log c)\). Para este conjunto fijo de movimientos, el método completo usa \(O(n+c)\) tiempo y \(O(1)\) memoria auxiliar.
考虑一个 \(n \times n\) 的棋盘，每个坐标轴都用 \(0,1,\dots,n-1\) 编号。一次合法移动会把某一个坐标减少 \(2,3,5,7\) 中的一个低素数，并且结果不能为负。若有 \(c\) 个彼此独立的棋子，那么整体局面是若干个公平组合博弈的和，因此当且仅当所有棋子 Grundy 值的按位异或结果为 \(0\) 时，这个局面是必败局。题目要求的是必胜初始摆放方案数，并对 \(10^9\) 取模。
直接枚举的规模是 \((n^2)^c\)，对真实参数完全不可行。解法的核心是分三层处理：先解一维减法博弈，再把一维结果提升到二维格点，最后把 \(c\) 个独立格点用 XOR 卷积组合起来。
设 \(s(i)\) 表示单个坐标位于位置 \(i\) 时的 Sprague-Grundy 值。合法后继是 \(i-2\)、\(i-3\)、\(i-5\)、\(i-7\) 中仍然存在的那些位置，因此有递推式
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\}.$$
不可达的前驱直接忽略。最初两个位置没有任何合法移动，所以
$$s(0)=s(1)=0.$$
按此递推计算，前几项为
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
每一步最多只会观察四个后继值，因此 mex 不可能超过 \(4\)。于是可以立即得到
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
位于 \((x,y)\) 的一个棋子，可以看作两个独立一维博弈的组合：一个作用在 \(x\) 坐标上，另一个作用在 \(y\) 坐标上。根据 Sprague-Grundy 定理，这个格点的 Grundy 值为
$$G(x,y)=s(x)\oplus s(y).$$
接着定义一维频数表
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
那么棋盘上 Grundy 值等于 \(t\) 的格点个数就是
$$B_t=\sum_{a\oplus b=t} A_aA_b.$$
这正是一维分布与自身的 XOR 卷积，并满足
$$\sum_{t=0}^7 B_t=n^2.$$
令 \(D_j(u)\) 表示放置 \(j\) 个棋子后，总 Grundy 异或值恰好等于 \(u\) 的方案数。空摆放只有一种，且其异或值为 \(0\)，因此
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
如果再加入一个落在值为 \(t\) 的格点上的棋子，那么总异或值会从 \(v\) 变成 \(v\oplus t\)。所以转移公式为
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t.$$
经过 \(c\) 次转移以后，所有总异或值为 \(0\) 的摆放恰好就是必败摆放：
$$L=D_c(0).$$
每个棋子都可以独立选择 \(n^2\) 个格点之一，因此总摆放数为
$$T=(n^2)^c.$$
于是题目所求为
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
这样一来，原问题在完成一维扫描之后，就只剩下一个固定八状态的动态规划。
由步骤 1 知道，一维 Grundy 值只可能落在 \(\{0,1,2,3,4\}\) 中。因此单个格点的值 \(s(x)\oplus s(y)\) 只能落在
$$\{0,1,2,3,4,5,6,7\}$$
之中。也就是说，频数表 \(B_t\) 和动态规划 \(D_j(u)\) 都只需要处理 8 个状态，和 \(n\) 的大小无关。这正是超大棋盘仍然可计算的原因。
当坐标只有 \(0,1,2\) 时，一维 Grundy 值为
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1,$$
因此频数表为
$$A_0=2,\qquad A_1=1.$$
棋盘格点的分布随之变成
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
其余所有 \(B_t\) 都等于 \(0\)。对于 1 个棋子，立刻得到
$$D_1(0)=5,\qquad D_1(1)=4.$$
对于 2 个棋子，总异或值为 \(0\) 的方案数为
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41.$$
全部摆放方案数为
$$T=(3^2)^2=81,$$
因此必胜方案数是
$$W(3,2)=81-41=40,$$
这与实现中的校验值完全一致。
C++、Python 和 Java 实现首先线性扫描坐标 \(0,1,\dots,n-1\)，按照 mex 递推直接计算每个位置的一维 Grundy 值。由于递推只会访问前面 \(2\)、\(3\)、\(5\)、\(7\) 个单位的位置，实现中只保留一个最近值的滚动窗口，而不必存下整条序列。同时，它会在这一遍扫描中累计一维频数表 \(A_r\)。
随后，实现通过枚举所有一维值对并取 XOR，得到棋盘格点分布 \(B_t\)。因为真正会出现的格点状态只有 8 个，这一步的代价是常数级。之后程序在这 8 个 XOR 状态上做 \(c\) 轮动态规划，每一轮都在模 \(10^9\) 下完成乘法和加法。
最后，实现利用快速模幂计算 \((n^2)^c \bmod 10^9\)，减去零异或的必败方案数，并把结果格式化为九位字符串。校验值 \(W(3,1)=4\)、\(W(3,2)=40\)、\(W(9,3)=450304\) 与上面的推导一致。
计算 \(n\) 个坐标的一维 Grundy 序列需要 \(O(n)\) 时间。构造棋盘分布只涉及固定的 8 个状态，因此是常数时间。对 \(c\) 个棋子的动态规划同样只在这 8 个状态上进行，所以时间是 \(O(c)\)，常数很小。快速模幂再增加 \(O(\log c)\)。对于这组固定移动，整体时间复杂度是 \(O(n+c)\)，辅助空间复杂度是 \(O(1)\)。
Рассмотрим доску \(n \times n\), где каждая координата пробегает значения \(0,1,\dots,n-1\). Один ход уменьшает ровно одну координату на одно из малых простых чисел \(2,3,5,7\), если результат остается неотрицательным. При \(c\) независимых фишках вся позиция является суммой беспристрастных игр в нормальной игре, а значит проигрышна тогда и только тогда, когда XOR всех значений Гранди равен \(0\). Требуется посчитать число выигрышных начальных расстановок по модулю \(10^9\).
Прямой перебор имеет размер \((n^2)^c\), что совершенно неприемлемо для реальных параметров. Поэтому решение разбивается на три уровня: сначала решается одномерная игра вычитания, затем эта информация поднимается на отдельную клетку доски, а потом \(c\) независимых клеток объединяются XOR-сверткой.
Пусть \(s(i)\) обозначает значение Спрага-Гранди для одной координаты в позиции \(i\). Разрешенные ходы ведут в \(i-2\), \(i-3\), \(i-5\) и \(i-7\), если такие позиции существуют. Следовательно,
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\}.$$
Недопустимые предшественники просто игнорируются. Базовые значения таковы:
$$s(0)=s(1)=0.$$
Первые члены последовательности получаются такими:
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
На каждом шаге рассматриваются не более четырех значений-потомков, поэтому mex не может быть больше \(4\). Значит,
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
Фишка в клетке \((x,y)\) представляет собой дизъюнктивную сумму двух независимых координатных игр: одной по \(x\) и одной по \(y\). По теореме Спрага-Гранди значение клетки равно
$$G(x,y)=s(x)\oplus s(y).$$
Определим одномерную таблицу частот
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
Тогда число клеток со значением \(t\) равно
$$B_t=\sum_{a\oplus b=t} A_aA_b.$$
Это XOR-свертка одномерного распределения с самим собой, и она удовлетворяет равенству
$$\sum_{t=0}^7 B_t=n^2.$$
Пусть \(D_j(u)\) обозначает число способов поставить \(j\) фишек так, чтобы итоговый XOR их значений был равен \(u\). Для пустой расстановки имеем
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
Если добавить еще одну фишку в клетку со значением \(t\), то общий XOR меняется с \(v\) на \(v\oplus t\). Поэтому переход имеет вид
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t.$$
После \(c\) шагов проигрышные расстановки - это ровно те, где суммарный nim-XOR равен нулю:
$$L=D_c(0).$$
Каждая фишка независимо выбирает одну из \(n^2\) клеток, значит общее число расстановок равно
$$T=(n^2)^c.$$
Искомое число выигрышных расстановок равно
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
После первоначального одномерного прохода задача сводится к очень маленькой динамике по фиксированному числу состояний.
Из шага 1 следует, что одномерные значения лежат в \(\{0,1,2,3,4\}\). Тогда значение клетки \(s(x)\oplus s(y)\) может лежать только в множестве
$$\{0,1,2,3,4,5,6,7\}.$$
Следовательно, и таблица \(B_t\), и динамика \(D_j(u)\) работают всего с восемью состояниями, независимо от величины \(n\).
Для координат \(0,1,2\) одномерные значения таковы:
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1,$$
поэтому
$$A_0=2,\qquad A_1=1.$$
Распределение по клеткам получается таким:
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
а все остальные \(B_t\) равны нулю. Для одной фишки это уже дает
$$D_1(0)=5,\qquad D_1(1)=4.$$
Для двух фишек число расстановок с нулевым XOR равно
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41.$$
Общее число расстановок равно
$$T=(3^2)^2=81,$$
поэтому
$$W(3,2)=81-41=40,$$
что совпадает с контрольным значением в реализации.
Реализации на C++, Python и Java сначала проходят по координатам \(0,1,\dots,n-1\) и напрямую вычисляют одномерные значения Гранди по mex-рекурренте. Поскольку рекурсия смотрит только на позиции, отстоящие на \(2\), \(3\), \(5\) и \(7\), достаточно хранить циклическое окно последних значений, а не всю последовательность целиком. В том же проходе накапливается таблица частот \(A_r\).
Затем реализация строит распределение \(B_t\), комбинируя XOR-ом все пары одномерных значений. Это вычисление имеет постоянный размер, потому что релевантных состояний клетки всего восемь. После этого выполняется динамическое программирование из \(c\) шагов по тем же восьми XOR-состояниям, причем каждая сумма и каждое произведение сразу берутся по модулю \(10^9\).
В конце реализация вычисляет \((n^2)^c \bmod 10^9\) быстрой модульной степенью, вычитает количество нулевых XOR-расстановок и форматирует ответ как девятизначную строку. Проверки \(W(3,1)=4\), \(W(3,2)=40\) и \(W(9,3)=450304\) полностью согласуются с приведенной математикой.
Вычисление одномерной последовательности Гранди для \(n\) координат занимает \(O(n)\) времени. Построение распределения по клеткам требует постоянного времени, поскольку число возможных значений клетки фиксировано и равно \(8\). Динамика для \(c\) фишек также работает только с этими восемью состояниями, поэтому ее стоимость равна \(O(c)\) с малой константой. Быстрое возведение в степень добавляет \(O(\log c)\). Для данного фиксированного набора ходов общий порядок составляет \(O(n+c)\) по времени и \(O(1)\) по дополнительной памяти.
لدينا لوح \(n \times n\) وتؤخذ الإحداثيات على كل محور من المجموعة \(0,1,\dots,n-1\). الحركة القانونية تُنقص إحداثيًا واحدًا فقط بمقدار أحد الأعداد الأولية الصغيرة \(2,3,5,7\) بشرط ألا تصبح النتيجة سالبة. إذا وُجدت \(c\) قطع مستقلة فإن الوضع الكلي هو مجموع ألعاب غير متحيزة بنمط اللعب العادي، ولذلك يكون وضعًا خاسرًا إذا وفقط إذا كان XOR لقيم غرندي الفردية مساويًا للصفر. المطلوب هو عدد أوضاع البداية الرابحة بترديد \(10^9\).
العد المباشر يمر على فضاء حجمه \((n^2)^c\)، وهذا غير ممكن عمليًا للمدخلات الحقيقية. لذلك يقسم الحل المسألة إلى ثلاث طبقات: أولًا نحل لعبة الطرح أحادية البعد، ثم نرفع النتيجة إلى قيمة كل خلية على اللوح، ثم نجمع \(c\) خلايا مستقلة بواسطة التفاف XOR.
لنعرّف \(s(i)\) بأنها قيمة Sprague-Grundy لإحداثي واحد في الموضع \(i\). الحركات المسموح بها تذهب إلى \(i-2\) و\(i-3\) و\(i-5\) و\(i-7\) متى كانت هذه المواضع موجودة، ولذلك
$$s(i)=\operatorname{mex}\{s(i-2),s(i-3),s(i-5),s(i-7)\}.$$
ويتم تجاهل السوابق غير الصالحة. الحالتان الابتدائيتان واضحتان:
$$s(0)=s(1)=0.$$
ومن ثم تبدأ السلسلة بالشكل
$$0,0,1,1,2,2,3,3,4,0,0,1,1,\dots$$
وبما أننا ننظر في كل مرة إلى أربعة قيم تالية على الأكثر، فإن قيمة mex لا يمكن أن تتجاوز \(4\). لذلك نحصل على
$$s(i)\in\{0,1,2,3,4\}\qquad (\forall i\ge 0).$$
القطعة الموجودة في الخلية \((x,y)\) يمكن النظر إليها على أنها مجموع منفصل للعبتين مستقلتين: واحدة على الإحداثي \(x\) وأخرى على الإحداثي \(y\). وبحسب نظرية Sprague-Grundy تكون قيمة الخلية
$$G(x,y)=s(x)\oplus s(y).$$
لنعرّف الآن جدول التكرارات الأحادي
$$A_r=\#\{\,i\in\{0,\dots,n-1\}:s(i)=r\,\}.$$
عندئذ يكون عدد الخلايا التي قيمتها \(t\) هو
$$B_t=\sum_{a\oplus b=t} A_aA_b.$$
وهذا هو التفاف XOR لتوزيع الإحداثي مع نفسه، كما أنه يحقق
$$\sum_{t=0}^7 B_t=n^2.$$
ليكن \(D_j(u)\) عدد الطرق لوضع \(j\) قطع بحيث يكون XOR الكلي لقيمها مساويًا لـ \(u\). في الوضع الفارغ لدينا
$$D_0(0)=1,\qquad D_0(u)=0\quad (u\ne 0).$$
إذا أضفنا قطعة جديدة على خلية قيمتها \(t\)، فإن XOR الكلي يتحول من \(v\) إلى \(v\oplus t\). لذلك تكون علاقة الانتقال
$$D_{j+1}(u)=\sum_{t=0}^7 D_j(u\oplus t)\,B_t.$$
وبعد \(c\) خطوات، فإن الأوضاع الخاسرة هي بالضبط تلك التي يكون فيها مجموع nim مساويًا للصفر:
$$L=D_c(0).$$
كل قطعة تختار بشكل مستقل واحدة من \(n^2\) خلية، لذا فإن العدد الكلي للترتيبات هو
$$T=(n^2)^c.$$
إذن الجواب المطلوب هو
$$W(n,c)\equiv T-L\equiv (n^2)^c-D_c(0)\pmod{10^9}.$$
وهكذا تتحول المسألة بعد المسح الأحادي الأول إلى برمجة ديناميكية صغيرة على عدد ثابت من الحالات.
من الخطوة الأولى نعلم أن \(s(i)\) لا يخرج عن المجموعة \(\{0,1,2,3,4\}\). لذلك فإن قيمة الخلية \(s(x)\oplus s(y)\) لا يمكن إلا أن تكون في
$$\{0,1,2,3,4,5,6,7\}.$$
هذا يعني أن جدول \(B_t\) وكذلك البرمجة الديناميكية \(D_j(u)\) يحتاجان إلى ثماني حالات فقط مهما كان \(n\) كبيرًا.
عند الإحداثيات \(0,1,2\) نحصل على القيم الأحادية
$$s(0)=0,\qquad s(1)=0,\qquad s(2)=1,$$
ومن ثم
$$A_0=2,\qquad A_1=1.$$
ويصبح توزيع قيم الخلايا على اللوح
$$B_0=A_0^2+A_1^2=2^2+1^2=5,$$
$$B_1=A_0A_1+A_1A_0=2\cdot 1+1\cdot 2=4,$$
وجميع القيم الأخرى لـ \(B_t\) تساوي الصفر. بالنسبة إلى قطعة واحدة نحصل على
$$D_1(0)=5,\qquad D_1(1)=4.$$
وبالنسبة إلى قطعتين يكون عدد الأوضاع ذات XOR صفري هو
$$D_2(0)=D_1(0)B_0+D_1(1)B_1=5\cdot 5+4\cdot 4=41.$$
أما العدد الكلي للترتيبات فهو
$$T=(3^2)^2=81,$$
ولذلك
$$W(3,2)=81-41=40,$$
وهو نفس مقدار التحقق المستخدم في التنفيذ.
تبدأ تطبيقات C++ وPython وJava بمسح الإحداثيات \(0,1,\dots,n-1\) وحساب قيم غرندي الأحادية مباشرة من علاقة mex. ولأن العلاقة لا تنظر إلا إلى المواضع التي تبعد \(2\) و\(3\) و\(5\) و\(7\) خطوات إلى الخلف، فإن التنفيذ يحتفظ بنافذة دائرية صغيرة من القيم الأخيرة بدلًا من تخزين السلسلة كاملة. وخلال المرور نفسه يتم أيضًا بناء جدول التكرارات \(A_r\).
بعد ذلك يبني التنفيذ توزيع اللوح \(B_t\) عن طريق جمع كل أزواج القيم الأحادية باستخدام XOR. وهذه العملية ذات كلفة ثابتة لأن عدد حالات الخلية الفعلية هو ثمانية فقط. ثم تُجرى برمجة ديناميكية من \(c\) مراحل فوق هذه الحالات الثماني، مع أخذ الباقي modulo \(10^9\) بعد كل عملية جمع أو ضرب.
في النهاية يحسب التنفيذ \((n^2)^c \bmod 10^9\) بواسطة الأس السريع المعياري، ويطرح عدد الأوضاع ذات XOR الصفري، ثم ينسق الناتج على هيئة سلسلة من تسع خانات. وقيم التحقق \(W(3,1)=4\) و\(W(3,2)=40\) و\(W(9,3)=450304\) تتفق تمامًا مع الاشتقاق الرياضي السابق.
حساب متتالية غرندي الأحادية لـ \(n\) إحداثيات يحتاج إلى زمن \(O(n)\). وبناء توزيع اللوح يتم في زمن ثابت لأن عدد قيم الخلية الممكنة ثابت ويساوي \(8\). أما البرمجة الديناميكية الخاصة بـ \(c\) قطع فتعمل هي أيضًا على هذه الحالات الثماني فقط، ولذلك تكلفتها \(O(c)\) بزمن ثابت صغير. ويضيف الأس السريع المعياري مقدار \(O(\log c)\). لهذه المجموعة الثابتة من النقلات يكون التعقيد الكلي \(O(n+c)\) زمنيًا و\(O(1)\) في الذاكرة الإضافية.