We consider a game with \(k\) independent piles. Each pile starts at an integer \(x\) chosen from the interval \([2,n]\). For one pile, a legal move selects two proper divisors of the current number, both strictly between \(1\) and the number itself, and replaces that pile by the two resulting subgames. By the Sprague-Grundy theorem, the whole position is losing exactly when the xor of the pile Grundy values is \(0\).
The task is therefore to count how many \(k\)-tuples \((x_1,\dots,x_k)\in [2,n]^k\) are winning, with the final answer taken modulo
$$987654321.$$
The program splits the work into two layers: first compute the Grundy value of one pile, then combine those one-pile values across \(k\) piles by xor convolution.
Write
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
The ordered list \(\lambda(x)=(a_1,\dots,a_m)\) is the canonical state used by the implementation. The actual primes do not matter; only the multiset of exponents matters.
Why is this valid? Every divisor of \(x\) is obtained by choosing exponents
$$0\le b_i\le a_i$$
and forming \(\prod p_i^{b_i}\). After removing zero exponents and sorting the remaining positive ones in non-increasing order, we get the same canonical pattern no matter which prime labels were used. Therefore any two integers with the same exponent pattern have exactly the same family of reachable divisor patterns. By induction on the total exponent sum, they also have the same Grundy value.
For example,
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
both have pattern \((2,1)\), so they belong to the same one-pile game state.
Fix a pattern \(\lambda\). Let \(\mathcal{D}(\lambda)\) be the set of canonical patterns obtained from all proper divisors of a number with pattern \(\lambda\), excluding \(1\) and excluding the number itself.
If \(\mathcal{G}(\mu)\) denotes the Grundy value of pattern \(\mu\), define
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}.$$
A legal move chooses two proper divisors, so the resulting position is the disjoint sum of two smaller games. Sprague-Grundy theory therefore gives the option nimbers
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
where \(\oplus\) denotes bitwise xor and the two chosen divisors may be equal. Hence
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
If \(\mathcal{D}(\lambda)\) is empty, there is no legal move and the Grundy value is \(0\).
This formula is exactly what the implementations evaluate recursively and memoize by pattern.
Suppose \(\lambda=(a_1,\dots,a_m)\). Then every divisor pattern comes from a vector \((b_1,\dots,b_m)\) with
$$0\le b_i\le a_i.$$
The all-zero vector gives the forbidden divisor \(1\), while the vector \((a_1,\dots,a_m)\) gives the forbidden divisor \(x\) itself. All other vectors correspond to proper divisors.
After deleting zeros and sorting, several different exponent choices may collapse to the same canonical pattern, but that is harmless because only the resulting Grundy values matter. The recursion is finite because every proper divisor has strictly smaller total exponent sum than the original state.
Small examples:
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
Likewise the squarefree pattern \((1,1)\) has only prime proper divisors, so its option set again has nimber set \(\{0\}\), giving Grundy value \(1\).
Once the one-pile Grundy value is known for each \(x\in[2,n]\), define the histogram
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
For \(k\) independent piles, the number of positions whose total xor equals \(t\) is the \(k\)-fold xor convolution of the sequence \(C\):
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k\text{ factors}},$$
where
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j. $$
The losing positions are exactly those with xor \(0\), so the desired answer is
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
Xor convolution is handled efficiently by the Walsh-Hadamard transform. If \(\widehat{C}\) denotes the transform of \(C\), then
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k.$$
So the procedure is:
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F.$$
The inverse transform divides by the transform length. Because the modulus \(987654321\) is odd, every power of two has a modular inverse, so the inverse transform is valid modulo the required modulus.
The single-pile values for \(x\in[2,10]\) are easy to derive from the recurrence:
$$\begin{aligned} &2,3,5,7 &&\text{are prime} &&\Rightarrow \mathcal{G}=0,\\ &4,6,9,10 &&\text{have divisor nimber set }\{0\} &&\Rightarrow \mathcal{G}=1,\\ &8 &&\text{has divisor nimber set }\{0,1\} &&\Rightarrow \mathcal{G}=2. \end{aligned}$$
Therefore
$$C=(4,4,1,0).$$
Using transform length \(4\), the Walsh-Hadamard transform is
$$\widehat{C}=(9,1,7,-1).$$
Raise componentwise to the fifth power:
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
The zero-xor coefficient after the inverse transform is
$$F_0=\frac{59049+1+16807-1}{4}=18964.$$
Total positions are
$$9^5=59049,$$
so the number of winning positions is
$$59049-18964=40085,$$
which is the checkpoint used by the implementation.
The C++, Python, and Java implementations follow the same pipeline. First they build a smallest-prime-factor sieve up to \(n\). Each integer from \(2\) to \(n\) is factored with that sieve, its prime exponents are sorted into canonical non-increasing order, and the corresponding one-pile Grundy value is obtained by memoized recursion on patterns.
During that recursion, the implementation enumerates every proper divisor in exponent space, converts it to its canonical pattern, gathers the Grundy values of all reachable proper-divisor states, and computes the mex of all pairwise xor combinations. The resulting one-pile Grundy histogram is then padded to the next power of two, transformed with the xor Walsh-Hadamard transform, raised pointwise to the \(k\)-th power, and inverse transformed. The coefficient of xor \(0\) is subtracted from \((n-1)^k\), always modulo \(987654321\).
The smallest-prime-factor sieve up to \(n\) is linear or near-linear in practice and uses \(O(n)\) memory. Factoring all integers from \(2\) to \(n\) is near-linear on average. The recursive Grundy phase depends on the number of distinct exponent patterns actually encountered and on the number of divisor exponent vectors generated for each pattern; for \(n=10^7\), those patterns are heavily reused and each exponent list is short.
If the largest observed Grundy value is below a power of two \(L\), then the xor transform works on length \(L\) and costs \(O(L\log L)\) time, plus \(O(L\log k)\) for the pointwise modular exponentiations, with \(O(L)\) additional memory. This is what makes the \(k\)-pile aggregation feasible even when \(k\) is extremely large.
Wir betrachten ein Spiel mit \(k\) unabhängigen Stapeln. Jeder Stapel startet mit einer Zahl \(x\) aus dem Intervall \([2,n]\). Für einen einzelnen Stapel besteht ein legaler Zug darin, zwei echte Teiler der aktuellen Zahl zu wählen, also beide strikt zwischen \(1\) und der Zahl selbst, und den Stapel durch die beiden entstehenden Teilspiele zu ersetzen. Nach dem Sprague-Grundy-Theorem ist die Gesamtposition genau dann verloren, wenn das xor aller Stapel-Grundy-Werte gleich \(0\) ist.
Gesucht ist also die Anzahl der \(k\)-Tupel \((x_1,\dots,x_k)\in [2,n]^k\), die Gewinnstellungen sind, modulo
$$987654321.$$
Das Programm trennt die Aufgabe in zwei Ebenen: zuerst den Grundy-Wert eines einzelnen Stapels bestimmen, danach diese Ein-Stapel-Werte über \(k\) Stapel per xor-Faltung kombinieren.
Schreibe
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
Die geordnete Liste \(\lambda(x)=(a_1,\dots,a_m)\) ist der kanonische Zustand der Implementierung. Die konkreten Primzahlen sind unwichtig; nur das Multiset ihrer Exponenten zählt.
Warum ist das korrekt? Jeder Teiler von \(x\) entsteht durch die Wahl von Exponenten
$$0\le b_i\le a_i$$
und die Bildung von \(\prod p_i^{b_i}\). Entfernt man Nullen und sortiert die positiven Exponenten wieder absteigend, so erhält man unabhängig von den Primzahlbezeichnungen dasselbe kanonische Muster. Daher besitzen zwei Zahlen mit demselben Exponentenmuster dieselbe Menge erreichbarer Teilermuster. Induktiv über die Summe der Exponenten folgt daraus auch derselbe Grundy-Wert.
Zum Beispiel haben
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
beide das Muster \((2,1)\) und gehören somit zu demselben Ein-Stapel-Zustand.
Fixiere ein Muster \(\lambda\). Sei \(\mathcal{D}(\lambda)\) die Menge aller kanonischen Muster, die aus echten Teilern einer Zahl mit Muster \(\lambda\) entstehen, wobei \(1\) und die Zahl selbst ausgeschlossen werden.
Bezeichne mit \(\mathcal{G}(\mu)\) den Grundy-Wert des Musters \(\mu\), und definiere
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}.$$
Ein legaler Zug wählt zwei echte Teiler, also entsteht als Folgestellung die disjunkte Summe zweier kleinerer Spiele. Nach Sprague-Grundy sind die Zug-Nimber daher
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
wobei \(\oplus\) das bitweise xor ist und beide gewählten Teiler auch gleich sein dürfen. Also gilt
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
Ist \(\mathcal{D}(\lambda)\) leer, gibt es keinen legalen Zug und der Grundy-Wert ist \(0\).
Genau diese Formel werten die Implementierungen rekursiv aus und memoisierten sie nach Mustern.
Sei \(\lambda=(a_1,\dots,a_m)\). Dann kommt jedes Teilermuster von einem Vektor \((b_1,\dots,b_m)\) mit
$$0\le b_i\le a_i.$$
Der Nullvektor liefert den verbotenen Teiler \(1\), während \((a_1,\dots,a_m)\) die ebenfalls ausgeschlossene Zahl \(x\) selbst ergibt. Alle anderen Vektoren stehen für echte Teiler.
Nach dem Entfernen der Nullen und dem Sortieren können mehrere Exponentenwahlen auf dasselbe kanonische Muster fallen. Das ist unproblematisch, denn für die Rekursion zählen am Ende nur die dabei entstehenden Grundy-Werte. Die Rekursion terminiert, weil jeder echte Teiler eine strikt kleinere Exponentensumme besitzt als der Ausgangszustand.
Kleine Beispiele:
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
Ebenso hat das quadratfreie Muster \((1,1)\) nur primäre echte Teiler, also wieder die Nimber-Menge \(\{0\}\), und damit Grundy-Wert \(1\).
Sobald der Grundy-Wert für jedes \(x\in[2,n]\) bekannt ist, definieren wir das Histogramm
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
Für \(k\) unabhängige Stapel ist die Anzahl der Stellungen mit Gesamt-xor \(t\) die \(k\)-fache xor-Faltung der Folge \(C\):
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k\text{ Faktoren}},$$
wobei
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j. $$
Verluststellungen sind genau die Zustände mit xor \(0\). Daher lautet die gesuchte Zahl
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
Xor-Faltung wird effizient mit der Walsh-Hadamard-Transformation behandelt. Bezeichnet \(\widehat{C}\) die Transformierte von \(C\), dann gilt
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k.$$
Das Verfahren ist also
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F.$$
Die inverse Transformation teilt durch die Transformationslänge. Weil der Modulus \(987654321\) ungerade ist, besitzt jede Zweierpotenz ein multiplikatives Inverses modulo diesem Wert, also ist die Rücktransformation wohldefiniert.
Die Ein-Stapel-Werte für \(x\in[2,10]\) folgen direkt aus der Rekursion:
$$\begin{aligned} &2,3,5,7 &&\text{sind prim} &&\Rightarrow \mathcal{G}=0,\\ &4,6,9,10 &&\text{haben die Teilernimber-Menge }\{0\} &&\Rightarrow \mathcal{G}=1,\\ &8 &&\text{hat die Teilernimber-Menge }\{0,1\} &&\Rightarrow \mathcal{G}=2. \end{aligned}$$
Somit ist
$$C=(4,4,1,0).$$
Bei Transformationslänge \(4\) ergibt die Walsh-Hadamard-Transformation
$$\widehat{C}=(9,1,7,-1).$$
Komponentenweise fünfte Potenz liefert
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
Der Koeffizient für xor \(0\) nach der inversen Transformation ist
$$F_0=\frac{59049+1+16807-1}{4}=18964.$$
Die Gesamtzahl aller Stellungen ist
$$9^5=59049,$$
also beträgt die Zahl der Gewinnstellungen
$$59049-18964=40085,$$
genau der Kontrollwert der Implementierung.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Pipeline. Zuerst bauen sie ein Sieb der kleinsten Primfaktoren bis \(n\) auf. Dann wird jede Zahl von \(2\) bis \(n\) damit faktorisiert, ihre Primexponenten werden in kanonische nicht zunehmende Reihenfolge sortiert, und der zugehörige Ein-Stapel-Grundy-Wert wird per memoisierten Rekursionen auf Mustern bestimmt.
Während dieser Rekursion zählt die Implementierung alle echten Teiler im Exponentenraum auf, überführt sie in ihre kanonischen Muster, sammelt die Grundy-Werte aller erreichbaren Teilermuster und bildet daraus den mex aller paarweisen xor-Kombinationen. Danach wird das Histogramm der Ein-Stapel-Werte auf die nächste Zweierpotenz aufgefüllt, xor-transformiert, punktweise zur \(k\)-ten Potenz erhoben und zurücktransformiert. Der Koeffizient zu xor \(0\) wird schließlich von \((n-1)^k\) abgezogen, stets modulo \(987654321\).
Das Sieb der kleinsten Primfaktoren bis \(n\) läuft in linearer oder praktisch nahezu linearer Zeit und benötigt \(O(n)\) Speicher. Auch das Faktorisieren aller Zahlen von \(2\) bis \(n\) ist im Mittel nahezu linear. Die rekursive Grundy-Phase hängt von der Zahl der tatsächlich auftretenden Exponentenmuster und von der Anzahl der für jedes Muster erzeugten Teiler-Exponentenvektoren ab; für \(n=10^7\) werden dieselben Muster jedoch oft wiederverwendet und die Exponentenlisten bleiben kurz.
Liegt der größte beobachtete Grundy-Wert unter einer Zweierpotenz \(L\), dann arbeitet die xor-Transformation auf Länge \(L\) und kostet \(O(L\log L)\) Zeit sowie zusätzlich \(O(L\log k)\) für die komponentenweisen modularen Potenzen, bei \(O(L)\) Zusatzspeicher. Genau dadurch bleibt die Aggregation über \(k\) Stapel auch für extrem großes \(k\) machbar.
\(k\) bağımsız yığından oluşan bir oyun inceleniyor. Her yığın \([2,n]\) aralığından seçilen bir \(x\) sayısıyla başlıyor. Tek bir yığın üzerinde yasal hamle, mevcut sayının \(1\) ile sayının kendisi arasında kalan iki uygun bölenini seçip yığını bu iki alt oyuna dönüştürmektir. Sprague-Grundy teoremine göre toplam konum, ancak ve ancak bütün yığınların Grundy değerlerinin xor toplamı \(0\) ise kaybeden konumdur.
Dolayısıyla amaç, \((x_1,\dots,x_k)\in [2,n]^k\) biçimindeki kaç başlangıç konumunun kazanan olduğunu saymak ve sonucu
$$987654321$$
modunda vermektir.
Program işi iki katmana ayırır: önce tek yığın Grundy değerlerini hesaplar, sonra bu dağılımı \(k\) yığın için xor konvolüsyonuyla birleştirir.
Şunu yazalım:
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
\(\lambda(x)=(a_1,\dots,a_m)\) listesi uygulamanın kullandığı kanonik durumdur. Burada asal sayıların kimliği önemli değildir; önemli olan sadece üslerin çoklu kümesidir.
Bunun nedeni şudur: \(x\)'in her böleni,
$$0\le b_i\le a_i$$
seçimleriyle \(\prod p_i^{b_i}\) biçiminde elde edilir. Sıfır üsleri atıp kalan pozitif üsleri azalan sıraya koyduğumuzda, hangi asalların kullanıldığına bakmaksızın aynı kanonik desen ortaya çıkar. Bu yüzden aynı üs desenine sahip iki sayının erişebildiği bölen desenleri aynıdır. Toplam üs sayısına göre yapılan tümevarım da Grundy değerlerinin aynı olduğunu gösterir.
Örneğin
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
aynı \((2,1)\) desenine sahiptir; dolayısıyla tek-yığın oyunu açısından aynı durumdadır.
Sabit bir \(\lambda\) deseni alalım. \(\mathcal{D}(\lambda)\), bu desene sahip bir sayının bütün uygun bölenlerinden elde edilen kanonik desenlerin kümesi olsun; burada \(1\) ve sayının kendisi dışlanır.
\(\mathcal{G}(\mu)\) deseni \(\mu\) için Grundy değeri olmak üzere
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}$$
tanımını yapalım.
Yasal bir hamle iki uygun bölen seçtiği için ortaya çıkan yeni konum iki küçük oyunun ayrık toplamıdır. Bu yüzden hamle nimber'ları
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
şeklindedir; burada \(\oplus\) bit düzeyinde xor işlemidir ve iki bölen aynı da olabilir. O halde
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
Eğer \(\mathcal{D}(\lambda)\) boşsa hiç yasal hamle yoktur ve Grundy değeri \(0\) olur.
C++, Python ve Java uygulamaları tam olarak bu bağıntıyı desen bazında özyinelemeli ve hafızalı biçimde hesaplar.
\(\lambda=(a_1,\dots,a_m)\) olsun. Her bölen deseni
$$0\le b_i\le a_i$$
koşulunu sağlayan bir \((b_1,\dots,b_m)\) vektöründen gelir. Tüm sıfırlar yasak olan \(1\) bölenini, \((a_1,\dots,a_m)\) vektörü ise yine yasak olan sayının kendisini verir. Geri kalan tüm vektörler uygun bölenlere karşılık gelir.
Sıfırlar silinip kalan üsler sıralandığında, farklı seçimler bazen aynı kanonik desene düşebilir. Bu sorun değildir; çünkü özyineleme sonunda yalnızca elde edilen Grundy değerleri kullanılır. Ayrıca her uygun bölenin toplam üs sayısı daha küçük olduğu için özyineleme sonludur.
Küçük örnekler:
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
Aynı şekilde kare-serbest desen \((1,1)\) için de uygun bölenlerin nimber kümesi \(\{0\}\) olur; dolayısıyla Grundy değeri yine \(1\)'dir.
Her \(x\in[2,n]\) için tek yığın Grundy değeri bilindiğinde şu histogram tanımlanır:
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
\(k\) bağımsız yığın için toplam xor değeri \(t\) olan konumların sayısı, \(C\) dizisinin \(k\)-kat xor konvolüsyonudur:
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k\text{ adet}}.$$
Burada
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j $$
olarak tanımlanır. Kaybeden konumlar tam olarak xor'u \(0\) olanlardır. Bu yüzden aranan cevap
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
Xor konvolüsyonunu verimli hesaplamak için Walsh-Hadamard dönüşümü kullanılır. \(\widehat{C}\), \(C\)'nin dönüşümü ise
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k$$
olur.
Yani süreç
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F$$
şeklindedir. Ters dönüşümde dönüşüm uzunluğuna bölmek gerekir. Modül \(987654321\) tek olduğu için her \(2\) kuvvetinin modüler tersi vardır; böylece ters dönüşüm güvenle yapılabilir.
\(x\in[2,10]\) için tek-yığın Grundy değerleri doğrudan bulunabilir:
$$\begin{aligned} &2,3,5,7 &&\text{asaldır} &&\Rightarrow \mathcal{G}=0,\\ &4,6,9,10 &&\text{için bölen nimber kümesi }\{0\} &&\Rightarrow \mathcal{G}=1,\\ &8 &&\text{için bölen nimber kümesi }\{0,1\} &&\Rightarrow \mathcal{G}=2. \end{aligned}$$
Dolayısıyla
$$C=(4,4,1,0).$$
Dönüşüm uzunluğu \(4\) seçildiğinde Walsh-Hadamard dönüşümü
$$\widehat{C}=(9,1,7,-1)$$
olur. Bileşenleri beşinci kuvvete yükseltirsek
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
Ters dönüşümden sonra xor'u \(0\) olan konum sayısı
$$F_0=\frac{59049+1+16807-1}{4}=18964$$
çıkar. Toplam konum sayısı
$$9^5=59049$$
olduğuna göre kazanan konum sayısı
$$59049-18964=40085$$
olur; bu da uygulamanın kullandığı kontrol değeridir.
C++, Python ve Java uygulamaları aynı akışı izler. Önce \(n\)'ye kadar en küçük asal bölen tablosu kurulur. Sonra \(2\)'den \(n\)'ye kadar her sayı bu tabloyla çarpanlara ayrılır, üsler azalan sırada kanonik biçime getirilir ve karşılık gelen tek-yığın Grundy değeri desen tabanlı hafızalı özyinelemeyle bulunur.
Bu özyineleme sırasında uygulama, tüm uygun bölenleri üs uzayında üretir, her birini kanonik desene çevirir, erişilebilen bölen durumlarının Grundy değerlerini toplar ve tüm ikili xor birleşimlerinin mex değerini alır. Daha sonra tek-yığın histogramı bir sonraki \(2\) kuvvetine kadar uzatılır, xor Walsh-Hadamard dönüşümünden geçirilir, her bileşen \(k\). kuvvete yükseltilir ve ters dönüşüm uygulanır. Son adımda xor'u \(0\) olan katsayı \((n-1)^k\)'den çıkarılır; her işlem \(987654321\) modunda yapılır.
\(n\)'ye kadar kurulan en küçük asal bölen eleği doğrusal ya da pratikte doğrusal-zamana yakın çalışır ve \(O(n)\) bellek kullanır. \(2\)'den \(n\)'ye kadar tüm sayıların çarpanlara ayrılması da ortalamada yaklaşık doğrusal davranır. Özyinelemeli Grundy aşamasının maliyeti, gerçekten karşılaşılan farklı üs desenlerinin sayısına ve her desen için üretilen bölen üs vektörlerinin sayısına bağlıdır; \(n=10^7\) için desenler yoğun biçimde yeniden kullanılır ve üs listeleri kısadır.
Gözlenen en büyük Grundy değeri bir \(L\) iki kuvvetinin altındaysa, xor dönüşümü uzunluk \(L\) üzerinde çalışır ve \(O(L\log L)\) zaman ister; ayrıca bileşen bazlı modüler üs alma için \(O(L\log k)\) ek zaman ve \(O(L)\) ek bellek gerekir. Bu sayede \(k\) çok büyük olsa bile \(k\) yığını birleştirmek mümkün olur.
Se estudia un juego con \(k\) pilas independientes. Cada pila empieza con un entero \(x\) elegido en \([2,n]\). En una pila individual, un movimiento legal consiste en escoger dos divisores propios del número actual, ambos estrictamente entre \(1\) y el número mismo, y reemplazar la pila por los dos subjuegos resultantes. Por el teorema de Sprague-Grundy, la posición total es perdedora exactamente cuando el xor de los valores Grundy de todas las pilas es \(0\).
Por lo tanto, hay que contar cuántos \(k\)-tuplos \((x_1,\dots,x_k)\in [2,n]^k\) son posiciones ganadoras, y devolver el resultado módulo
$$987654321.$$
El programa separa el problema en dos capas: primero calcula el valor Grundy de una sola pila y después combina esa distribución para \(k\) pilas mediante convolución xor.
Escribimos
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
La lista \(\lambda(x)=(a_1,\dots,a_m)\) es el estado canónico que usa la implementación. Las bases primas concretas no importan; solo importa el multiconjunto de exponentes.
La razón es la siguiente: cada divisor de \(x\) se obtiene eligiendo exponentes
$$0\le b_i\le a_i$$
y formando \(\prod p_i^{b_i}\). Si eliminamos los exponentes nulos y ordenamos los positivos en orden no creciente, obtenemos el mismo patrón canónico sin importar qué etiquetas primas aparezcan. En consecuencia, dos enteros con el mismo patrón de exponentes tienen exactamente la misma familia de patrones de divisores alcanzables. Por inducción sobre la suma total de exponentes, también tienen el mismo valor Grundy.
Por ejemplo,
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
comparten el patrón \((2,1)\), así que representan el mismo estado de una pila.
Fijemos un patrón \(\lambda\). Sea \(\mathcal{D}(\lambda)\) el conjunto de patrones canónicos producidos por todos los divisores propios de un número con patrón \(\lambda\), excluyendo \(1\) y excluyendo el propio número.
Si \(\mathcal{G}(\mu)\) denota el valor Grundy del patrón \(\mu\), definimos
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}.$$
Un movimiento legal elige dos divisores propios, así que la posición resultante es la suma disjunta de dos juegos más pequeños. Por Sprague-Grundy, los nimbers de las opciones son
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
donde \(\oplus\) es xor bit a bit y los dos divisores escogidos pueden coincidir. Por tanto,
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
Si \(\mathcal{D}(\lambda)\) es vacío, no existe ningún movimiento legal y el valor Grundy es \(0\).
Ésta es exactamente la relación que evalúan las implementaciones de forma recursiva con memoización por patrón.
Si \(\lambda=(a_1,\dots,a_m)\), cada patrón de divisor procede de un vector \((b_1,\dots,b_m)\) tal que
$$0\le b_i\le a_i.$$
El vector completamente nulo produce el divisor prohibido \(1\), mientras que \((a_1,\dots,a_m)\) produce el propio \(x\), que también se excluye. Todos los demás vectores corresponden a divisores propios.
Después de borrar ceros y ordenar, varias elecciones distintas pueden colapsar al mismo patrón canónico. Eso no causa ningún problema, porque al final solo importan los valores Grundy que aparecen. La recursión termina porque todo divisor propio tiene suma total de exponentes estrictamente menor que la del estado original.
Ejemplos pequeños:
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
Del mismo modo, el patrón libre de cuadrados \((1,1)\) solo tiene divisores propios primos, así que su conjunto de nimbers accesibles es \(\{0\}\) y su valor Grundy también vale \(1\).
Una vez conocido el valor Grundy para cada \(x\in[2,n]\), definimos el histograma
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
Para \(k\) pilas independientes, el número de posiciones cuyo xor total vale \(t\) es la \(k\)-ésima convolución xor de la secuencia \(C\):
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k\text{ factores}},$$
donde
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j. $$
Las posiciones perdedoras son exactamente las de xor \(0\), de modo que la respuesta buscada es
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
La convolución xor se calcula eficientemente con la transformada de Walsh-Hadamard. Si \(\widehat{C}\) es la transformada de \(C\), entonces
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k.$$
Así, el procedimiento es
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F.$$
La transformada inversa divide por la longitud de la transformada. Como el módulo \(987654321\) es impar, toda potencia de \(2\) tiene inverso modular, por lo que la inversión es válida bajo el módulo pedido.
Los valores de una pila para \(x\in[2,10]\) se obtienen directamente de la recurrencia:
$$\begin{aligned} &2,3,5,7 &&\text{son primos} &&\Rightarrow \mathcal{G}=0,\\ &4,6,9,10 &&\text{tienen conjunto de nimbers }\{0\} &&\Rightarrow \mathcal{G}=1,\\ &8 &&\text{tiene conjunto de nimbers }\{0,1\} &&\Rightarrow \mathcal{G}=2. \end{aligned}$$
Por tanto,
$$C=(4,4,1,0).$$
Con longitud de transformada \(4\), la transformada de Walsh-Hadamard es
$$\widehat{C}=(9,1,7,-1).$$
Elevando componente a componente a la quinta potencia obtenemos
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
El coeficiente de xor \(0\) después de invertir la transformada es
$$F_0=\frac{59049+1+16807-1}{4}=18964.$$
Como el número total de posiciones es
$$9^5=59049,$$
el número de posiciones ganadoras resulta ser
$$59049-18964=40085,$$
que coincide con el punto de verificación usado por la implementación.
Las implementaciones en C++, Python y Java siguen la misma tubería. Primero construyen una criba de menor factor primo hasta \(n\). Después factorizan cada entero entre \(2\) y \(n\), ordenan sus exponentes en una forma canónica no creciente y obtienen el valor Grundy de una pila mediante una recursión memoizada sobre patrones.
Durante esa recursión, la implementación enumera todos los divisores propios en el espacio de exponentes, transforma cada uno a su patrón canónico, reúne los valores Grundy de todos los estados accesibles por divisor propio y calcula el mex de todas las combinaciones xor por pares. Luego el histograma de valores de una pila se amplía hasta la siguiente potencia de dos, se transforma con Walsh-Hadamard xor, se eleva punto a punto a la potencia \(k\) y se invierte. El coeficiente de xor \(0\) se resta de \((n-1)^k\), siempre módulo \(987654321\).
La criba de menor factor primo hasta \(n\) es lineal o casi lineal en la práctica y usa \(O(n)\) memoria. Factorizar todos los enteros de \(2\) a \(n\) también es casi lineal en promedio. La fase recursiva de Grundy depende del número de patrones de exponentes distintos que realmente aparecen y del número de vectores de exponentes de divisores generados para cada patrón; para \(n=10^7\), los patrones se reutilizan mucho y las listas de exponentes son cortas.
Si el mayor valor Grundy observado está por debajo de una potencia de dos \(L\), la transformada xor trabaja con longitud \(L\) y cuesta \(O(L\log L)\) tiempo, más \(O(L\log k)\) por las potenciaciones modulares punto a punto, con \(O(L)\) memoria adicional. Eso hace viable la agregación de \(k\) pilas incluso cuando \(k\) es enorme.
这里研究的是一个由 \(k\) 个相互独立的堆组成的博弈。每个堆一开始放着一个整数 \(x\)，其中 \(x\in[2,n]\)。对单个堆而言，一步合法操作是从当前数字的真因子中选出两个数，它们都严格大于 \(1\) 且严格小于当前数字，然后把这一堆替换成这两个子博弈。根据 Sprague-Grundy 定理，整个局面当且仅当所有堆的 Grundy 值按位异或后的结果为 \(0\) 时是必败态。
因此问题等价于统计有多少个 \(k\) 元组 \((x_1,\dots,x_k)\in[2,n]^k\) 是必胜态，并将答案对
$$987654321$$
取模。
程序把问题分成两层：先求单堆的 Grundy 值，再把这些单堆结果通过 xor 卷积合并成 \(k\) 堆的总分布。
把整数写成
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
实现中真正作为状态使用的是有序指数列表 \(\lambda(x)=(a_1,\dots,a_m)\)。具体是哪几个素数并不重要，重要的是这些指数构成的多重集。
原因在于：\(x\) 的任意一个因子都可以通过选择
$$0\le b_i\le a_i$$
并构造 \(\prod p_i^{b_i}\) 得到。把所有为 \(0\) 的指数删掉，再把剩余正指数按非增顺序排序，就得到一个与素数标签无关的标准模式。所以，只要两个整数拥有相同的指数模式，它们能够到达的真因子模式集合就完全相同。再对指数总和做归纳，就可知它们的 Grundy 值也必然相同。
例如
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
虽然具体素数位置不同，但它们的模式同为 \((2,1)\)，所以在单堆游戏里属于同一个状态。
固定一个模式 \(\lambda\)。记 \(\mathcal{D}(\lambda)\) 为所有真因子对应的标准模式集合，其中排除了 \(1\) 和原数本身。
若 \(\mathcal{G}(\mu)\) 表示模式 \(\mu\) 的 Grundy 值，那么定义
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}.$$
一步合法操作会选出两个真因子，因此新局面是两个更小子游戏的直和。由 Sprague-Grundy 理论可知，对应选项的 nimber 为
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
其中 \(\oplus\) 表示按位异或，而且两个选到的真因子允许相同。于是得到核心递推：
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
如果 \(\mathcal{D}(\lambda)\) 为空，就说明没有合法移动，Grundy 值自然是 \(0\)。
C++、Python 和 Java 实现所做的事情，正是按模式递归计算这个公式，并把已经求过的模式缓存起来。
设 \(\lambda=(a_1,\dots,a_m)\)。那么任意一个因子模式都来自某个指数向量 \((b_1,\dots,b_m)\)，满足
$$0\le b_i\le a_i.$$
全零向量对应被排除的因子 \(1\)，而 \((a_1,\dots,a_m)\) 对应原数自身，也必须排除。除这两种情况以外，其余向量全部对应真因子。
删掉零指数并重新排序以后，不同的向量有时会压缩成同一个标准模式。但这并不会破坏算法，因为递推最终只依赖这些可达状态的 Grundy 值，而不是依赖它们最初是由哪一种具体因子写法产生的。递归一定会终止，因为任何真因子的指数总和都严格小于原状态。
几个小例子可以直接算出：
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
同理，无平方因子模式 \((1,1)\) 的所有真因子都是素数，因此可达 nimber 集仍是 \(\{0\}\)，它的 Grundy 值也是 \(1\)。
当每个 \(x\in[2,n]\) 的单堆 Grundy 值都已知时，定义频数序列
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
对于 \(k\) 个相互独立的堆，总 xor 为 \(t\) 的局面数，正是序列 \(C\) 的 \(k\) 次 xor 卷积：
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k\text{ 个因子}}.$$
这里
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j. $$
由于必败态恰好对应总 xor 为 \(0\)，最终答案就是
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
xor 卷积最适合用 Walsh-Hadamard 变换来对角化。若 \(\widehat{C}\) 表示 \(C\) 的变换结果，则有
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k.$$
因此整个流程可以写成
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F.$$
逆变换需要除以变换长度。由于模数 \(987654321\) 是奇数，任何 \(2\) 的幂都与它互素，因此都存在模逆元，逆变换在这个模数下是合法的。
先计算 \(x\in[2,10]\) 的单堆 Grundy 值：
$$\begin{aligned} &2,3,5,7 &&\text{都是素数} &&\Rightarrow \mathcal{G}=0,\\ &4,6,9,10 &&\text{可达 nimber 集为 }\{0\} &&\Rightarrow \mathcal{G}=1,\\ &8 &&\text{可达 nimber 集为 }\{0,1\} &&\Rightarrow \mathcal{G}=2. \end{aligned}$$
所以频数序列为
$$C=(4,4,1,0).$$
取变换长度为 \(4\)，得到 Walsh-Hadamard 变换
$$\widehat{C}=(9,1,7,-1).$$
把各分量分别提升到五次幂：
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
逆变换后，总 xor 为 \(0\) 的系数是
$$F_0=\frac{59049+1+16807-1}{4}=18964.$$
全部初始局面的总数是
$$9^5=59049,$$
因此必胜态个数为
$$59049-18964=40085,$$
这正是实现中使用的校验值。
C++、Python 和 Java 实现遵循同一条流水线。首先构造到 \(n\) 为止的最小素因子筛。然后把 \(2\) 到 \(n\) 的每个整数都用该筛分解，得到其素因子指数列表，再把指数按非增顺序整理成标准模式，并通过带缓存的递归求出对应的单堆 Grundy 值。
在递归阶段，实现会在指数空间中枚举所有真因子，把它们转换成标准模式，收集所有可达真因子状态的 Grundy 值，再对所有两两 xor 结果取 mex。接着把单堆 Grundy 频数补齐到不小于最大 Grundy 值的下一个 \(2\) 的幂，执行 xor 型 Walsh-Hadamard 变换，对每个变换分量做 \(k\) 次幂，最后逆变换。得到的 xor 为 \(0\) 的项从 \((n-1)^k\) 中减去，全程都在模 \(987654321\) 下完成。
最小素因子筛到 \(n\) 的时间在实践中是线性或近线性的，空间为 \(O(n)\)。对区间 \([2,n]\) 中所有整数做分解，平均复杂度也接近线性。递归 Grundy 阶段的代价取决于实际出现的不同指数模式数量，以及每个模式需要枚举多少个真因子指数向量；在 \(n=10^7\) 这一规模下，指数模式会被大量复用，而且每个指数列表都很短。
如果观测到的最大 Grundy 值落在某个二次幂 \(L\) 以下，那么 xor 变换长度就是 \(L\)，对应时间复杂度 \(O(L\log L)\)；逐点做模幂还要额外花费 \(O(L\log k)\) 时间，附加空间为 \(O(L)\)。这一步正是算法能够处理极大 \(k\) 的关键。
Рассматривается игра с \(k\) независимыми кучами. Каждая куча начинается с числа \(x\), выбранного из интервала \([2,n]\). Для одной кучи допустимый ход состоит в том, чтобы выбрать два собственных делителя текущего числа, оба строго больше \(1\) и строго меньше самого числа, и заменить кучу двумя получившимися подиграми. По теореме Спрэге-Гранди вся позиция проигрышна тогда и только тогда, когда xor всех значений Гранди по кучам равен \(0\).
Значит, нужно посчитать, сколько \(k\)-кортежей \((x_1,\dots,x_k)\in[2,n]^k\) являются выигрышными позициями, а ответ выдать по модулю
$$987654321.$$
Программа разбивает задачу на два уровня: сначала вычисляет значение Гранди для одной кучи, затем объединяет эти одно-кучные значения по \(k\) кучам с помощью xor-свёртки.
Запишем
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
Состоянием в реализации служит упорядоченный список \(\lambda(x)=(a_1,\dots,a_m)\). Конкретные простые числа не важны; важен только мультимножество показателей.
Почему это работает? Любой делитель числа \(x\) получается выбором показателей
$$0\le b_i\le a_i$$
и построением \(\prod p_i^{b_i}\). Если удалить нули и отсортировать оставшиеся положительные показатели по невозрастанию, мы получим один и тот же канонический шаблон независимо от имён простых. Поэтому два числа с одинаковым шаблоном показателей имеют одинаковое множество достижимых шаблонов делителей. Индукция по сумме показателей показывает, что и значение Гранди у них одинаково.
Например,
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
оба имеют шаблон \((2,1)\), а значит соответствуют одному и тому же одно-кучному состоянию.
Зафиксируем шаблон \(\lambda\). Пусть \(\mathcal{D}(\lambda)\) обозначает множество канонических шаблонов, которые получаются из всех собственных делителей числа с шаблоном \(\lambda\), при этом исключаются \(1\) и само число.
Если \(\mathcal{G}(\mu)\) означает значение Гранди шаблона \(\mu\), то положим
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}.$$
Один ход выбирает два собственных делителя, поэтому новая позиция есть дизъюнктная сумма двух меньших игр. По теореме Спрэге-Гранди нимберы ходов имеют вид
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
где \(\oplus\) означает побитовый xor, причём оба выбранных делителя могут совпадать. Следовательно,
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
Если \(\mathcal{D}(\lambda)\) пусто, допустимых ходов нет, и значение Гранди равно \(0\).
Именно эту формулу реализации вычисляют рекурсивно с мемоизацией по шаблонам.
Пусть \(\lambda=(a_1,\dots,a_m)\). Тогда каждый шаблон делителя задаётся вектором \((b_1,\dots,b_m)\), где
$$0\le b_i\le a_i.$$
Нулевой вектор соответствует запрещённому делителю \(1\), а вектор \((a_1,\dots,a_m)\) соответствует самому \(x\), который тоже исключается. Все остальные векторы задают собственные делители.
После удаления нулей и повторной сортировки разные выборы показателей могут схлопнуться в один и тот же канонический шаблон. Это не мешает, потому что рекурсия использует только возникающие значения Гранди. Рекурсия конечна, поскольку любой собственный делитель имеет строго меньшую сумму показателей, чем исходное состояние.
Небольшие примеры:
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
Точно так же для бесквадратного шаблона \((1,1)\) все собственные делители простые, поэтому множество достижимых нимберов равно \(\{0\}\), и значение Гранди снова равно \(1\).
Когда значение Гранди известно для каждого \(x\in[2,n]\), введём гистограмму
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
Для \(k\) независимых куч количество позиций с суммарным xor, равным \(t\), есть \(k\)-кратная xor-свёртка последовательности \(C\):
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k\text{ множителей}},$$
где
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j. $$
Проигрышные позиции — это ровно случаи с xor \(0\). Поэтому искомый ответ равен
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
Xor-свёртка эффективно считается с помощью преобразования Уолша-Адамара. Если \(\widehat{C}\) — преобразование последовательности \(C\), то
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k.$$
То есть алгоритм имеет вид
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F.$$
Обратное преобразование делит на длину преобразования. Так как модуль \(987654321\) нечётный, любая степень двойки обратима по этому модулю, поэтому обратное преобразование корректно.
Одно-кучные значения для \(x\in[2,10]\) легко получить из рекурсии:
$$\begin{aligned} &2,3,5,7 &&\text{простые} &&\Rightarrow \mathcal{G}=0,\\ &4,6,9,10 &&\text{имеют множество нимберов делителей }\{0\} &&\Rightarrow \mathcal{G}=1,\\ &8 &&\text{имеет множество нимберов делителей }\{0,1\} &&\Rightarrow \mathcal{G}=2. \end{aligned}$$
Значит,
$$C=(4,4,1,0).$$
При длине преобразования \(4\) получаем
$$\widehat{C}=(9,1,7,-1).$$
Возводим компоненты в пятую степень:
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
После обратного преобразования коэффициент при xor \(0\) равен
$$F_0=\frac{59049+1+16807-1}{4}=18964.$$
Общее число стартовых позиций равно
$$9^5=59049,$$
следовательно, количество выигрышных позиций равно
$$59049-18964=40085,$$
что совпадает с проверочным значением, используемым в реализации.
Реализации на C++, Python и Java используют одну и ту же схему. Сначала строится решето минимального простого делителя до \(n\). Затем каждое число от \(2\) до \(n\) раскладывается с помощью этого решета, его показатели сортируются в канонический невозрастающий порядок, и для полученного шаблона вычисляется значение Гранди одной кучи с помощью рекурсивной мемоизации.
Во время этой рекурсии реализация перебирает все собственные делители в пространстве показателей, переводит их в канонические шаблоны, собирает значения Гранди всех достижимых состояний по собственным делителям и берёт mex от всех попарных xor-комбинаций. Затем гистограмма одно-кучных значений дополняется до ближайшей степени двойки, подвергается xor-преобразованию Уолша-Адамара, покомпонентно возводится в степень \(k\) и преобразуется обратно. Коэффициент при xor \(0\) вычитается из \((n-1)^k\), всё по модулю \(987654321\).
Решето минимального простого делителя до \(n\) работает за линейное или почти линейное время на практике и требует \(O(n)\) памяти. Факторизация всех чисел от \(2\) до \(n\) в среднем тоже близка к линейной. Рекурсивная фаза значений Гранди зависит от числа реально встречающихся шаблонов показателей и от количества векторов показателей делителей, которые нужно перебрать для каждого шаблона; при \(n=10^7\) шаблоны многократно переиспользуются, а сами списки показателей коротки.
Если максимальное наблюдаемое значение Гранди меньше некоторой степени двойки \(L\), xor-преобразование работает на длине \(L\) и стоит \(O(L\log L)\) времени, плюс \(O(L\log k)\) на покомпонентные модульные степени, при \(O(L)\) дополнительной памяти. Именно это и делает возможной агрегацию по \(k\) кучам даже для очень большого \(k\).
ننظر إلى لعبة مكوّنة من \(k\) أكوام مستقلة. يبدأ كل كومة بعدد صحيح \(x\) مأخوذ من المجال \([2,n]\). في الكومة الواحدة، الحركة القانونية هي اختيار قاسمين حقيقيين للعدد الحالي، أي إن كلاهما أكبر من \(1\) وأصغر من العدد نفسه، ثم استبدال تلك الكومة باللعبتين الناتجتين. ووفقًا لمبرهنة Sprague-Grundy فإن الوضع الكلي يكون خاسرًا بالضبط عندما يكون xor لقيم Grundy لجميع الأكوام مساويًا لـ \(0\).
لذلك فالمطلوب هو عدّ عدد جميع \(k\)-يات \((x_1,\dots,x_k)\in[2,n]^k\) التي تمثل أوضاع فوز، مع إعطاء النتيجة بترديد
$$987654321.$$
يقسم البرنامج العمل إلى مرحلتين: أولًا يحسب قيمة Grundy لكومة واحدة، ثم يجمع هذه القيم عبر \(k\) أكوام باستخدام التفاف xor.
نكتب
$$x=\prod_{i=1}^{m} p_i^{a_i},\qquad a_1\ge a_2\ge \cdots \ge a_m\ge 1.$$
القائمة \(\lambda(x)=(a_1,\dots,a_m)\) هي الحالة المعيارية التي تستخدمها الخوارزمية. نوع الأعداد الأولية نفسها لا يهم؛ الذي يهم هو متعدد مجموعة الأسس فقط.
والسبب هو أن كل قاسم للعدد \(x\) ينتج من اختيار
$$0\le b_i\le a_i$$
ثم تكوين \(\prod p_i^{b_i}\). وإذا حذفنا الأسس الصفرية ورتبنا الأسس الموجبة المتبقية ترتيبًا تنازليًا، حصلنا على النمط المعياري نفسه بغض النظر عن أسماء العوامل الأولية. لذلك فإن أي عددين لهما نمط الأسس نفسه يمتلكان مجموعة حالات القواسم القابلة للوصول نفسها. وبالاستقراء على مجموع الأسس ينتج أن قيمة Grundy تكون نفسها أيضًا.
فمثلًا
$$12=2^2\cdot 3,\qquad 18=2\cdot 3^2$$
لهما النمط نفسه \((2,1)\)، ولهذا يمثلان الحالة نفسها في لعبة الكومة الواحدة.
ثبّت نمطًا \(\lambda\). ولتكن \(\mathcal{D}(\lambda)\) مجموعة الأنماط المعيارية الناتجة من جميع القواسم الحقيقية لعدد يملك النمط \(\lambda\)، مع استبعاد \(1\) واستبعاد العدد نفسه.
إذا رمزنا إلى قيمة Grundy للنمط \(\mu\) بالرمز \(\mathcal{G}(\mu)\)، فنعرف
$$\Sigma(\lambda)=\{\mathcal{G}(\mu):\mu\in\mathcal{D}(\lambda)\}.$$
بما أن الحركة القانونية تختار قاسمين حقيقيين، فإن الحالة التالية هي مجموع منفصل للعبتين أصغر. لذا فإن قيم النيم للحركات الممكنة هي
$$u\oplus v\qquad (u,v\in \Sigma(\lambda)),$$
حيث ترمز \(\oplus\) إلى xor الثنائي، ويجوز أن يكون القاسمان المختاران متساويين. ومن ثم نحصل على العلاقة الأساسية
$$\boxed{\mathcal{G}(\lambda)=\operatorname{mex}\{u\oplus v:\ u,v\in\Sigma(\lambda)\}.}$$
إذا كانت \(\mathcal{D}(\lambda)\) فارغة، فلا توجد حركة قانونية أصلًا، وبالتالي تكون قيمة Grundy مساوية لـ \(0\).
وهذه هي الصيغة نفسها التي تحسبها تطبيقات C++ وPython وJava تراجعيًا مع التخزين بحسب النمط.
إذا كان \(\lambda=(a_1,\dots,a_m)\)، فإن كل نمط لقاسم يأتي من متجه \((b_1,\dots,b_m)\) يحقق
$$0\le b_i\le a_i.$$
المتجه الصفري بالكامل يعطي القاسم المرفوض \(1\)، بينما المتجه \((a_1,\dots,a_m)\) يعطي العدد الأصلي \(x\) وهو مستبعد أيضًا. وكل المتجهات الأخرى تمثل قواسم حقيقية.
بعد حذف الأصفار وإعادة الترتيب، قد تنهار اختيارات مختلفة إلى النمط المعياري نفسه. وهذا لا يسبب أي مشكلة، لأن التراجع لا يحتاج في النهاية إلا إلى قيم Grundy الناتجة للحالات القابلة للوصول. كما أن التراجع منتهٍ لأن كل قاسم حقيقي يملك مجموع أسس أصغر من الحالة الأصلية.
أمثلة صغيرة:
$$\lambda=(1)\implies \mathcal{D}(\lambda)=\varnothing,\qquad \mathcal{G}(1)=0,$$
$$\lambda=(2)\implies \mathcal{D}(\lambda)=\{(1)\},\qquad \mathcal{G}(2)=\operatorname{mex}\{0\}=1,$$
$$\lambda=(3)\implies \Sigma(\lambda)=\{0,1\},\qquad \mathcal{G}(3)=\operatorname{mex}\{0,1\}=2.$$
وبالطريقة نفسها فإن النمط المربع-الحر \((1,1)\) لا يملك إلا قواسم أولية حقيقية، لذلك تبقى مجموعة النيمات القابلة للوصول \(\{0\}\)، ومن ثم تكون قيمة Grundy مساوية لـ \(1\).
بعد معرفة قيمة Grundy لكل \(x\in[2,n]\)، نعرّف المدرج التكراري
$$C_r=\#\{x\in[2,n]:\mathcal{G}(x)=r\}.$$
ولأجل \(k\) أكوام مستقلة، فإن عدد الأوضاع التي يكون xor الكلي فيها مساويًا لـ \(t\) هو التفاف xor من الرتبة \(k\) للمتتالية \(C\):
$$F=\underbrace{C *_\oplus C *_\oplus \cdots *_\oplus C}_{k}.$$
أي إن المتتالية \(C\) تُلفّ xor مع نفسها \(k\) مرة.
حيث
$$ (A *_\oplus B)_t=\sum_{i\oplus j=t} A_iB_j. $$
الأوضاع الخاسرة هي تمامًا الحالات التي يكون xor الكلي فيها \(0\). لذلك فإن الجواب المطلوب هو
$$\boxed{(n-1)^k-F_0 \pmod{987654321}.}$$
يُحسب التفاف xor بكفاءة بواسطة تحويل Walsh-Hadamard. فإذا كانت \(\widehat{C}\) هي صورة \(C\) بعد التحويل، فإن
$$\widehat{F}_j=\bigl(\widehat{C}_j\bigr)^k.$$
أي إن خط الأنابيب هو
$$C\ \longrightarrow\ \widehat{C}\ \longrightarrow\ \widehat{F}\ \longrightarrow\ F.$$
التحويل العكسي يتطلب القسمة على طول التحويل. وبما أن المود \(987654321\) عدد فردي، فإن كل قوة للعدد \(2\) لها معكوس ضربي modulo هذا المود، ولذلك تكون العملية العكسية صحيحة تمامًا.
يمكن استخراج قيم Grundy للأعداد \(x\in[2,10]\) مباشرة من العلاقة التراجعية:
\(2,3,5,7\) أعداد أولية، ولذلك \(\mathcal{G}=0\).
\(4,6,9,10\) تمتلك جميعها مجموعة نيمات قواسم تساوي \(\{0\}\)، ولذلك \(\mathcal{G}=1\).
\(8\) يمتلك مجموعة نيمات قواسم تساوي \(\{0,1\}\)، ولذلك \(\mathcal{G}=2\).
إذن
$$C=(4,4,1,0).$$
وباستخدام طول تحويل يساوي \(4\)، نحصل على
$$\widehat{C}=(9,1,7,-1).$$
ثم نرفع كل مركبة إلى القوة الخامسة:
$$\widehat{F}=(9^5,1^5,7^5,(-1)^5)=(59049,1,16807,-1).$$
معامل xor الصفري بعد التحويل العكسي هو
$$F_0=\frac{59049+1+16807-1}{4}=18964.$$
والعدد الكلي للأوضاع الابتدائية هو
$$9^5=59049,$$
ومن ثم يكون عدد أوضاع الفوز
$$59049-18964=40085,$$
وهو بالضبط مقدار التحقق الذي تستخدمه الخوارزمية.
تتبع تطبيقات C++ وPython وJava المسار نفسه. في البداية تُبنى غربال لأصغر عامل أولي حتى \(n\). بعد ذلك يُحلَّل كل عدد من \(2\) إلى \(n\) باستخدام هذه البنية، ثم تُرتَّب أسسه ترتيبًا تنازليًا لتكوين النمط المعياري، وتُحسب قيمة Grundy الخاصة بالكومة الواحدة باستعمال تراجع مع تخزين للحالات بحسب النمط.
أثناء هذا التراجع، تقوم الخوارزمية بتعداد جميع القواسم الحقيقية في فضاء الأسس، وتحويل كل واحد منها إلى نمطه المعياري، وجمع قيم Grundy لجميع الحالات الممكن الوصول إليها، ثم أخذ mex لكل تراكيب xor الثنائية الممكنة. بعد ذلك يُمدَّد التوزيع التكراري لقيم الكومة الواحدة إلى أقرب قوة للعدد \(2\)، ثم يُطبَّق تحويل Walsh-Hadamard الخاص بـ xor، وتُرفع القيم المتحوّلة عنصرًا بعنصر إلى القوة \(k\)، ثم يُطبَّق التحويل العكسي. وفي النهاية يُطرح معامل xor الصفري من \((n-1)^k\)، وكل ذلك تحت المود \(987654321\).
غربال أصغر عامل أولي حتى \(n\) يعمل زمنيًا بخطية أو شبه خطية عمليًا، ويستهلك \(O(n)\) من الذاكرة. كما أن تحليل جميع الأعداد من \(2\) إلى \(n\) إلى عوامل أولية يبقى قريبًا من الخطية في المتوسط. أما مرحلة Grundy التراجعية فتعتمد على عدد أنماط الأسس المختلفة التي تظهر فعلًا، وعلى عدد متجهات أسس القواسم التي تُولَّد لكل نمط؛ وعند \(n=10^7\) تكون الأنماط معاد استخدامها بكثرة، كما أن قوائم الأسس قصيرة.
إذا كانت أكبر قيمة Grundy ملحوظة أصغر من قوة للعدد \(2\) مقدارها \(L\)، فإن تحويل xor يعمل على طول \(L\) بكلفة \(O(L\log L)\)، مع كلفة إضافية \(O(L\log k)\) لرفع المركبات ترديديًا إلى القوة \(k\)، وذاكرة إضافية \(O(L)\). وهذه هي الخطوة التي تجعل تجميع \(k\) أكوام ممكنًا حتى عندما يكون \(k\) كبيرًا جدًا.