We play on a strip of length \(n\). A move removes two adjacent cells, so the strip breaks into a left part and a right part. Under normal play, the player who makes the last legal move wins. The Project Euler question asks for how many lengths \(1 \le n \le 10^6\) the starting player has a winning strategy.
If we remove the domino covering positions \(\ell+1\) and \(\ell+2\), the remaining cells split into two independent strips of lengths
$$\ell \quad \text{and} \quad n-2-\ell.$$
Because the two sides no longer interact, the position after one move is the disjoint sum of two smaller games. That is exactly the setting where Sprague-Grundy theory applies.
Let \(g(n)\) be the Grundy number of a strip of length \(n\). The empty strip and the length-1 strip have no legal move, so
$$g(0)=0,\qquad g(1)=0.$$
For \(n \ge 2\), every legal move produces the xor of two smaller Grundy numbers, hence
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
The mex operator returns the smallest nonnegative integer that does not appear among the reachable xor-values.
The move with split \((\ell,n-2-\ell)\) gives the same xor-value as the mirrored move \((n-2-\ell,\ell)\), because xor is commutative:
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
So the implementation only iterates while \(\ell \le n-2-\ell\). This does not change the reachable set; it only avoids duplicate work.
The first few values already show the mechanism clearly.
For \(n=2\), the only move leaves \((0,0)\), so the reachable set is \(\{0\}\), hence
$$g(2)=\operatorname{mex}\{0\}=1.$$
For \(n=4\), the legal splits are \((0,2)\) and \((1,1)\), so the reachable set is
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
therefore
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
For \(n=5\), the only distinct splits are \((0,3)\) and \((1,2)\), and both give xor-value \(1\). Thus
$$g(5)=\operatorname{mex}\{1\}=0.$$
So length \(5\) is a losing position: every legal move hands a winning position to the opponent.
A position is losing exactly when its Grundy number is zero. Therefore a strip length \(n\) is winning iff
$$g(n)\neq 0.$$
The computed prefix begins
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
So the first losing lengths are
$$1,5,9,15,\dots$$
and among \(1 \le n \le 5\) the winners are \(2,3,4\). This matches the checkpoint
$$\texttt{solve(5)}=3.$$
The source also checks
$$\texttt{solve(50)}=40.$$
For many finite splitting games, the Grundy sequence eventually becomes periodic, and this game shows that behavior too. The implementation does not prove periodicity from first principles; instead it computes a long prefix and verifies the pattern
$$g(n)=g(100+((n-100)\bmod 34))$$
for every
$$100 \le n \le 1200.$$
After that validation step, the solver safely reuses the same period-\(34\) block to count winning lengths up to \(10^6\). So the program relies on a checked empirical periodicity, not on an unproved guess.
1) Prefix computation. compute_grundy(n) builds the table \(g(0),g(1),\dots,g(n)\) in increasing order, so when it needs \(g(\ell)\) and \(g(n-2-\ell)\), those values already exist.
2) Fast mex with timestamps. Instead of clearing a boolean array for every length, the code stores seen[value] = length. Then a value is known to belong to the current reachable set exactly when seen[value] == length. This is a classic timestamp trick.
3) Periodic lookup. solve() precomputes Grundy values up to \(1200\). For \(n \le 100\) it reads the exact value; for \(n > 100\) it maps \(n\) back into the verified period window.
4) Counting winners. The final loop tests whether the selected Grundy value is nonzero and increments the answer. Because the code still scans all lengths \(1\) through \(N\), the final counting phase is linear in \(N\), even though each lookup itself is constant time.
If \(P\) is the precomputed prefix length, the Grundy table costs about \(O(P^2)\), because each \(g(n)\) scans \(O(n)\) split points. In the actual program \(P=1200\), so this stage is tiny. The final counting pass is \(O(N)\) for the requested limit \(N=10^6\). Memory usage is \(O(P)\).
Wir spielen auf einem Papierstreifen der Länge \(n\). Ein Zug entfernt zwei benachbarte Felder; dadurch zerfällt der Rest in einen linken und einen rechten Teilstreifen. Gesucht ist die Anzahl der Längen \(1 \le n \le 10^6\), für die der Startspieler eine Gewinnstrategie besitzt.
Wird der Domino auf den Positionen \(\ell+1\) und \(\ell+2\) entfernt, bleiben zwei unabhängige Teilspiele der Längen
$$\ell \quad \text{und} \quad n-2-\ell.$$
Da sich die beiden Seiten danach nicht mehr beeinflussen, handelt es sich um eine disjunkte Summe kleinerer Spiele. Genau dafür ist die Sprague-Grundy-Theorie gemacht.
Sei \(g(n)\) die Grundy-Zahl eines Streifens der Länge \(n\). Für \(n=0\) und \(n=1\) gibt es keinen Zug, also
$$g(0)=0,\qquad g(1)=0.$$
Für \(n \ge 2\) liefert jeder Zug das xor zweier kleinerer Grundy-Zahlen. Daher gilt
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
mex ist die kleinste nichtnegative ganze Zahl, die in der erreichbaren Wertemenge nicht vorkommt.
Die Aufspaltungen \((\ell,n-2-\ell)\) und \((n-2-\ell,\ell)\) liefern denselben xor-Wert, weil xor kommutativ ist:
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
Darum genügt es, nur die Hälfte der möglichen Trennstellen zu betrachten. Das spart Arbeit, ohne die Menge der erreichbaren Werte zu verändern.
Die ersten Fälle zeigen die Struktur bereits deutlich.
Für \(n=2\) gibt es nur den Zug nach \((0,0)\), also ist die erreichbare Menge \(\{0\}\), damit
$$g(2)=\operatorname{mex}\{0\}=1.$$
Für \(n=4\) sind die verschiedenen Aufspaltungen \((0,2)\) und \((1,1)\). Also
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
und somit
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
Für \(n=5\) bleiben nur \((0,3)\) und \((1,2)\), beide mit xor-Wert \(1\). Deshalb
$$g(5)=\operatorname{mex}\{1\}=0.$$
Länge \(5\) ist also eine Verlustposition.
Eine Position ist genau dann verloren, wenn ihre Grundy-Zahl \(0\) ist. Also ist \(n\) genau dann gewinnend, wenn
$$g(n)\neq 0.$$
Das berechnete Präfix beginnt mit
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
Die ersten Verlustlängen sind damit
$$1,5,9,15,\dots$$
Unter \(1 \le n \le 5\) sind genau \(2,3,4\) Gewinnpositionen. Das passt zum Checkpoint
$$\texttt{solve(5)}=3.$$
Zusätzlich prüft der Quellcode
$$\texttt{solve(50)}=40.$$
Bei vielen endlichen Aufspaltungsspielen wird die Grundy-Folge ab einem gewissen Punkt periodisch; genau dieses Verhalten tritt hier auf. Die Implementierung beweist die Periodizität nicht abstrakt, sondern berechnet ein langes Präfix und verifiziert dann die Beziehung
$$g(n)=g(100+((n-100)\bmod 34))$$
für alle
$$100 \le n \le 1200.$$
Erst nach dieser Kontrolle verwendet das Programm die Periode \(34\) für große Längen. Es handelt sich also um eine im Code überprüfte empirische Periodizität.
1) Präfixberechnung. compute_grundy(n) erzeugt die Tabelle \(g(0),g(1),\dots,g(n)\) aufsteigend.
2) Schnelles mex per Zeitstempel. Statt ein Marker-Array für jede Länge neu zu löschen, speichert der Code seen[value] = length. Ein Wert gehört genau dann zur aktuellen mex-Menge, wenn seen[value] == length gilt.
3) Periodisches Nachschlagen. solve() rechnet bis \(1200\) vor. Für \(n \le 100\) nimmt es den exakten Wert, für \(n > 100\) den per Periode zurückgefalteten Wert.
4) Gewinnersumme. Danach werden alle Längen \(1\) bis \(N\) durchlaufen und gezählt, falls die zugeordnete Grundy-Zahl ungleich \(0\) ist. Der Lookup ist konstant schnell, aber das Zählen selbst bleibt linear in \(N\).
Ist \(P\) die Länge des vorberechneten Präfixes, dann kostet die Grundy-Tabelle ungefähr \(O(P^2)\), weil jede Länge \(n\) etwa \(O(n)\) Aufspaltungen prüft. Im echten Programm ist \(P=1200\), also klein. Die abschließende Zählphase kostet \(O(N)\) für \(N=10^6\). Der Speicherbedarf ist \(O(P)\).
Uzunluğu \(n\) olan bir kâğıt şeritte her hamle yan yana iki hücreyi siler. Böylece kalan kısım solda ve sağda iki bağımsız alt oyuna ayrılır. Soru, \(1 \le n \le 10^6\) için başlangıç oyuncusunun kazanabildiği uzunlukların sayısını istemektedir.
\(\ell+1\) ve \(\ell+2\) konumlarındaki domino kaldırıldığında kalan parçalar şu uzunluklara sahiptir:
$$\ell \quad \text{ve} \quad n-2-\ell.$$
Bu iki taraf artık birbirini etkilemez. Dolayısıyla yeni durum, iki küçük oyunun ayrık toplamıdır ve Sprague-Grundy teoremi doğrudan uygulanır.
Uzunluğu \(n\) olan şeridin Grundy sayısını \(g(n)\) ile gösterelim. Boş şerit ve uzunluğu \(1\) olan şeritte hamle yoktur, yani
$$g(0)=0,\qquad g(1)=0.$$
\(n \ge 2\) için her hamle iki alt oyunun xor'unu verir:
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
Buradaki mex, ulaşılan değerler arasında bulunmayan en küçük negatif olmayan tamsayıdır.
\((\ell,n-2-\ell)\) bölmesi ile ters yöndeki \((n-2-\ell,\ell)\) bölmesi aynı xor değerini üretir, çünkü xor değişme özelliğine sahiptir:
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
Bu yüzden implementasyon yalnızca \(\ell \le n-2-\ell\) koşuluna kadar gider. Böylece aynı hamle tipi iki kez sayılmaz.
İlk birkaç değer mekanizmayı açıkça gösterir.
\(n=2\) için tek hamle \((0,0)\) bırakır. Erişilebilir küme \(\{0\}\) olduğu için
$$g(2)=\operatorname{mex}\{0\}=1.$$
\(n=4\) için farklı bölmeler \((0,2)\) ve \((1,1)\) olur:
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
dolayısıyla
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
\(n=5\) için farklı bölmeler \((0,3)\) ve \((1,2)\)'dir; ikisi de xor olarak \(1\) verir. Bu nedenle
$$g(5)=\operatorname{mex}\{1\}=0.$$
Yani uzunluk \(5\) kaybeden durumdur.
Bir durum tam ve ancak Grundy sayısı sıfırsa kaybedendir. O hâlde uzunluk \(n\) için başlangıç oyuncusu şu koşulda kazanır:
$$g(n)\neq 0.$$
Hesaplanan başlangıç bloğu şöyledir:
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
Buna göre ilk kaybeden uzunluklar
$$1,5,9,15,\dots$$
olur. \(1 \le n \le 5\) aralığında kazananlar yalnızca \(2,3,4\) olduğu için
$$\texttt{solve(5)}=3$$
kontrolü doğrudur. Kod ayrıca
$$\texttt{solve(50)}=40$$
değerini de test eder.
Birçok sonlu split game'de Grundy dizisi bir eşiğin ardından periyodikleşir; bu oyunda da aynısı olur. Program bunu soyut bir ispatla değil, uzun bir prefix hesaplayıp şu deseni doğrulayarak kullanır:
$$g(n)=g(100+((n-100)\bmod 34)).$$
Bu eşitlik
$$100 \le n \le 1200$$
aralığındaki tüm değerler için kontrol edilir. Doğrulamadan sonra aynı periyot bloğu büyük \(n\) değerleri için tekrar kullanılır. Dolayısıyla burada kullanılan şey kör bir tahmin değil, kod tarafından sınanmış bir periodik davranıştır.
1) Prefix hesaplama. compute_grundy(n) fonksiyonu \(g(0),g(1),\dots,g(n)\) tablosunu küçükten büyüğe kurar.
2) Zaman damgalı mex. Her adımda yardımcı diziyi sıfırlamak yerine seen[value] = length atanır. Böylece bir xor değerinin mevcut uzunluk için görülüp görülmediği yalnızca seen[value] == length testiyle anlaşılır.
3) Periyodik lookup. solve() önce \(1200\)'e kadar Grundy sayıları hesaplar. \(n \le 100\) için doğrudan tabloyu, \(n > 100\) için ise periyot penceresine geri katlanmış indeksi kullanır.
4) Kazanan sayımı. Son döngü \(1\)'den \(N\)'ye kadar tüm uzunlukları gezer ve seçilen Grundy değeri sıfır değilse cevabı bir artırır. Yani tek tek lookup sabit zamanda yapılsa da toplam sayım aşaması yine \(O(N)\)'dir.
Önhesap uzunluğunu \(P\) ile gösterirsek Grundy tablosunun maliyeti yaklaşık \(O(P^2)\)'dir; çünkü her \(g(n)\), \(O(n)\) farklı bölmeyi inceler. Gerçek programda \(P=1200\) olduğu için bu kısım küçüktür. Son sayım turu \(N=10^6\) için \(O(N)\) sürer. Bellek kullanımı \(O(P)\)'dir.
Se juega sobre una tira de longitud \(n\). Cada jugada elimina dos celdas adyacentes, de modo que la tira se divide en una parte izquierda y otra derecha. La pregunta es cuántas longitudes \(1 \le n \le 10^6\) son ganadoras para el jugador inicial.
Si quitamos el dominó que cubre las posiciones \(\ell+1\) y \(\ell+2\), quedan dos subjuegos independientes de longitudes
$$\ell \quad \text{y} \quad n-2-\ell.$$
Como ambos lados ya no interactúan, la nueva posición es la suma disjunta de dos juegos menores. Por eso encaja exactamente en la teoría de Sprague-Grundy.
Sea \(g(n)\) el número de Grundy de una tira de longitud \(n\). Las posiciones de longitud \(0\) y \(1\) no tienen movimientos legales, así que
$$g(0)=0,\qquad g(1)=0.$$
Para \(n \ge 2\), cada movimiento produce el xor de dos posiciones más pequeñas:
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
El operador mex devuelve el menor entero no negativo que no aparece entre los valores alcanzables.
Las particiones \((\ell,n-2-\ell)\) y \((n-2-\ell,\ell)\) producen el mismo xor, porque xor es conmutativo:
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
Por eso basta iterar mientras \(\ell \le n-2-\ell\). Así se evita trabajo duplicado sin cambiar el conjunto de opciones alcanzables.
Los primeros valores muestran bien la idea.
Para \(n=2\), el único movimiento deja \((0,0)\), luego el conjunto alcanzable es \(\{0\}\) y
$$g(2)=\operatorname{mex}\{0\}=1.$$
Para \(n=4\), las particiones distintas son \((0,2)\) y \((1,1)\), así que
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
y por tanto
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
Para \(n=5\), las particiones distintas son \((0,3)\) y \((1,2)\), y ambas dan xor igual a \(1\). Entonces
$$g(5)=\operatorname{mex}\{1\}=0.$$
Así, la longitud \(5\) es perdedora.
Una posición es perdedora exactamente cuando su número de Grundy vale \(0\). En consecuencia, una longitud \(n\) es ganadora si y solo si
$$g(n)\neq 0.$$
El prefijo calculado empieza con
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
Por tanto, las primeras longitudes perdedoras son
$$1,5,9,15,\dots$$
y en el intervalo \(1 \le n \le 5\) las ganadoras son \(2,3,4\). Eso coincide con el checkpoint
$$\texttt{solve(5)}=3.$$
El código también valida
$$\texttt{solve(50)}=40.$$
En muchos juegos finitos de partición la sucesión de Grundy acaba volviéndose periódica, y aquí ocurre lo mismo. La implementación no lo demuestra desde teoría abstracta; en su lugar calcula un prefijo largo y comprueba el patrón
$$g(n)=g(100+((n-100)\bmod 34))$$
para todos los valores con
$$100 \le n \le 1200.$$
Solo después de esa verificación reutiliza el bloque de periodo \(34\) para contar hasta \(10^6\). Es decir, el programa se apoya en una periodicidad observada y comprobada, no en una conjetura sin revisar.
1) Cálculo del prefijo. compute_grundy(n) construye \(g(0),g(1),\dots,g(n)\) en orden creciente.
2) mex rápido con marcas temporales. En vez de limpiar un arreglo auxiliar en cada longitud, el programa guarda seen[value] = length. Entonces un valor pertenece al conjunto actual exactamente cuando seen[value] == length.
3) Consulta periódica. solve() precomputa hasta \(1200\). Si \(n \le 100\), usa el valor exacto; si \(n > 100\), repliega \(n\) dentro de la ventana periódica verificada.
4) Conteo final. Luego recorre todas las longitudes de \(1\) a \(N\) y suma una unidad si el valor de Grundy correspondiente es no nulo. El acceso es \(O(1)\), pero el conteo total sigue siendo lineal en \(N\).
Si \(P\) es el tamaño del prefijo precalculado, la tabla de Grundy cuesta aproximadamente \(O(P^2)\), porque cada \(g(n)\) examina \(O(n)\) cortes. En el programa real \(P=1200\), así que esa fase es pequeña. El conteo final cuesta \(O(N)\) para \(N=10^6\). La memoria es \(O(P)\).
我们在长度为 \(n\) 的纸条上玩游戏。每一步删除两个相邻格子，于是剩余部分被分成左、右两个独立子局。题目要求统计在 \(1 \le n \le 10^6\) 中，先手必胜的长度有多少个。
如果删除覆盖位置 \(\ell+1\) 和 \(\ell+2\) 的那一块，剩下的就是两个长度分别为
$$\ell \quad \text{和} \quad n-2-\ell$$
的独立纸条。两边之后互不影响，所以新局面就是两个小博弈的直和，这正是 Sprague-Grundy 理论的标准场景。
记长度为 \(n\) 的纸条的 Grundy 数为 \(g(n)\)。空纸条和长度 \(1\) 的纸条都没有合法操作，因此
$$g(0)=0,\qquad g(1)=0.$$
当 \(n \ge 2\) 时，每个合法操作都会产生两个更小局面的 xor，所以
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
这里的 mex 表示“没有出现过的最小非负整数”。
拆分 \((\ell,n-2-\ell)\) 与镜像拆分 \((n-2-\ell,\ell)\) 得到同一个 xor 值，因为 xor 满足交换律：
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
因此程序只需要枚举满足 \(\ell \le n-2-\ell\) 的一半拆分位置，就能得到完整的可达集合。
前几个值已经能看清整个机制。
对 \(n=2\)，唯一操作留下 \((0,0)\)，可达集合是 \(\{0\}\)，所以
$$g(2)=\operatorname{mex}\{0\}=1.$$
对 \(n=4\)，不同拆分为 \((0,2)\) 和 \((1,1)\)，因此
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
从而
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
对 \(n=5\)，不同拆分是 \((0,3)\) 和 \((1,2)\)，两者的 xor 都等于 \(1\)。于是
$$g(5)=\operatorname{mex}\{1\}=0.$$
也就是说长度 \(5\) 是必败态。
一个局面恰好在 Grundy 数为 \(0\) 时是必败态。因此长度 \(n\) 必胜，当且仅当
$$g(n)\neq 0.$$
程序算出的前缀开头为
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
所以最早的必败长度是
$$1,5,9,15,\dots$$
在 \(1 \le n \le 5\) 中，必胜的只有 \(2,3,4\)，这正好对应检查值
$$\texttt{solve(5)}=3.$$
源码还验证了
$$\texttt{solve(50)}=40.$$
很多有限拆分博弈的 Grundy 序列在足够长之后会进入周期，这个游戏也是如此。实现并没有从纯理论上证明这一点，而是先计算一个较长前缀，再检查下面的关系：
$$g(n)=g(100+((n-100)\bmod 34))$$
对所有
$$100 \le n \le 1200$$
都成立。只有通过这一步检查后，程序才把周期 \(34\) 用到更大的 \(n\) 上。因此这里依赖的是“已经验证过的经验周期”，不是未经检验的猜测。
1) 计算前缀。 compute_grundy(n) 按从小到大的顺序构造 \(g(0),g(1),\dots,g(n)\)。
2) 用时间戳技巧做 mex。 程序不在每个长度上清空辅助数组，而是记录 seen[value] = length。这样只要检查 seen[value] == length，就知道该 xor 值是否在当前长度的可达集合中出现过。
3) 周期映射。 solve() 先把 Grundy 值算到 \(1200\)。若 \(n \le 100\)，直接读取精确值；若 \(n > 100\)，就把 \(n\) 映射回已经验证过的周期窗口。
4) 统计答案。 最后程序仍然逐个扫描 \(1\) 到 \(N\) 的所有长度，只要对应 Grundy 值非零就把答案加一。所以单次查值是 \(O(1)\)，但总计数阶段仍是 \(O(N)\)。
设预计算前缀长度为 \(P\)，那么 Grundy 表的成本约为 \(O(P^2)\)，因为每个 \(g(n)\) 要检查 \(O(n)\) 个拆分位置。实际程序里 \(P=1200\)，这部分很小。最后统计 \(N=10^6\) 的答案需要 \(O(N)\) 时间，空间复杂度为 \(O(P)\)。
Игра ведется на полоске длины \(n\). За один ход удаляются две соседние клетки, после чего позиция распадается на левую и правую независимые части. Требуется посчитать, для скольких длин \(1 \le n \le 10^6\) стартовый игрок имеет выигрышную стратегию.
Если удалить домино, покрывающее клетки \(\ell+1\) и \(\ell+2\), то остаются две независимые полоски длины
$$\ell \quad \text{и} \quad n-2-\ell.$$
После такого хода левая и правая части больше не взаимодействуют, значит новая позиция является дизъюнктной суммой двух меньших игр. Именно к таким позициям применяется теория Шпрэге-Гранди.
Пусть \(g(n)\) обозначает число Гранди для полоски длины \(n\). Для \(n=0\) и \(n=1\) хода нет, поэтому
$$g(0)=0,\qquad g(1)=0.$$
При \(n \ge 2\) любой ход дает xor двух меньших чисел Гранди:
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
Здесь mex означает наименьшее неотрицательное число, отсутствующее среди достижимых значений.
Разбиение \((\ell,n-2-\ell)\) и зеркальное разбиение \((n-2-\ell,\ell)\) дают одинаковый xor, поскольку xor коммутативен:
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
Поэтому код итерируется лишь до середины, не теряя ни одного достижимого значения.
Первые значения уже показывают всю механику.
Для \(n=2\) единственный ход оставляет \((0,0)\), значит достижимое множество равно \(\{0\}\), и потому
$$g(2)=\operatorname{mex}\{0\}=1.$$
Для \(n=4\) различные разбиения: \((0,2)\) и \((1,1)\), следовательно
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
и значит
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
Для \(n=5\) остаются \((0,3)\) и \((1,2)\); оба дают xor, равный \(1\). Поэтому
$$g(5)=\operatorname{mex}\{1\}=0.$$
То есть длина \(5\) является проигрышной.
Позиция проигрышна тогда и только тогда, когда ее число Гранди равно нулю. Значит длина \(n\) выигрышна ровно при условии
$$g(n)\neq 0.$$
Начало вычисленной последовательности таково:
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
Первые проигрышные длины:
$$1,5,9,15,\dots$$
Среди \(1 \le n \le 5\) выигрышны только \(2,3,4\), что совпадает с контрольным значением
$$\texttt{solve(5)}=3.$$
В исходниках также проверяется
$$\texttt{solve(50)}=40.$$
Для многих конечных игр с расщеплением последовательность Гранди со временем становится периодической; здесь наблюдается именно это. Реализация не доказывает периодичность теоретически, а вычисляет длинный префикс и проверяет соотношение
$$g(n)=g(100+((n-100)\bmod 34))$$
для всех
$$100 \le n \le 1200.$$
Только после этой проверки программа использует период \(34\) для больших длин. Иными словами, она опирается на проверенный шаблон, а не на непроверенное предположение.
1) Построение префикса. compute_grundy(n) последовательно строит таблицу \(g(0),g(1),\dots,g(n)\).
2) Быстрый mex через метки времени. Вместо очистки вспомогательного массива на каждой длине код записывает seen[value] = length. Тогда значение принадлежит текущему достижимому множеству тогда и только тогда, когда seen[value] == length.
3) Периодический доступ. solve() предварительно считает значения до \(1200\). Для \(n \le 100\) берется точное значение, а для \(n > 100\) индекс сворачивается назад в подтвержденное периодическое окно.
4) Финальный подсчет. Затем программа все равно проходит по всем длинам от \(1\) до \(N\) и увеличивает ответ, если соответствующее число Гранди отлично от нуля. Поэтому отдельный доступ имеет стоимость \(O(1)\), но весь этап подсчета остается линейным по \(N\).
Если \(P\) обозначает длину предварительно вычисляемого префикса, то построение таблицы Гранди стоит примерно \(O(P^2)\), потому что для каждого \(g(n)\) проверяется \(O(n)\) разбиений. В реальной программе \(P=1200\), так что эта часть мала. Финальный подсчет для \(N=10^6\) стоит \(O(N)\). Память: \(O(P)\).
نلعب على شريط طوله \(n\). في كل حركة نحذف خليتين متجاورتين، فينقسم الشريط الباقي إلى جزء أيسر وجزء أيمن مستقلين تمامًا. المطلوب هو عدد الأطوال \(1 \le n \le 10^6\) التي يملك فيها اللاعب الأول استراتيجية فوز.
إذا حذفنا القطعة التي تغطي الموضعين \(\ell+1\) و\(\ell+2\)، فإن ما يبقى هو شريطان مستقلان بطولي
$$\ell \quad \text{و} \quad n-2-\ell.$$
بما أن الجانبين لا يتفاعلان بعد ذلك، فالوضع الجديد هو مجموع منفصل للعبتين أصغر. وهذا هو الإطار القياسي لنظرية Sprague-Grundy.
لنرمز إلى عدد Grundy للشريط ذي الطول \(n\) بالرمز \(g(n)\). الشريط الفارغ والشريط ذو الطول \(1\) لا يحتويان على أي حركة قانونية، لذلك
$$g(0)=0,\qquad g(1)=0.$$
ولكل \(n \ge 2\)، كل حركة تعطي xor لعددين أصغر، ومن ثم
$$g(n)=\operatorname{mex}\{g(\ell)\oplus g(n-2-\ell): 0\le \ell \le n-2\}.$$
العامل mex يعني أصغر عدد صحيح غير سالب لا يظهر داخل مجموعة القيم الممكن الوصول إليها.
التقسيم \((\ell,n-2-\ell)\) والتقسيم المعكوس \((n-2-\ell,\ell)\) يعطيان قيمة xor نفسها، لأن xor تبادلي:
$$g(\ell)\oplus g(n-2-\ell)=g(n-2-\ell)\oplus g(\ell).$$
لذلك يكفي أن يمر الكود على الحالات التي تحقق \(\ell \le n-2-\ell\)، وبذلك يتجنب التكرار من دون أن يفقد أي نتيجة ممكنة.
أول القيم تكشف الفكرة كاملة.
عند \(n=2\)، الحركة الوحيدة تترك \((0,0)\)، إذًا مجموعة القيم الممكنة هي \(\{0\}\)، وبالتالي
$$g(2)=\operatorname{mex}\{0\}=1.$$
وعند \(n=4\)، تكون التقسيمات المختلفة هي \((0,2)\) و\((1,1)\)، ومن ثم
$$\{g(0)\oplus g(2),\ g(1)\oplus g(1)\}=\{1,0\},$$
ولذلك
$$g(4)=\operatorname{mex}\{0,1\}=2.$$
أما عند \(n=5\)، فالتقسيمان المختلفان هما \((0,3)\) و\((1,2)\)، وكلاهما يعطي xor يساوي \(1\). إذًا
$$g(5)=\operatorname{mex}\{1\}=0.$$
وهذا يعني أن الطول \(5\) وضع خاسر.
الوضع يكون خاسرًا بالضبط عندما يكون عدد Grundy مساويًا للصفر. لذلك يكون الطول \(n\) رابحًا إذا وفقط إذا
$$g(n)\neq 0.$$
وبداية المتتالية المحسوبة هي
$$g(1..10)=(0,1,1,2,0,3,1,1,0,3).$$
إذن أول الأطوال الخاسرة هي
$$1,5,9,15,\dots$$
وفي المجال \(1 \le n \le 5\) تكون الأطوال الرابحة هي فقط \(2,3,4\)، وهذا يطابق نقطة الفحص
$$\texttt{solve(5)}=3.$$
كما يتحقق الكود أيضًا من أن
$$\texttt{solve(50)}=40.$$
في كثير من ألعاب التقسيم المنتهية تصبح متتالية Grundy دورية بعد حد معين، وهذه اللعبة تُظهر السلوك نفسه. التنفيذ لا يثبت ذلك نظريًا من الصفر، بل يحسب مقطعًا ابتدائيًا طويلًا ثم يفحص العلاقة
$$g(n)=g(100+((n-100)\bmod 34))$$
لكل
$$100 \le n \le 1200.$$
بعد نجاح هذا الفحص فقط يستعمل البرنامج الدورة \(34\) للأطوال الأكبر. أي أن الحل يعتمد على دورية مُشاهَدة ومتحقق منها داخل الكود، لا على تخمين غير مفحوص.
1) بناء المقطع الابتدائي. الدالة compute_grundy(n) تبني الجدول \(g(0),g(1),\dots,g(n)\) تصاعديًا.
2) حساب mex بخدعة الطابع الزمني. بدل تصفير مصفوفة مساعدة في كل مرة، يسجل الكود seen[value] = length. وعندها نعرف أن قيمة xor ظهرت في الطول الحالي إذا وفقط إذا كان seen[value] == length.
3) الفهرسة الدورية. في solve() تُحسب قيم Grundy حتى \(1200\). إذا كان \(n \le 100\) تُؤخذ القيمة الدقيقة، وإذا كان \(n > 100\) يُعاد إسقاط \(n\) داخل نافذة الدورية التي تم التحقق منها.
4) عدّ الأطوال الرابحة. بعد ذلك يمر البرنامج على جميع الأطوال من \(1\) إلى \(N\)، ويزيد الجواب عندما تكون قيمة Grundy المختارة غير صفرية. لذلك فالوصول إلى القيمة نفسها ثابت الزمن، لكن مرحلة العد كاملة ما زالت \(O(N)\).
إذا كان \(P\) هو طول المقطع الابتدائي المحسوب، فإن بناء جدول Grundy يكلف تقريبًا \(O(P^2)\)، لأن كل \(g(n)\) يفحص نحو \(O(n)\) أماكن قطع. في البرنامج الفعلي لدينا \(P=1200\)، لذا فهذه المرحلة صغيرة. أما العد النهائي حتى \(N=10^6\) فيكلف \(O(N)\). الذاكرة المطلوبة هي \(O(P)\).