We study an impartial heap game in which a heap of size \(n\) may be changed in two ways: remove \(1\), \(2\), \(4\), or \(9\) counters, or split the heap into two positive heaps whose sizes add up to \(n\). For the large parameters \(N=12{,}491{,}249\) and \(m=1249\), the required quantity \(S(N,m)\) is the number of size-\(m\) multisets of heap sizes chosen from \(\{1,2,\dots,N\}\) whose combined position is losing, taken modulo \(912491249\).
By the Sprague-Grundy theorem, a disjoint sum of heaps is losing exactly when the xor of the single-heap Grundy values is \(0\). The whole problem therefore becomes: compute the Grundy value \(g(n)\) for one heap, understand how often each Grundy value appears among \(1\le n\le N\), and count size-\(m\) multisets whose xor is zero.
The implementations combine game theory, eventual periodicity, and a compact xor dynamic program. The key point is that the huge bound \(N\) is handled through periodic structure, not by computing every \(g(n)\) all the way to \(N\).
Let \(g(n)\) be the Grundy value of one heap of size \(n\). Then \(g(0)=0\), and for \(n\ge 1\) every legal move contributes one reachable Grundy value. The subtraction moves contribute \(g(n-1)\), \(g(n-2)\), \(g(n-4)\), and \(g(n-9)\) whenever the index is nonnegative. A split \(n=a+(n-a)\) contributes the xor \(g(a)\oplus g(n-a)\).
Therefore
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
The upper limit \(\lfloor n/2\rfloor\) is enough because the split \(a,n-a\) is the same position as \(n-a,a\). Computing the first values gives
$$g(1..10)=1,2,0,3,4,6,1,2,5,3.$$
These initial values already show that the sequence is nontrivial: subtraction moves alone would be much simpler, but the split move injects xor structure into the recurrence.
The implementations do not try to prove a closed form for \(g(n)\). Instead they compute a long prefix and then look for eventual periodicity separately in the even and odd subsequences
$$e_k=g(2k),\qquad o_k=g(2k-1).$$
This parity split is exactly what works in practice. The computed data show that the even subsequence becomes periodic with period \(79\) after the first \(22\) even terms, while the odd subsequence becomes periodic with period \(70\) after the first \(161\) odd terms.
If \(c_r(N)\) denotes the number of heap sizes \(n\in[1,N]\) with Grundy value \(r\), then
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
For each parity subsequence, once a preperiod and a period are known, the count of any value \(r\) among the first \(T\) terms is obtained by prefix plus whole cycles plus a short tail. That turns the enormous value \(N=12{,}491{,}249\) into a straightforward counting exercise.
After periodic counting, all heap sizes are grouped only by their Grundy value. Let
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
Now consider one fixed class \(r\). There are \(c_r\) distinct heap sizes inside this class, and the game position allows repeated heap sizes, so choosing exactly \(k\) heaps from that class is a multiset-counting problem. The number of possibilities is
$$\binom{c_r+k-1}{k}.$$
This is the usual combinations-with-repetition formula, equivalently the coefficient of \(z^k\) in
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$$
The xor contribution of those \(k\) heaps is especially simple: since \(r\oplus r=0\), the total xor from class \(r\) is \(0\) when \(k\) is even and \(r\) when \(k\) is odd.
Process the Grundy classes one by one. Let \(DP[\xi][t]\) be the number of ways to choose \(t\) heaps from the classes processed so far so that the current xor is \(\xi\). Initially, before any class is used,
$$DP[0][0]=1.$$
When the class \(r\) is added, choosing \(k\) heaps from it changes the count by \(k\) and changes the xor only according to the parity of \(k\). Thus the transition is
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{for even }k,$$
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{for odd }k.$$
After every Grundy class has been processed, the answer is
$$S(N,m)=DP[0][m]\pmod{912491249}.$$
The computed prefix shows that only Grundy values \(0\) through \(10\) occur, so the xor state space has size \(16\), which keeps the dynamic program compact.
Using the first ten Grundy values
$$g(1..10)=1,2,0,3,4,6,1,2,5,3,$$
the class counts are
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$$
With exactly two heaps, the total xor is \(0\) precisely when both chosen heaps come from the same Grundy class. So
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
This matches the dynamic-program interpretation perfectly: every class contributes its even-sized selections to xor \(0\), and for \(m=2\) that means selecting two heaps from one class.
The implementation first computes a prefix of the Grundy sequence up to \(20000\). For each heap size it gathers all reachable Grundy values into a bit mask and then takes the mex. That gives both the sequence itself and the maximum Grundy value appearing in the prefix.
Next it extracts the even-indexed and odd-indexed subsequences and searches for a short period in each one. Candidate periods up to \(300\) are tested, the tail is required to contain at least six consecutive repetitions, and then the start is moved left to the earliest index where the same period still works. In the final data this yields period \(79\) starting after \(22\) even terms and period \(70\) starting after \(161\) odd terms.
Using those periodic descriptions, the implementation counts how many times each Grundy value occurs in \(\{1,\dots,N\}\). For each class size \(c_r\), it then builds the coefficients \(\binom{c_r+k-1}{k}\bmod 912491249\) for \(0\le k\le m\). The coefficients are split into even-\(k\) and odd-\(k\) lists so that the xor update is just “stay in the same mask” or “toggle by \(r\)”.
Finally, a rolling two-layer dynamic program over xor masks and selected-heap count is executed. Since the observed Grundy values lie in \(0,\dots,10\), only \(16\) xor masks are needed, and the answer is the entry with xor \(0\) and total size \(1249\).
Let \(M=20000\) be the precomputation cutoff, let \(R\) be the number of Grundy classes actually used, and let \(X\) be the number of xor masks. The Grundy prefix computation costs
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$$
time, because every \(n\) checks all splits up to \(n/2\), and it uses \(O(M)\) memory for the stored sequence. The period search over the even and odd subsequences is much smaller and is negligible compared with the quadratic prefix build.
The counting stage after periodic compression is linear in the period lengths. The main combinatorial stage uses a dynamic program of size \(X\times (m+1)\), updated for each class over all \(k\le m\), so its running time is \(O(RXm^2)\) and its memory use is \(O(Xm)\). In this problem \(R=11\) and \(X=16\), so the practical bottleneck is the one-time Grundy precomputation, not the final xor DP.
Betrachtet wird ein unparteiisches Haufenspiel. Aus einem Haufen der Größe \(n\) darf man entweder \(1\), \(2\), \(4\) oder \(9\) Steine entfernen oder den Haufen in zwei positive Teilhaufen zerlegen, deren Summe \(n\) ist. Für \(N=12{,}491{,}249\) und \(m=1249\) zählt die gesuchte Größe \(S(N,m)\) die Anzahl der Multimengen aus genau \(m\) Haufengrößen aus \(\{1,2,\dots,N\}\), deren Gesamtstellung verloren ist, modulo \(912491249\).
Nach dem Sprague-Grundy-Theorem ist eine Summe unabhängiger Haufen genau dann verloren, wenn das xor ihrer Einzel-Grundywerte \(0\) ist. Deshalb zerfällt die Aufgabe in drei Teile: die Folge \(g(n)\) für einen einzelnen Haufen berechnen, die Häufigkeit jeder Grundyklasse bis \(N\) bestimmen und anschließend alle Multimengen der Größe \(m\) mit xor \(0\) zählen.
Die Implementierungen verbinden Spieltheorie, periodisches Verhalten und eine kompakte xor-Dynamik. Der große Parameter \(N\) wird nicht durch vollständiges Ausrechnen bis \(N\) bewältigt, sondern durch eine erkannte Periodenstruktur.
Sei \(g(n)\) der Grundywert eines einzelnen Haufens der Größe \(n\). Dann gilt \(g(0)=0\). Für \(n\ge 1\) sammeln wir alle per Zug erreichbaren Grundywerte. Die Abzüge liefern \(g(n-1)\), \(g(n-2)\), \(g(n-4)\) und \(g(n-9)\), sofern der Index nicht negativ wird. Eine Zerlegung \(n=a+(n-a)\) liefert den xor-Wert \(g(a)\oplus g(n-a)\).
Also
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
Die Schranke \(\lfloor n/2\rfloor\) genügt, weil die Zerlegung \(a,n-a\) dieselbe Stellung wie \(n-a,a\) beschreibt. Die ersten Werte sind
$$g(1..10)=1,2,0,3,4,6,1,2,5,3.$$
Schon dieser Anfang zeigt, dass der Spaltzug die Struktur deutlich komplizierter macht als bei einer reinen Subtraktionsvariante.
Die Implementierungen suchen keine geschlossene Formel für \(g(n)\), sondern berechnen zunächst ein langes Präfix und testen dann die beiden Teilfolgen
$$e_k=g(2k),\qquad o_k=g(2k-1)$$
jeweils separat auf periodisches Verhalten. Genau diese Paritätstrennung funktioniert hier. In den berechneten Daten wird die gerade Teilfolge nach \(22\) geraden Termen periodisch mit Periode \(79\), die ungerade Teilfolge nach \(161\) ungeraden Termen mit Periode \(70\).
Bezeichnet \(c_r(N)\) die Anzahl der Haufengrößen \(n\in[1,N]\) mit Grundywert \(r\), dann gilt
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Sobald Vorperiode und Periode bekannt sind, lässt sich die Anzahl eines Werts \(r\) unter den ersten \(T\) Folgengliedern als Präfix plus volle Zyklen plus kurzer Rest berechnen. So wird das riesige \(N=12{,}491{,}249\) auf einfache Arithmetik reduziert.
Nach dieser periodischen Auswertung werden die Haufengrößen nur noch über ihren Grundywert betrachtet. Definiere
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
Fixiere nun eine Klasse \(r\). In ihr liegen \(c_r\) verschiedene Haufengrößen, und gleiche Haufengrößen dürfen mehrfach gewählt werden. Die Anzahl der Möglichkeiten, genau \(k\) Haufen aus dieser Klasse zu wählen, ist daher
$$\binom{c_r+k-1}{k}.$$
Das ist die Standardformel für Kombinationen mit Wiederholung, also der Koeffizient von \(z^k\) in
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$$
Der xor-Beitrag dieser \(k\) Haufen ist besonders einfach: wegen \(r\oplus r=0\) ergibt sich bei geradem \(k\) der Beitrag \(0\), bei ungeradem \(k\) der Beitrag \(r\).
Die Grundyklassen werden nacheinander verarbeitet. Sei \(DP[\xi][t]\) die Anzahl der Möglichkeiten, aus den bisher behandelten Klassen genau \(t\) Haufen mit aktuellem xor \(\xi\) zu wählen. Am Anfang gilt
$$DP[0][0]=1.$$
Beim Hinzufügen der Klasse \(r\) wird für jede Wahl von \(k\) Haufen die Anzahl um \(k\) erhöht, und das xor ändert sich nur gemäß der Parität von \(k\). Die Übergänge lauten daher
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{für gerades }k,$$
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{für ungerades }k.$$
Nach allen Klassen ist die gesuchte Zahl
$$S(N,m)=DP[0][m]\pmod{912491249}.$$
Das berechnete Präfix zeigt, dass nur die Grundywerte \(0\) bis \(10\) auftreten. Daher reichen \(16\) xor-Zustände aus.
Mit
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
erhält man die Klassenhäufigkeiten
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$$
Bei genau zwei Haufen ist das Gesamt-xor genau dann \(0\), wenn beide gewählten Haufen aus derselben Grundyklasse stammen. Also
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
Dieses Beispiel spiegelt die DP-Logik direkt wider: für \(m=2\) trägt jede Klasse nur über ihre geraden Auswahlen zum xor \(0\) bei.
Die Implementierung berechnet zunächst ein Präfix der Grundyfolge bis \(20000\). Für jede Haufengröße werden alle erreichbaren Grundywerte in einer Bitmaske gesammelt; anschließend wird daraus per mex der nächste Wert bestimmt. So erhält man sowohl die Folge selbst als auch den größten im Präfix vorkommenden Grundywert.
Danach werden die geraden und ungeraden Indexfolgen getrennt extrahiert und auf kurze Perioden getestet. Kandidaten \(p\le 300\) werden ausprobiert; das Ende der Folge muss mindestens sechs aufeinanderfolgende Wiederholungen enthalten; anschließend wird der Start so weit wie möglich nach links verschoben. Im Ergebnis erhält man Periode \(79\) ab dem \(22\). geraden Term sowie Periode \(70\) ab dem \(161\). ungeraden Term.
Mit diesen Periodenbeschreibungen zählt die Implementierung, wie oft jeder Grundywert in \(\{1,\dots,N\}\) auftritt. Für jede Klassengröße \(c_r\) werden dann die Koeffizienten \(\binom{c_r+k-1}{k}\bmod 912491249\) für \(0\le k\le m\) erzeugt und in gerade sowie ungerade \(k\) zerlegt, sodass das xor-Update nur noch „Maske bleibt gleich“ oder „Maske wird mit \(r\) getoggelt“ bedeutet.
Zum Schluss läuft eine zweilagige DP über xor-Masken und die gewählte Haufenanzahl. Da nur Grundywerte aus \(0,\dots,10\) vorkommen, genügen \(16\) xor-Masken, und die Antwort ist der Eintrag für xor \(0\) und Gesamtgröße \(1249\).
Sei \(M=20000\) die Präfixlänge, \(R\) die Anzahl der tatsächlich verwendeten Grundyklassen und \(X\) die Anzahl der xor-Masken. Der Aufbau des Grundypräfixes benötigt
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$$
Zeit, weil für jedes \(n\) alle Zerlegungen bis \(n/2\) geprüft werden, und \(O(M)\) Speicher für die Folge. Die Periodensuche auf den geraden und ungeraden Teilfolgen ist deutlich kleiner und fällt gegenüber dieser quadratischen Vorarbeit kaum ins Gewicht.
Nach der Periodenkompression ist das Zählen linear in den Periodenlängen. Die kombinatorische Hauptarbeit steckt in der DP der Größe \(X\times(m+1)\), die für jede Klasse über alle \(k\le m\) aktualisiert wird. Das ergibt \(O(RXm^2)\) Zeit und \(O(Xm)\) Speicher. In diesem Problem sind \(R=11\) und \(X=16\), daher dominiert praktisch die einmalige Grundy-Vorberechnung und nicht die abschließende xor-DP.
Burada tek yığınlı bir yansız oyun incelenir. Boyutu \(n\) olan bir yığından \(1\), \(2\), \(4\) veya \(9\) taş çıkarılabilir ya da yığın toplamları \(n\) olacak biçimde iki pozitif alt yığına bölünebilir. \(N=12{,}491{,}249\) ve \(m=1249\) için istenen \(S(N,m)\) değeri, \(\{1,2,\dots,N\}\) kümesinden seçilen \(m\) elemanlı yığın boyu çoklukları arasında birleşik konumu kaybedenlerin sayısıdır; sonuç \(912491249\) modunda alınır.
Sprague-Grundy teoremine göre bağımsız yığınların toplam konumu, tek tek yığınların Grundy değerlerinin xor'u \(0\) ise kaybedendir. Dolayısıyla problem üç parçaya ayrılır: tek yığın için \(g(n)\) dizisini üretmek, her Grundy değerinin \(1\le n\le N\) aralığında kaç kez göründüğünü bulmak ve xor'u sıfır olan \(m\) elemanlı çoklukları saymak.
Uygulamalar oyun kuramını, sonradan oluşan periyodik yapıyı ve kompakt bir xor dinamik programını birleştirir. Büyük \(N\) değeri, tüm \(g(n)\) değerlerini sonuna kadar yazarak değil, periyot yapısını kullanarak yönetilir.
\(g(n)\), boyutu \(n\) olan tek bir yığının Grundy değeri olsun. O halde \(g(0)=0\). \(n\ge 1\) için her yasal hamle ulaşılabilir bir Grundy değeri üretir. Çıkarma hamleleri, indeks negatif olmadığı sürece \(g(n-1)\), \(g(n-2)\), \(g(n-4)\) ve \(g(n-9)\) değerlerini verir. Bir \(n=a+(n-a)\) bölmesi ise \(g(a)\oplus g(n-a)\) xor değerini verir.
Bu yüzden
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
Üst sınırın \(\lfloor n/2\rfloor\) olması yeterlidir; çünkü \(a,n-a\) bölmesi ile \(n-a,a\) bölmesi aynı konumu verir. İlk değerler
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
şeklindedir. Bu başlangıç bile bölme hamlesinin diziyi sıradan bir çıkarma oyunundan daha zengin hale getirdiğini gösterir.
Uygulamalar \(g(n)\) için kapalı form aramaz. Bunun yerine uzun bir ön ek hesaplanır ve sonra
$$e_k=g(2k),\qquad o_k=g(2k-1)$$
alt dizileri ayrı ayrı periyodiklik açısından incelenir. Bu problemde işe yarayan yapı tam olarak bu parite ayrımıdır. Hesaplanan veriler, çift alt dizinin ilk \(22\) çift terimden sonra periyodu \(79\) olan bir kuyruğa girdiğini, tek alt dizinin ise ilk \(161\) tek terimden sonra periyodu \(70\) olan bir kuyruğa girdiğini gösterir.
\(c_r(N)\), \(1\le n\le N\) aralığında Grundy değeri \(r\) olan yığın boylarının sayısı olsun. O zaman
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Bir parite alt dizisi için ön periyot ve periyot bilindiğinde, ilk \(T\) terim içindeki \(r\) sayısı “ön ek + tam döngüler + kısa kuyruk” biçiminde hesaplanır. Böylece devasa \(N=12{,}491{,}249\) değeri basit sayaç aritmetiğine indirgenir.
Periyodik sayım tamamlandıktan sonra artık yığın boyları yalnızca Grundy değerlerine göre gruplanır. Tanım:
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
Şimdi sabit bir \(r\) sınıfını ele alalım. Bu sınıfta \(c_r\) farklı yığın boyu vardır ve aynı yığın boyunu birden çok kez seçmek serbesttir. Dolayısıyla bu sınıftan tam \(k\) yığın seçmenin sayısı
$$\binom{c_r+k-1}{k}$$
olur. Bu, tekrar izinli kombinasyon formülüdür; eşdeğer olarak
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k$$
serisinde \(z^k\) katsayısıdır. Bu \(k\) seçimin xor katkısı da çok basittir: \(r\oplus r=0\) olduğundan \(k\) çiftse toplam katkı \(0\), \(k\) tekse katkı \(r\) olur.
Grundy sınıfları teker teker işlenir. \(DP[\xi][t]\), şimdiye kadar işlenen sınıflardan toplam \(t\) yığın seçilip mevcut xor değeri \(\xi\) olduğunda elde edilen yol sayısı olsun. Başlangıçta
$$DP[0][0]=1.$$
\(r\) sınıfı eklenince sınıftan \(k\) adet seçim toplam sayıyı \(k\) artırır ve xor'u yalnızca \(k\)'nin paritesine göre değiştirir. Geçişler bu nedenle
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{\(k\) çiftse},$$
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{\(k\) tekse}$$
şeklindedir. Tüm sınıflar işlendiğinde cevap
$$S(N,m)=DP[0][m]\pmod{912491249}$$
olur. Hesaplanan ön ek, yalnızca \(0\) ile \(10\) arasındaki Grundy değerlerinin görüldüğünü gösterir; bu yüzden xor durum uzayı sadece \(16\) maskeden oluşur.
İlk on Grundy değeri
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
olduğundan sınıf sayıları
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1$$
şeklindedir. Tam iki yığın için toplam xor'un \(0\) olması, iki seçimin de aynı Grundy sınıfından gelmesi demektir. Bu nedenle
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
Bu sonuç DP mantığıyla birebir uyumludur: \(m=2\) iken xor \(0\)'a yalnızca sınıf içindeki çift seçimler katkı verir.
Uygulama önce Grundy dizisinin \(20000\)'e kadarki ön ekini hesaplar. Her yığın boyu için ulaşılabilir Grundy değerleri bir bit maskesinde toplanır ve ardından mex alınır. Böylece hem dizi hem de ön ekte görülen en büyük Grundy değeri elde edilir.
Daha sonra çift indeksli ve tek indeksli alt diziler ayrılır ve her biri için kısa periyot aranır. \(300\)'e kadar aday periyotlar denenir; kuyruğun en az altı ardışık tekrar içermesi istenir; sonra başlangıç, aynı periyodun hâlâ geçerli olduğu en erken noktaya çekilir. Sonuç olarak çift alt dizi için başlangıcı \(22\) olan periyot \(79\), tek alt dizi için başlangıcı \(161\) olan periyot \(70\) bulunur.
Bu periyodik açıklama kullanılarak \(\{1,\dots,N\}\) içinde her Grundy değerinin kaç kez geçtiği sayılır. Her sınıf büyüklüğü \(c_r\) için \(0\le k\le m\) aralığında \(\binom{c_r+k-1}{k}\bmod 912491249\) katsayıları oluşturulur ve \(k\)'nin tek/çift olmasına göre iki listeye ayrılır. Böylece xor güncellemesi yalnızca “aynı maskede kal” veya “\(r\) ile xor yap” olur.
Son aşamada xor maskeleri ve seçilen yığın sayısı üzerinde kayan iki katmanlı bir DP çalıştırılır. Görülen Grundy değerleri \(0,\dots,10\) aralığında olduğu için yalnızca \(16\) xor maskesi gerekir; cevap da xor \(0\), toplam boyut \(1249\) hücresidir.
\(M=20000\) ön hesaplama sınırı, \(R\) kullanılan Grundy sınıfı sayısı ve \(X\) xor maskesi sayısı olsun. Grundy ön ekini oluşturmak
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$$
zaman alır; çünkü her \(n\) için \(n/2\)'ye kadar bütün bölmeler denenir. Bellek kullanımı dizi için \(O(M)\)'dir. Çift ve tek alt dizilerde yapılan periyot araması bunun yanında küçüktür ve baskın terim olmaz.
Periyot sıkıştırmasından sonraki sayım, periyot uzunlukları cinsinden doğrusaldır. Asıl kombinatoryal maliyet, her sınıf için tüm \(k\le m\) değerleri üzerinde güncellenen \(X\times(m+1)\) boyutlu DP'dedir. Bu kısım \(O(RXm^2)\) zaman ve \(O(Xm)\) bellek kullanır. Bu problemde \(R=11\) ve \(X=16\) olduğundan pratikte baskın maliyet tek seferlik Grundy ön hesaplamasıdır.
Se estudia un juego imparcial sobre montones. Desde un montón de tamaño \(n\) se puede quitar \(1\), \(2\), \(4\) o \(9\) fichas, o bien partir el montón en dos montones positivos cuya suma sea \(n\). Para \(N=12{,}491{,}249\) y \(m=1249\), la cantidad pedida \(S(N,m)\) es el número de multisets de tamaño \(m\) formados con tamaños de montón de \(\{1,2,\dots,N\}\) cuya posición conjunta es perdedora, todo ello módulo \(912491249\).
Por el teorema de Sprague-Grundy, una suma disjunta de montones es perdedora exactamente cuando el xor de los valores de Grundy de cada montón vale \(0\). Por eso el problema se divide en tres etapas: calcular \(g(n)\) para un solo montón, contar cuántas veces aparece cada valor de Grundy entre \(1\) y \(N\), y finalmente contar los multisets de tamaño \(m\) cuyo xor total es cero.
Las implementaciones combinan teoría de juegos, periodicidad eventual y una programación dinámica compacta sobre xor. El parámetro gigante \(N\) no se maneja extendiendo la sucesión completa hasta \(N\), sino usando la estructura periódica que aparece en sus subsecuencias.
Sea \(g(n)\) el valor de Grundy de un único montón de tamaño \(n\). Entonces \(g(0)=0\). Para \(n\ge 1\), cada jugada legal produce un valor alcanzable. Las jugadas de sustracción aportan \(g(n-1)\), \(g(n-2)\), \(g(n-4)\) y \(g(n-9)\) siempre que el índice sea no negativo. Una partición \(n=a+(n-a)\) aporta el xor \(g(a)\oplus g(n-a)\).
Por tanto,
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
El límite \(\lfloor n/2\rfloor\) basta porque la partición \(a,n-a\) describe la misma posición que \(n-a,a\). Los primeros valores son
$$g(1..10)=1,2,0,3,4,6,1,2,5,3.$$
Incluso este comienzo muestra que la jugada de partir introduce una estructura mucho más rica que la de un simple juego de restas.
Las implementaciones no buscan una fórmula cerrada para \(g(n)\). En su lugar calculan un prefijo largo y luego estudian por separado las subsecuencias
$$e_k=g(2k),\qquad o_k=g(2k-1).$$
Esta separación por paridad es precisamente la que funciona aquí. Los datos calculados muestran que la subsecuencia par se vuelve periódica con período \(79\) después de los primeros \(22\) términos pares, mientras que la subsecuencia impar se vuelve periódica con período \(70\) después de los primeros \(161\) términos impares.
Si \(c_r(N)\) denota el número de tamaños \(n\in[1,N]\) con valor de Grundy \(r\), entonces
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
Una vez conocidos el preperíodo y el período de cada subsecuencia, el número de apariciones de \(r\) entre los primeros \(T\) términos se obtiene como prefijo más ciclos completos más una cola corta. Así, el enorme valor \(N=12{,}491{,}249\) se reduce a una cuenta aritmética muy simple.
Tras el conteo periódico, los tamaños de montón ya solo importan por su valor de Grundy. Definimos
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
Fijemos una clase \(r\). Dentro de ella hay \(c_r\) tamaños distintos y se permite repetir un mismo tamaño, de modo que elegir exactamente \(k\) montones de esta clase es un problema de multisets. El número de posibilidades es
$$\binom{c_r+k-1}{k}.$$
Es la fórmula estándar de combinaciones con repetición, es decir, el coeficiente de \(z^k\) en
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$$
La contribución al xor también es muy simple: como \(r\oplus r=0\), tomar \(k\) montones de la clase \(r\) produce xor \(0\) si \(k\) es par y xor \(r\) si \(k\) es impar.
Las clases de Grundy se procesan una por una. Sea \(DP[\xi][t]\) el número de maneras de elegir \(t\) montones de las clases ya tratadas con xor actual \(\xi\). Inicialmente
$$DP[0][0]=1.$$
Al añadir la clase \(r\), elegir \(k\) montones de esa clase aumenta el total en \(k\) y cambia el xor solo según la paridad de \(k\). Por eso la transición es
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{si \(k\) es par},$$
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{si \(k\) es impar}.$$
Cuando todas las clases han sido procesadas, la respuesta es
$$S(N,m)=DP[0][m]\pmod{912491249}.$$
El prefijo calculado muestra que solo aparecen los valores de Grundy \(0\) a \(10\), por lo que bastan \(16\) máscaras xor.
Con
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
se obtienen las frecuencias
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$$
Con exactamente dos montones, el xor total es \(0\) si y solo si ambos montones provienen de la misma clase de Grundy. Entonces
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
El ejemplo encaja exactamente con la interpretación de la DP: para \(m=2\), solo las elecciones pares dentro de una misma clase contribuyen al xor nulo.
La implementación calcula primero un prefijo de la sucesión de Grundy hasta \(20000\). Para cada tamaño de montón reúne los valores alcanzables en una máscara de bits y luego calcula el mex. De ese modo obtiene tanto la sucesión como el máximo valor de Grundy observado en el prefijo.
Después extrae las subsecuencias de índices pares e impares y busca un período corto en cada una. Se prueban candidatos \(p\le 300\), se exige que la cola contenga al menos seis repeticiones consecutivas, y luego el inicio se desplaza hacia la izquierda todo lo posible. El resultado final es período \(79\) a partir del término par \(22\) y período \(70\) a partir del término impar \(161\).
Con esas descripciones periódicas, la implementación cuenta cuántas veces aparece cada valor de Grundy en \(\{1,\dots,N\}\). Para cada clase de tamaño \(c_r\) construye luego los coeficientes \(\binom{c_r+k-1}{k}\bmod 912491249\) para \(0\le k\le m\), y los separa en listas de \(k\) pares e impares para que la actualización de xor sea simplemente “quedarse en la misma máscara” o “conmutar con \(r\)”.
Por último se ejecuta una DP de dos capas sobre máscaras xor y número total de montones elegidos. Como los valores observados están en \(0,\dots,10\), solo hacen falta \(16\) máscaras xor, y la respuesta es la entrada con xor \(0\) y tamaño total \(1249\).
Sea \(M=20000\) el límite de precomputación, \(R\) el número de clases de Grundy usadas y \(X\) el número de máscaras xor. Construir el prefijo de Grundy cuesta
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$$
tiempo, porque para cada \(n\) se revisan todas las particiones hasta \(n/2\), y usa \(O(M)\) memoria para guardar la sucesión. La búsqueda de períodos en las dos subsecuencias es mucho menor y no domina el coste total.
Tras comprimir con la periodicidad, el conteo de frecuencias es lineal en las longitudes de período. La parte combinatoria principal es una DP de tamaño \(X\times(m+1)\), actualizada para cada clase y para todos los \(k\le m\). Por tanto, su coste es \(O(RXm^2)\) en tiempo y \(O(Xm)\) en memoria. En este problema \(R=11\) y \(X=16\), de modo que en la práctica el paso dominante es la precomputación inicial de Grundy.
这里研究的是一个无偏博弈。对一个大小为 \(n\) 的单堆，可以执行两类操作：移走 \(1\)、\(2\)、\(4\) 或 \(9\) 个石子，或者把这堆分裂成两个正整数大小的子堆，且两堆之和仍为 \(n\)。在参数 \(N=12{,}491{,}249\)、\(m=1249\) 下，要求的 \(S(N,m)\) 是从 \(\{1,2,\dots,N\}\) 中选出 \(m\) 个堆大小所形成的多重集里，所有整体为必败态的局面数目，并对 \(912491249\) 取模。
根据 Sprague-Grundy 定理，若把多个独立堆并在一起考虑，则该复合局面是必败态，当且仅当所有单堆 Grundy 值的 xor 为 \(0\)。因此问题可以分成三步：先求单堆的 Grundy 序列 \(g(n)\)，再统计每个 Grundy 值在 \(1\le n\le N\) 中出现多少次，最后统计大小为 \(m\) 且 xor 为零的多重集数目。
实现采用了组合博弈论、奇偶分裂后的尾部周期性，以及一个很紧凑的 xor 动态规划。超大的 \(N\) 不是靠把 \(g(n)\) 一项项算到 \(N\)，而是靠对序列结构进行压缩。
设 \(g(n)\) 表示大小为 \(n\) 的单堆 Grundy 值。显然 \(g(0)=0\)。对 \(n\ge 1\)，每个合法操作都会给出一个可达 Grundy 值。减法操作对应 \(g(n-1)\)、\(g(n-2)\)、\(g(n-4)\)、\(g(n-9)\)，前提是下标不为负。若把堆分裂成 \(a\) 和 \(n-a\)，则得到的复合局面的 Grundy 值是 \(g(a)\oplus g(n-a)\)。
因此有递推式
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
上界只写到 \(\lfloor n/2\rfloor\) 就足够，因为分裂成 \(a,n-a\) 与分裂成 \(n-a,a\) 是同一个局面。前十项计算结果为
$$g(1..10)=1,2,0,3,4,6,1,2,5,3.$$
这个前缀已经说明：一旦允许分裂，序列结构就不再像普通减法博弈那样直接，而会把 xor 结构嵌入递推中。
实现并没有直接寻找 \(g(n)\) 的闭式公式，而是先计算一个足够长的前缀，再分别研究
$$e_k=g(2k),\qquad o_k=g(2k-1).$$
也就是偶数堆大小和奇数堆大小对应的两条子序列。对这个问题，正是这种奇偶拆分呈现出了稳定的周期结构。实际算出的结果是：偶数子序列在前 \(22\) 个偶数项之后进入周期 \(79\)，奇数子序列在前 \(161\) 个奇数项之后进入周期 \(70\)。
若记
$$c_r(N)=\#\{n\in[1,N]:g(n)=r\},$$
则可以拆成
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
一旦某条子序列的前导段长度和周期长度确定下来，前 \(T\) 项中值 \(r\) 出现的次数就可以写成“前导段贡献 + 整周期贡献 + 余下尾段贡献”。这样一来，\(N=12{,}491{,}249\) 这个极大的上界就不再需要逐项展开。
有了周期计数以后，具体的堆大小只通过其 Grundy 值参与后续计算。定义
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
固定某个 Grundy 类 \(r\)。这一类中一共有 \(c_r\) 种不同的堆大小，而且允许重复选择同一个堆大小。因此，从该类中恰好选出 \(k\) 个堆的方案数是
$$\binom{c_r+k-1}{k}.$$
这就是可重复组合公式，也可以看成下列生成函数中 \(z^k\) 的系数：
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$$
更关键的是 xor 贡献只取决于 \(k\) 的奇偶性。因为 \(r\oplus r=0\)，所以从同一类里取 \(k\) 个堆时，若 \(k\) 为偶数，则该类总 xor 贡献为 \(0\)；若 \(k\) 为奇数，则总 xor 贡献为 \(r\)。
接下来按 Grundy 类依次处理。令 \(DP[\xi][t]\) 表示：只使用目前已经处理过的类别，选出恰好 \(t\) 个堆，并且当前 xor 为 \(\xi\) 的方案数。初始状态是
$$DP[0][0]=1.$$
当加入类别 \(r\) 时，如果从该类中再选 \(k\) 个堆，则总个数增加 \(k\)，xor 是否变化完全由 \(k\) 的奇偶决定，因此转移为
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{当 \(k\) 为偶数},$$
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{当 \(k\) 为奇数}.$$
所有类别处理完以后，答案就是
$$S(N,m)=DP[0][m]\pmod{912491249}.$$
实际前缀里只出现了 \(0\) 到 \(10\) 这 \(11\) 个 Grundy 值，因此 xor 状态空间只需要 \(16\) 个掩码。
由
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
可得各类频数
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$$
若总共只选两个堆，那么总 xor 为 \(0\) 当且仅当这两个堆来自同一个 Grundy 类。于是
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
这个例子与动态规划的含义完全一致：当 \(m=2\) 时，只有同一类别中的偶数次选取会贡献到 xor 为零的最终状态。
实现首先把 Grundy 序列预计算到 \(20000\)。对每个 \(n\)，程序把所有可达状态的 Grundy 值装入一个位掩码，再从中取 mex，得到新的 \(g(n)\)。这样既得到了整个前缀，也得到了前缀中出现的最大 Grundy 值。
随后程序把偶数位置和奇数位置两条子序列分别取出，并为每条子序列搜索一个较短周期。候选周期只检查到 \(300\)，尾部必须至少已经连续重复六次，然后再把起点尽量向前移动到仍然满足周期的位置。最终得到的结果是：偶数子序列周期为 \(79\)、起点在第 \(22\) 个偶数项之后；奇数子序列周期为 \(70\)、起点在第 \(161\) 个奇数项之后。
利用这两个周期描述，程序就能计算 \(1\) 到 \(N\) 中每个 Grundy 值的出现次数。对每个类别大小 \(c_r\)，再生成 \(\binom{c_r+k-1}{k}\bmod 912491249\) 的系数表，其中 \(0\le k\le m\)，并按 \(k\) 的奇偶拆成两部分。这样做以后，每个类别的转移只剩下“xor 保持不变”或“xor 与 \(r\) 做一次异或”两种情况。
最后执行一个滚动两层的动态规划，维度是 xor 掩码和已选堆数。由于观测到的 Grundy 值只在 \(0,\dots,10\) 之间，所以只需要 \(16\) 个 xor 掩码；最终答案就是 xor 为 \(0\)、总堆数为 \(1249\) 的那一格。
记预计算长度为 \(M=20000\)，Grundy 类别数为 \(R\)，xor 掩码数为 \(X\)。构造 Grundy 前缀的时间复杂度为
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2),$$
因为每个 \(n\) 都要检查最多到 \(n/2\) 的所有分裂，空间复杂度是存储前缀序列所需的 \(O(M)\)。奇偶子序列上的周期搜索规模远小于这一步，因此不是主导项。
周期压缩之后，频数统计只与周期长度线性相关。真正的组合计算来自一个大小为 \(X\times(m+1)\) 的动态规划表，它会对每个 Grundy 类和所有 \(k\le m\) 执行更新，因此时间复杂度为 \(O(RXm^2)\)，空间复杂度为 \(O(Xm)\)。在本题中 \(R=11\)、\(X=16\)，所以实际瓶颈是前面的 Grundy 预计算，而不是最后的 xor DP。
Рассматривается беспристрастная игра на кучах. Из кучи размера \(n\) можно либо убрать \(1\), \(2\), \(4\) или \(9\) камней, либо разбить кучу на две положительные части с суммой \(n\). Для \(N=12{,}491{,}249\) и \(m=1249\) величина \(S(N,m)\) равна числу мультимножеств из \(m\) размеров куч, выбранных из \(\{1,2,\dots,N\}\), для которых объединенная позиция является проигрышной; ответ берется по модулю \(912491249\).
По теореме Шпрага-Гранди сумма независимых куч проигрышна тогда и только тогда, когда xor одно-кучных значений Гранди равен \(0\). Поэтому задача распадается на три части: вычислить \(g(n)\) для одной кучи, определить, сколько раз каждое значение Гранди встречается при \(1\le n\le N\), и затем посчитать мультимножества размера \(m\) с нулевым xor.
Реализации сочетают теорию игр, хвостовую периодичность и компактную динамику по xor. Огромный параметр \(N\) обрабатывается не прямым продолжением последовательности до \(N\), а использованием найденной периодической структуры.
Пусть \(g(n)\) обозначает значение Гранди для одной кучи размера \(n\). Тогда \(g(0)=0\). Для \(n\ge 1\) каждая допустимая операция дает достижимое значение. Ходы вычитания дают \(g(n-1)\), \(g(n-2)\), \(g(n-4)\) и \(g(n-9)\), если индекс неотрицателен. Разбиение \(n=a+(n-a)\) дает xor \(g(a)\oplus g(n-a)\).
Следовательно,
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
Верхняя граница \(\lfloor n/2\rfloor\) достаточна, потому что разбиения \(a,n-a\) и \(n-a,a\) описывают одну и ту же позицию. Первые значения таковы:
$$g(1..10)=1,2,0,3,4,6,1,2,5,3.$$
Уже по этому началу видно, что операция разбиения делает структуру существенно богаче, чем в обычной игре на вычитание.
Реализации не пытаются вывести явную формулу для \(g(n)\). Вместо этого они вычисляют достаточно длинный префикс и отдельно анализируют подпоследовательности
$$e_k=g(2k),\qquad o_k=g(2k-1).$$
Именно такое разбиение по четности здесь и проявляет устойчивую периодичность. По вычисленным данным четная подпоследовательность становится периодической с периодом \(79\) после первых \(22\) четных членов, а нечетная подпоследовательность становится периодической с периодом \(70\) после первых \(161\) нечетных членов.
Если \(c_r(N)\) обозначает число размеров куч \(n\in[1,N]\) со значением Гранди \(r\), то
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
После того как известны предпериод и период каждой подпоследовательности, число появлений значения \(r\) среди первых \(T\) членов находится как вклад префикса, плюс вклад полных циклов, плюс короткий хвост. Так громадное \(N=12{,}491{,}249\) сводится к простой арифметике подсчета.
После периодического подсчета реальные размеры куч участвуют в дальнейшем только через их значение Гранди. Обозначим
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
Зафиксируем класс \(r\). В нем находится \(c_r\) различных размеров куч, причем один и тот же размер можно брать несколько раз. Поэтому число способов выбрать ровно \(k\) куч из класса \(r\) равно
$$\binom{c_r+k-1}{k}.$$
Это стандартная формула сочетаний с повторениями, то есть коэффициент при \(z^k\) в ряде
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$$
Вклад в xor зависит только от четности \(k\). Поскольку \(r\oplus r=0\), при четном \(k\) суммарный вклад класса равен \(0\), а при нечетном \(k\) равен \(r\).
Классы Гранди обрабатываются по очереди. Пусть \(DP[\xi][t]\) означает число способов выбрать ровно \(t\) куч из уже обработанных классов так, чтобы текущий xor был равен \(\xi\). Начальное состояние:
$$DP[0][0]=1.$$
При добавлении класса \(r\) выбор \(k\) куч увеличивает общее число на \(k\), а xor меняет только в зависимости от четности \(k\). Поэтому переходы имеют вид
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{для четных }k,$$
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}\qquad\text{для нечетных }k.$$
После обработки всех классов получаем
$$S(N,m)=DP[0][m]\pmod{912491249}.$$
В вычисленном префиксе встречаются только значения Гранди от \(0\) до \(10\), поэтому пространство xor-состояний имеет размер \(16\).
Из
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
следуют частоты классов
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$$
При выборе ровно двух куч общий xor равен \(0\) тогда и только тогда, когда обе выбранные кучи принадлежат одному классу Гранди. Поэтому
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
Этот пример точно отражает смысл DP: для \(m=2\) в конечное состояние с xor \(0\) попадают только четные выборы внутри одного класса.
Сначала реализация вычисляет префикс последовательности Гранди до \(20000\). Для каждого размера кучи она собирает все достижимые значения Гранди в битовую маску и затем берет mex. Так получается и сам префикс, и максимальное значение Гранди, встретившееся в нем.
Затем отдельно извлекаются четная и нечетная подпоследовательности, и для каждой ищется короткий период. Проверяются кандидаты \(p\le 300\), хвост обязан содержать не менее шести подряд идущих повторов, после чего начало сдвигается максимально влево. В итоге находятся период \(79\) после \(22\) четных членов и период \(70\) после \(161\) нечетных членов.
Используя эти периодические описания, реализация подсчитывает, сколько раз каждое значение Гранди встречается среди чисел от \(1\) до \(N\). Для каждого размера класса \(c_r\) затем строятся коэффициенты \(\binom{c_r+k-1}{k}\bmod 912491249\) для \(0\le k\le m\), причем отдельно хранятся члены с четным и нечетным \(k\), чтобы обновление xor сводилось к двум случаям: маска не меняется или xor переключается на \(r\).
В финале выполняется двухслойная динамика по xor-маске и количеству выбранных куч. Поскольку наблюдаемые значения Гранди лежат в диапазоне \(0,\dots,10\), достаточно \(16\) xor-масок, а ответом является ячейка с xor \(0\) и общим числом куч \(1249\).
Пусть \(M=20000\) — длина префикса, \(R\) — число реально используемых классов Гранди, \(X\) — число xor-масок. Построение префикса требует
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$$
времени, так как для каждого \(n\) перебираются все разбиения до \(n/2\), и \(O(M)\) памяти для хранения последовательности. Поиск периодов в четной и нечетной подпоследовательностях существенно меньше и не доминирует.
После сжатия по периодам подсчет частот линейный по длинам периодов. Основная комбинаторная часть — это DP размера \(X\times(m+1)\), которая для каждого класса обновляется по всем \(k\le m\). Отсюда получаем \(O(RXm^2)\) времени и \(O(Xm)\) памяти. В данной задаче \(R=11\) и \(X=16\), поэтому на практике главным узким местом остается предварительное вычисление последовательности Гранди.
المسألة تتعلق بلعبة غير متحيزة على أكوام. من كومة حجمها \(n\) يمكن إزالة \(1\) أو \(2\) أو \(4\) أو \(9\) حجرات، أو يمكن تقسيم الكومة إلى كومتين موجبتين مجموعهما \(n\). عند \(N=12{,}491{,}249\) و\(m=1249\)، فإن الكمية المطلوبة \(S(N,m)\) هي عدد المجموعات المتعددة المؤلفة من \(m\) أحجام أكوام مأخوذة من \(\{1,2,\dots,N\}\) بحيث تكون الوضعية الكلية خاسرة، مع أخذ النتيجة بترديد \(912491249\).
بحسب نظرية Sprague-Grundy تكون محصلة عدة أكوام مستقلة وضعية خاسرة إذا وفقط إذا كان xor لقيم Grundy الفردية مساويًا لـ \(0\). لذلك تنقسم المهمة إلى ثلاث مراحل: حساب \(g(n)\) لكومة واحدة، ثم حساب عدد مرات ظهور كل قيمة Grundy بين \(1\) و\(N\)، ثم عدّ المجموعات المتعددة ذات الحجم \(m\) التي يكون xor الكلي لها صفرًا.
تعتمد التطبيقات على مزج نظرية الألعاب مع دورية ذيلية ومع برمجة ديناميكية مدمجة على xor. العدد الضخم \(N\) لا يُعالَج بتمديد المتتالية كاملة حتى \(N\)، بل باستغلال البنية الدورية التي تظهر بعد فصل الحدود الزوجية عن الفردية.
لتكن \(g(n)\) قيمة Grundy لكومة واحدة حجمها \(n\). عندئذٍ \(g(0)=0\). ولكل \(n\ge 1\)، تعطي كل نقلة قانونية قيمة قابلة للوصول. حركات الإزالة تعطي \(g(n-1)\) و\(g(n-2)\) و\(g(n-4)\) و\(g(n-9)\) متى كان المؤشر غير سالب. أما التقسيم \(n=a+(n-a)\) فيعطي القيمة \(g(a)\oplus g(n-a)\).
إذًا
$$g(n)=\operatorname{mex}\left(\{g(n-s): s\in\{1,2,4,9\},\ s\le n\}\cup\{g(a)\oplus g(n-a):1\le a\le \lfloor n/2\rfloor\}\right).$$
يكفي الحد الأعلى \(\lfloor n/2\rfloor\) لأن التقسيمين \(a,n-a\) و\(n-a,a\) يمثلان الوضعية نفسها. والقيم الأولى هي
$$g(1..10)=1,2,0,3,4,6,1,2,5,3.$$
حتى هذا المقطع القصير يوضح أن إضافة خطوة التقسيم تجعل المتتالية أغنى بكثير من لعبة طرح بسيطة.
التطبيقات لا تبحث عن صيغة مغلقة لـ \(g(n)\)، بل تحسب بادئة طويلة أولًا ثم تدرس على حدة المتتاليتين
$$e_k=g(2k),\qquad o_k=g(2k-1).$$
هذا الفصل بحسب الزوجية هو بالضبط ما يُظهر البنية الدورية هنا. البيانات المحسوبة تبين أن المتتالية الزوجية تصبح دورية بفترة \(79\) بعد أول \(22\) حدًا زوجيًا، بينما تصبح المتتالية الفردية دورية بفترة \(70\) بعد أول \(161\) حدًا فرديًا.
إذا رمزنا بـ \(c_r(N)\) إلى عدد الأحجام \(n\in[1,N]\) التي تحقق \(g(n)=r\)، فإن
$$c_r(N)=c_r^{\text{odd}}\left(\left\lceil\frac{N}{2}\right\rceil\right)+c_r^{\text{even}}\left(\left\lfloor\frac{N}{2}\right\rfloor\right).$$
وبمجرد معرفة طول الجزء غير الدوري وطول الفترة لكل متتالية فرعية، يصبح عدد ظهور القيمة \(r\) بين أول \(T\) حدود مساويًا لمساهمة المقدمة، ثم عدد من الدورات الكاملة، ثم ذيل قصير. وبهذا يتحول \(N=12{,}491{,}249\) من حد هائل إلى حساب عددي مباشر.
بعد هذا العد الدوري لا يعود حجم الكومة مهمًا بذاته، بل فقط من خلال قيمة Grundy الخاصة به. نعرّف
$$c_r=\#\{n\in\{1,\dots,N\}:g(n)=r\}.$$
لنثبت فئة معينة \(r\). تحتوي هذه الفئة على \(c_r\) أحجام مختلفة، كما أن تكرار الحجم نفسه مسموح. لذلك فإن عدد الطرق لاختيار \(k\) أكوام بالضبط من هذه الفئة يساوي
$$\binom{c_r+k-1}{k}.$$
وهذه هي صيغة التوافيق مع التكرار، أي معامل \(z^k\) في
$$\frac{1}{(1-z)^{c_r}}=\sum_{k\ge 0}\binom{c_r+k-1}{k}z^k.$$
كما أن مساهمة xor لهذه الاختيارات تعتمد فقط على فردية \(k\) أو زوجيته. بما أن \(r\oplus r=0\)، فإن أخذ \(k\) عنصرًا من الفئة \(r\) يعطي xor كليًا يساوي \(0\) إذا كان \(k\) زوجيًا، ويساوي \(r\) إذا كان \(k\) فرديًا.
تُعالَج فئات Grundy واحدة بعد الأخرى. ليكن \(DP[\xi][t]\) عدد الطرق لاختيار \(t\) أكوام من الفئات التي عولجت حتى الآن بحيث يكون xor الحالي هو \(\xi\). في البداية لدينا
$$DP[0][0]=1.$$
عند إضافة الفئة \(r\)، فإن اختيار \(k\) أكوام منها يزيد العدد الكلي بمقدار \(k\)، ويغير xor فقط بحسب فردية \(k\). لذلك تكون الانتقالات
إذا كان \(k\) زوجيًا، فالتحديث يكون
$$DP'[\xi][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}.$$
وإذا كان \(k\) فرديًا، فالتحديث يكون
$$DP'[\xi\oplus r][t+k]\mathrel{+}=DP[\xi][t]\binom{c_r+k-1}{k}.$$
وبعد معالجة جميع الفئات تصبح الإجابة
$$S(N,m)=DP[0][m]\pmod{912491249}.$$
تُظهر البادئة المحسوبة أن قيم Grundy التي تظهر فعليًا تقع بين \(0\) و\(10\)، ولذلك يكفي فضاء xor مكوّن من \(16\) قناعًا.
من القيم
$$g(1..10)=1,2,0,3,4,6,1,2,5,3$$
نحصل على التكرارات
$$c_0=1,\quad c_1=2,\quad c_2=2,\quad c_3=2,\quad c_4=1,\quad c_5=1,\quad c_6=1.$$
إذا كان المطلوب اختيار كومتين فقط، فإن xor الكلي يساوي \(0\) إذا وفقط إذا جاءت الكومتان من فئة Grundy واحدة. وعندئذٍ
$$S(10,2)=\sum_r \binom{c_r+1}{2}=\binom{2}{2}+\binom{3}{2}+\binom{3}{2}+\binom{3}{2}+\binom{2}{2}+\binom{2}{2}+\binom{2}{2}=13.$$
هذا المثال يعكس تفسير البرمجة الديناميكية بدقة: عند \(m=2\) لا تصل إلى xor صفري إلا الاختيارات الزوجية من داخل الفئة نفسها.
يبدأ التنفيذ بحساب بادئة من متتالية Grundy حتى \(20000\). ولكل حجم كومة، تُجمع قيم Grundy الممكن الوصول إليها داخل قناع بتات، ثم تُؤخذ قيمة mex للحصول على الحد الجديد. وبهذا تُستخرج المتتالية نفسها وكذلك أكبر قيمة Grundy ظهرت في البادئة.
بعد ذلك تُفصل الحدود الزوجية والفردية إلى متتاليتين مستقلتين، ويُبحث عن فترة قصيرة لكل واحدة منهما. تُفحَص الفترات المرشحة حتى \(300\)، ويُشترط أن يحتوي الذيل على ست تكرارات متتالية على الأقل، ثم يُحرَّك موضع البداية إلى أقرب مكان مبكر تظل فيه الدورية صحيحة. والنتيجة النهائية هي فترة \(79\) بعد \(22\) حدًا زوجيًا، وفترة \(70\) بعد \(161\) حدًا فرديًا.
باستخدام هذا الوصف الدوري، يحسب التنفيذ عدد مرات ظهور كل قيمة Grundy ضمن \(\{1,\dots,N\}\). ولكل فئة حجمها \(c_r\)، تُبنى معاملات \(\binom{c_r+k-1}{k}\bmod 912491249\) لكل \(0\le k\le m\)، ثم تُقسَّم إلى معاملات لِـ \(k\) الزوجي و\(k\) الفردي، بحيث يصبح تحديث xor مجرد حالتين: البقاء في القناع نفسه أو التبديل بـ \(r\).
وفي النهاية تُنفَّذ برمجة ديناميكية ذات طبقتين على أقنعة xor وعلى عدد الأكوام المختارة. وبما أن القيم المشاهدة تقع في المجال \(0,\dots,10\)، فإن \(16\) قناع xor تكفي، وتكون الإجابة هي الخانة التي تحقق xor يساوي \(0\) وعددًا كليًا من الأكوام يساوي \(1249\).
ليكن \(M=20000\) حدَّ البادئة، و\(R\) عدد فئات Grundy المستعملة، و\(X\) عدد أقنعة xor. إن بناء بادئة Grundy يكلف
$$O\left(\sum_{n=1}^{M} n\right)=O(M^2)$$
زمنًا، لأن كل \(n\) يفحص جميع التقسيمات حتى \(n/2\)، ويستخدم \(O(M)\) ذاكرة لتخزين المتتالية. أما البحث عن الدورية في المتتاليتين الزوجية والفردية فأصغر بكثير من هذه المرحلة ولا يهيمن على الكلفة الكلية.
بعد ضغط العد بواسطة الدورية، يصبح حساب التكرارات خطيًا في أطوال الفترات. أما المرحلة التجميعية الأساسية فهي برمجة ديناميكية بحجم \(X\times(m+1)\)، تُحدَّث لكل فئة وعلى جميع القيم \(k\le m\). ولذلك يكون الزمن \(O(RXm^2)\) والذاكرة \(O(Xm)\). وفي هذه المسألة تحديدًا لدينا \(R=11\) و\(X=16\)، لذا فإن الكلفة العملية المسيطرة هي بناء بادئة Grundy مرة واحدة، لا DP النهائية.