For each pile size \(n\), one move chooses a number \(a\) with \(1 \le a \le n\) and \(\gcd(a,n)=1\), then replaces the pile by \(n-a\). For fixed \(N\) and \(K\), we consider ordered \(K\)-tuples of pile sizes drawn from \(\{1,2,\dots,N-1\}\). The task is to count how many such \(K\)-pile positions are losing positions, meaning that the xor of their Grundy values is \(0\), and to return the answer modulo \(10^9+7\).
A direct dynamic program over all \(K\)-pile states is hopeless for the intended input size, so the solution first classifies the one-pile game completely and then turns the multi-pile count into an xor convolution problem.
Let \(g(n)\) be the Grundy value of one pile of size \(n\). The move rule gives
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$$
If we know the distribution of these one-pile Grundy values on \(\{1,\dots,N-1\}\), then Sprague-Grundy theory reduces the full problem to counting xor sums.
The position with \(K\) piles \((x_1,\dots,x_K)\) is losing exactly when
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
So the main difficulty is to understand \(g(n)\) for one pile. Once that is known, each pile contributes only its Grundy label, and the counting problem becomes purely combinatorial.
The implementations use the closed form
$$g(1)=1,$$
$$g(n)=0 \quad \text{for even } n,$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{for odd } n>1,$$
where \(\operatorname{spf}(n)\) is the smallest prime factor of \(n\), and \(\pi(t)\) is the number of primes at most \(t\), so for a prime \(p\), \(\pi(p)\) is its \(1\)-based prime index.
This formula follows from the move structure:
For \(n=1\), the only legal move is to \(0\), so the mex is \(1\).
If \(n\) is even, every legal \(a\) must be odd, hence every reachable value \(n-a\) is a positive odd number. Every positive odd number has positive Grundy value, so \(0\) is missing from the move set and therefore \(g(n)=0\).
Now let \(n>1\) be odd and write \(p=\operatorname{spf}(n)\). The move \(a=1\) reaches \(n-1\), which is even, so Grundy value \(0\) is present. The move \(a=n-1\) reaches \(1\), so Grundy value \(1\) is present. More generally, for every odd prime \(q<p\), the move to the pile \(q\) is legal because
$$\gcd(n,n-q)=\gcd(n,q)=1,$$
since \(q\) does not divide \(n\). That target has Grundy value \(\pi(q)\). Hence every value below \(\pi(p)\) occurs among the legal moves.
On the other hand, no legal move can land on an odd number whose smallest prime factor is exactly \(p\). If such a target \(m\) existed, then \(p\mid n\) and \(p\mid m\), so
$$\gcd(n,n-m)=\gcd(n,m)\ge p,$$
contradicting the coprimality condition on the move. Therefore Grundy value \(\pi(p)\) is absent, and the mex is exactly \(\pi(p)\).
Larger Grundy values may also appear among some moves, but they do not matter once all smaller values are present and \(\pi(p)\) is missing.
Define
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
Then \(c_t\) is the number of pile sizes carrying Grundy label \(t\). The classification above immediately implies
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$$
because exactly the even pile sizes have Grundy value \(0\), and
$$c_1=1,$$
because the only pile with Grundy value \(1\) is \(1\) itself. Every odd \(x>1\) contributes to the bucket indexed by the prime index of its smallest prime factor.
The implementations obtain these buckets with a linear sieve that stores the smallest prime factor of every integer up to \(N-1\), together with the running prime-count function \(\pi\).
Let \(L(N,K)\) denote the number of losing ordered \(K\)-tuples. If one pile contributes Grundy value \(u\) in \(c_u\) ways and another contributes \(v\) in \(c_v\) ways, then the pair contributes xor value \(u\oplus v\). This is exactly xor convolution.
For two arrays \(f\) and \(h\), define
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$$
Therefore the distribution of xor sums for \(K\) piles is the \(K\)-fold xor convolution of \(c\) with itself, and the desired answer is
$$L(N,K)=c^{(*K)}(0).$$
This identity is just Sprague-Grundy theory translated into counting language: pile choices are independent, and a position is losing exactly when the xor sum is \(0\).
Directly forming \(K\) xor convolutions would still be too slow, so the implementations switch to the Walsh-Hadamard transform for xor convolution. If \(\widehat{c}\) denotes the xor transform of \(c\), then
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$$
So the whole computation becomes:
Pad the frequency vector to a power-of-two length \(m\).
Apply the xor Walsh-Hadamard transform.
Raise each transformed component to the \(K\)-th power modulo \(10^9+7\).
Apply the same transform again.
Multiply every entry by \(m^{-1}\pmod{10^9+7}\), because for xor convolution the transform is self-inverse up to the factor \(m\).
The coefficient at index \(0\) is then exactly \(L(N,K)\).
For \(N=5\), the allowed pile sizes are \(1,2,3,4\). Their Grundy values are
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$$
Hence the frequency vector is
$$c_0=2,\qquad c_1=1,\qquad c_2=1.$$
With two piles, xor is \(0\) exactly when both piles have the same Grundy value, so
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$$
This matches the checkpoint used by the implementation and illustrates why the entire problem is governed by the Grundy frequency distribution rather than by the raw pile values.
The C++, Python, and Java implementations follow the same pipeline. First they build a linear sieve up to \(N-1\), storing for every number its smallest prime factor and also the prime-count prefix needed to convert a smallest prime factor into its prime index. Then they construct the Grundy frequency vector directly from the closed form above: all even sizes contribute to Grundy \(0\), the pile \(1\) contributes to Grundy \(1\), and every odd size greater than \(1\) is placed into the bucket determined by the prime index of its smallest prime factor.
Next the implementation copies that frequency vector into a power-of-two buffer and applies the xor Walsh-Hadamard transform. Each transformed coefficient is raised to the \(K\)-th power modulo \(10^9+7\). After the inverse scaling step, the entry at index \(0\) is the number of losing positions. The C++ implementation also includes small brute-force cross-checks and fixed checkpoints to verify the closed form and the convolution result on manageable inputs, while keeping the main large-instance computation entirely in the fast pipeline.
Let \(L=N-1\), and let \(m\) be the smallest power of two with \(m\ge \pi(L)+1\). The linear sieve and the frequency construction take \(O(L)\) time. The Walsh-Hadamard transform takes \(O(m\log m)\) time, and the pointwise exponentiation takes \(O(m\log K)\) time because each coefficient is raised by binary exponentiation. The total memory usage is \(O(L+m)\), dominated in practice by the sieve arrays.
Für eine einzelne Kette der Größe \(n\) besteht ein Zug darin, eine Zahl \(a\) mit \(1 \le a \le n\) und \(\gcd(a,n)=1\) zu wählen und die Kette dann auf \(n-a\) zu verkleinern. Für feste Werte \(N\) und \(K\) betrachten wir geordnete \(K\)-Tupel von Haufengrößen aus \(\{1,2,\dots,N-1\}\). Gesucht ist die Anzahl der Verluststellungen, also genau derjenigen \(K\)-Haufen-Stellungen, deren xor der Grundy-Werte \(0\) ist, modulo \(10^9+7\).
Ein direkter Zustands-DP über alle \(K\)-Haufen-Stellungen ist für die Zielparameter viel zu groß. Daher bestimmt die Lösung zuerst die Ein-Haufen-Grundy-Werte vollständig und formt die Mehrhaufen-Zählung danach in ein XOR-Faltungsproblem um.
Sei \(g(n)\) der Grundy-Wert eines einzelnen Haufens der Größe \(n\). Aus der Zugregel folgt
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$$
Sobald die Verteilung dieser Werte auf \(\{1,\dots,N-1\}\) bekannt ist, reduziert das Sprague-Grundy-Theorem die Gesamtaufgabe auf das Zählen von XOR-Summen.
Die Stellung mit \(K\) Haufen \((x_1,\dots,x_K)\) ist genau dann verlierend, wenn
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
Der schwierige Teil ist also die Struktur von \(g(n)\) für einen einzelnen Haufen. Ist diese einmal verstanden, trägt jeder Haufen nur noch sein Grundy-Label bei, und das Restproblem ist rein kombinatorisch.
Die Implementierungen verwenden die geschlossene Formel
$$g(1)=1,$$
$$g(n)=0 \quad \text{für gerade } n,$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{für ungerade } n>1,$$
wobei \(\operatorname{spf}(n)\) den kleinsten Primfaktor von \(n\) bezeichnet und \(\pi(t)\) die Anzahl der Primzahlen bis \(t\) ist. Für eine Primzahl \(p\) ist \(\pi(p)\) also ihr \(1\)-basierter Primindex.
Diese Formel ergibt sich direkt aus der Zugstruktur:
Für \(n=1\) gibt es nur den Zug nach \(0\), also ist der mex gleich \(1\).
Ist \(n\) gerade, dann muss jedes zulässige \(a\) ungerade sein, also ist jeder erreichbare Wert \(n-a\) eine positive ungerade Zahl. Jede positive ungerade Zahl besitzt positiven Grundy-Wert. Daher fehlt \(0\) in der Zugmenge und es folgt \(g(n)=0\).
Sei nun \(n>1\) ungerade und \(p=\operatorname{spf}(n)\). Der Zug \(a=1\) führt zu \(n-1\), also zu einer geraden Zahl, und liefert damit den Grundy-Wert \(0\). Der Zug \(a=n-1\) führt zu \(1\), also ist auch der Wert \(1\) erreichbar. Allgemeiner ist für jede ungerade Primzahl \(q<p\) der Zug zum Haufen \(q\) legal, denn
$$\gcd(n,n-q)=\gcd(n,q)=1,$$
weil \(q\) kein Teiler von \(n\) ist. Das Ziel \(q\) hat den Grundy-Wert \(\pi(q)\). Somit treten alle Werte unterhalb von \(\pi(p)\) unter den legalen Zügen auf.
Dagegen kann kein legaler Zug auf eine ungerade Zahl landen, deren kleinster Primfaktor genau \(p\) ist. Gäbe es ein solches Ziel \(m\), dann würden sowohl \(n\) als auch \(m\) durch \(p\) teilbar sein, also
$$\gcd(n,n-m)=\gcd(n,m)\ge p,$$
im Widerspruch zur Koprimitätsbedingung des Zuges. Also fehlt der Grundy-Wert \(\pi(p)\), und der mex ist genau \(\pi(p)\).
Größere Grundy-Werte können unter Umständen ebenfalls als Kinder auftreten, sie beeinflussen den mex aber nicht mehr, sobald alle kleineren Werte vorhanden und \(\pi(p)\) selbst fehlend ist.
Definiere
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
Dann ist \(c_t\) genau die Anzahl der Haufengrößen mit Grundy-Label \(t\). Aus der obigen Klassifikation folgt sofort
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$$
denn genau die geraden Größen haben Grundy-Wert \(0\), sowie
$$c_1=1,$$
weil nur der Haufen \(1\) den Grundy-Wert \(1\) besitzt. Jedes ungerade \(x>1\) wird dem Eimer zugeordnet, der durch den Primindex seines kleinsten Primfaktors bestimmt ist.
Die Implementierungen gewinnen diese Häufigkeiten mit einem linearen Sieb, das für jede Zahl bis \(N-1\) den kleinsten Primfaktor und zusätzlich die laufende Primzahlzählfunktion \(\pi\) speichert.
Sei \(L(N,K)\) die Anzahl der verlierenden geordneten \(K\)-Tupel. Wenn ein Haufen den Grundy-Wert \(u\) auf \(c_u\) Arten liefert und ein anderer den Wert \(v\) auf \(c_v\) Arten, dann trägt das Paar den XOR-Wert \(u\oplus v\) bei. Genau das ist XOR-Faltung.
Für zwei Folgen \(f\) und \(h\) definieren wir
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$$
Die Verteilung der XOR-Summen für \(K\) Haufen ist daher die \(K\)-fache XOR-Faltung von \(c\) mit sich selbst, und die gesuchte Anzahl ist
$$L(N,K)=c^{(*K)}(0).$$
Das ist Sprague-Grundy in Zählform: Die Haufen werden unabhängig gewählt, und genau XOR-Summe \(0\) kennzeichnet eine Verluststellung.
Eine direkte Berechnung der \(K\)-fachen XOR-Faltung wäre noch zu langsam. Deshalb verwenden die Implementierungen die Walsh-Hadamard-Transformation für XOR-Faltung. Bezeichnet \(\widehat{c}\) die XOR-Transformierte von \(c\), dann gilt
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$$
Damit lautet der gesamte Rechenweg:
Den Häufigkeitsvektor auf eine Zweierpotenzlänge \(m\) auffüllen.
Die XOR-Walsh-Hadamard-Transformation anwenden.
Jede transformierte Komponente modulo \(10^9+7\) in die \(K\)-te Potenz erheben.
Dieselbe Transformation erneut anwenden.
Jeden Eintrag mit \(m^{-1}\pmod{10^9+7}\) multiplizieren, weil die XOR-Transformation bis auf den Faktor \(m\) selbstinvers ist.
Der Koeffizient an Index \(0\) ist dann genau \(L(N,K)\).
Für \(N=5\) sind die erlaubten Haufengrößen \(1,2,3,4\). Ihre Grundy-Werte lauten
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$$
Damit ist der Häufigkeitsvektor
$$c_0=2,\qquad c_1=1,\qquad c_2=1.$$
Bei zwei Haufen ist der XOR genau dann \(0\), wenn beide Haufen denselben Grundy-Wert besitzen. Also
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$$
Das stimmt mit dem Kontrollwert der Implementierung überein und zeigt anschaulich, warum nicht die Rohwerte der Haufen, sondern nur ihre Grundy-Häufigkeiten zählen.
Die C++-, Python- und Java-Implementierungen benutzen dieselbe Rechenkette. Zuerst wird bis \(N-1\) ein lineares Sieb aufgebaut, das für jede Zahl ihren kleinsten Primfaktor und zugleich die Primzahlanzahl-Präfixfunktion speichert, mit der ein kleinster Primfaktor in seinen Primindex übersetzt wird. Danach wird der Häufigkeitsvektor der Grundy-Werte direkt aus der geschlossenen Formel konstruiert: alle geraden Größen gehen in den Eimer für Grundy \(0\), der Haufen \(1\) in den Eimer für Grundy \(1\), und jedes ungerade \(x>1\) in den Eimer, der dem Primindex seines kleinsten Primfaktors entspricht.
Anschließend kopiert die Implementierung diesen Häufigkeitsvektor in einen Puffer mit Zweierpotenzlänge und führt die XOR-Walsh-Hadamard-Transformation aus. Jede transformierte Komponente wird modulo \(10^9+7\) in die \(K\)-te Potenz erhoben. Nach dem inversen Skalierungsschritt liefert der Eintrag an Position \(0\) die Anzahl der Verluststellungen. Die C++-Implementierung ergänzt dies noch durch kleine Brute-Force-Vergleiche und feste Kontrollwerte, um die geschlossene Formel und das Faltungsergebnis auf handhabbaren Eingaben zu verifizieren.
Setze \(L=N-1\), und sei \(m\) die kleinste Zweierpotenz mit \(m\ge \pi(L)+1\). Das lineare Sieb und der Aufbau der Häufigkeiten benötigen \(O(L)\) Zeit. Die Walsh-Hadamard-Transformation kostet \(O(m\log m)\) Zeit, und die komponentenweise Potenzierung \(O(m\log K)\), da binäre Exponentiation verwendet wird. Der gesamte Speicherbedarf ist \(O(L+m)\) und wird in der Praxis vom Sieb dominiert.
Tek bir yığın \(n\) büyüklüğündeyken hamle yapmak için \(1 \le a \le n\) ve \(\gcd(a,n)=1\) olacak bir sayı seçilir; ardından yığın \(n-a\) olur. Sabit \(N\) ve \(K\) için, \(\{1,2,\dots,N-1\}\) kümesinden seçilen sıralı \(K\)-li yığın durumlarını inceliyoruz. İstenen şey, Grundy değerlerinin xor toplamı \(0\) olan, yani kaybeden konumların sayısını \(10^9+7\) modunda bulmaktır.
Amaçlanan giriş boyutunda tüm \(K\)-yığınlı durumlar üzerinde doğrudan DP yapmak mümkün değildir. Bu yüzden çözüm önce tek yığın oyununun Grundy yapısını tamamen sınıflandırır, sonra çoklu yığın sayımını xor konvolüsyonuna dönüştürür.
\(g(n)\), boyutu \(n\) olan tek bir yığının Grundy değeri olsun. Hamle kuralı
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}$$
eşitliğini verir. \(\{1,\dots,N-1\}\) aralığındaki bu Grundy değerlerinin dağılımı bilindiğinde, Sprague-Grundy kuramı bütün problemi xor toplamlarını saymaya indirger.
\((x_1,\dots,x_K)\) biçimindeki \(K\) yığınlı bir konum tam ve ancak şu durumda kaybedendir:
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
Dolayısıyla asıl mesele, tek yığın için \(g(n)\)'nin yapısını anlamaktır. Bu yapı çözüldükten sonra her yığın sadece kendi Grundy etiketiyle temsil edilir ve geriye kalan iş tamamen kombinatorik hale gelir.
İmplementasyonların kullandığı kapalı form şudur:
$$g(1)=1,$$
$$g(n)=0 \quad \text{çift } n \text{ için},$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{tek } n>1 \text{ için}.$$
Burada \(\operatorname{spf}(n)\), \(n\)'in en küçük asal bölenidir; \(\pi(t)\) ise \(t\)'den küçük veya eşit asal sayıların sayısıdır. Dolayısıyla asal \(p\) için \(\pi(p)\), \(p\)'nin \(1\)-tabanlı asal indeksidir.
Bu formül hamle yapısından çıkar:
\(n=1\) için tek yasal hamle \(0\)'a gider; bu yüzden mex değeri \(1\)'dir.
\(n\) çift ise her yasal \(a\) tek olmak zorundadır; dolayısıyla her ulaşılabilir \(n-a\) değeri pozitif tek sayıdır. Her pozitif tek sayının Grundy değeri pozitiftir. Bu nedenle hamle kümesinde \(0\) yoktur ve \(g(n)=0\) olur.
Şimdi \(n>1\) tek olsun ve \(p=\operatorname{spf}(n)\) yazalım. \(a=1\) hamlesi \(n-1\)'e götürür; bu sayı çift olduğu için Grundy değeri \(0\) ulaşılabilirdir. \(a=n-1\) hamlesi \(1\)'e götürür; böylece Grundy değeri \(1\) de ulaşılabilirdir. Daha genel olarak, her \(q<p\) tek asalı için \(q\) yığınına inmek yasaldır, çünkü
$$\gcd(n,n-q)=\gcd(n,q)=1$$
olur; zira \(q\), \(n\)'i bölmez. Bu hedefin Grundy değeri \(\pi(q)\)'dir. Böylece \(\pi(p)\)'den küçük tüm değerler yasal hamleler arasında görülür.
Buna karşılık, en küçük asal böleni tam olarak \(p\) olan bir tek sayıya hiçbir yasal hamleyle inilemez. Böyle bir hedef \(m\) olsaydı hem \(n\) hem de \(m\), \(p\)'ye bölünürdü ve
$$\gcd(n,n-m)=\gcd(n,m)\ge p$$
olurdu; bu ise hamlenin aralarında asal olma şartına aykırıdır. Demek ki \(\pi(p)\) değeri eksiktir; dolayısıyla mex tam olarak \(\pi(p)\)'dir.
Daha büyük Grundy değerleri bazı hamlelerde görülebilir; ancak tüm daha küçük değerler mevcutken ve \(\pi(p)\) eksikken mex üzerinde etkileri kalmaz.
Şunu tanımlayalım:
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
Yani \(c_t\), Grundy etiketi \(t\) olan yığın boyutlarının sayısıdır. Yukarıdaki sınıflandırmadan hemen
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor$$
çıkar; çünkü Grundy değeri \(0\) olanlar tam olarak çift sayılardır. Ayrıca
$$c_1=1$$
olur; çünkü Grundy değeri \(1\) yalnızca \(1\) için görülür. \(1\)'den büyük her tek \(x\), en küçük asal böleninin asal indeksine karşılık gelen kovaya gider.
İmplementasyonlar bu kovaları, \(N-1\)'e kadar her tam sayı için en küçük asal böleni ve buna ek olarak \(\pi\) ön-ek dizisini üreten lineer sieve ile elde eder.
\(L(N,K)\), kaybeden sıralı \(K\)-li konumların sayısı olsun. Bir yığın \(u\) Grundy değerini \(c_u\) farklı boyutta üretiyor, başka bir yığın da \(v\) değerini \(c_v\) farklı boyutta üretiyorsa, bu ikili \(u\oplus v\) xor değerine katkı yapar. Bu tam olarak XOR konvolüsyonudur.
İki dizi \(f\) ve \(h\) için
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v)$$
tanımını yapalım. O halde \(K\) yığın için xor toplamlarının dağılımı, \(c\) dizisinin kendiyle \(K\)-kat XOR konvolüsyonudur ve istenen sayı
$$L(N,K)=c^{(*K)}(0)$$
olur. Bu, Sprague-Grundy teoreminin doğrudan sayım biçimidir: yığın seçimleri bağımsızdır ve kaybeden konum tam olarak xor toplamı \(0\) olan konumdur.
\(K\)-kat XOR konvolüsyonunu doğrudan kurmak yine yavaştır. Bu yüzden implementasyonlar XOR konvolüsyonu için Walsh-Hadamard dönüşümünü kullanır. \(c\)'nin XOR dönüşümü \(\widehat{c}\) ile gösterilirse
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K$$
eşitliği elde edilir. Böylece hesaplama şu hale gelir:
Frekans dizisini uzunluğu \(2\) kuvveti olan \(m\) boyutuna kadar sıfırlarla doldur.
XOR Walsh-Hadamard dönüşümünü uygula.
Dönüşmüş her bileşeni \(10^9+7\) modunda \(K\). kuvvete çıkar.
Aynı dönüşümü bir kez daha uygula.
XOR dönüşümü \(m\) katsayısına kadar kendi tersidir; bu yüzden tüm bileşenleri \(m^{-1}\pmod{10^9+7}\) ile çarp.
Sonra \(0\). indeks tam olarak \(L(N,K)\) değerini verir.
\(N=5\) için izinli yığın boyutları \(1,2,3,4\)'tür. Bunların Grundy değerleri
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0$$
olur. Dolayısıyla frekans vektörü
$$c_0=2,\qquad c_1=1,\qquad c_2=1$$
şeklindedir. İki yığınlı durumda xor toplamı ancak iki yığın aynı Grundy değerine sahipse \(0\) olur. Bu yüzden
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6$$
elde edilir. Bu değer implementasyondaki kontrol noktasıyla aynıdır ve problemin özünün ham yığın boyutları değil, Grundy frekans dağılımı olduğunu gösterir.
C++, Python ve Java implementasyonları aynı işlem hattını izler. Önce \(N-1\)'e kadar lineer sieve kurulur; burada her sayı için en küçük asal bölen ve bu böleni asal indeksine çevirmek için gereken asal sayma ön-eki tutulur. Sonra Grundy frekans vektörü kapalı formdan doğrudan üretilir: tüm çift boyutlar Grundy \(0\)'a, yığın \(1\) Grundy \(1\)'e, \(1\)'den büyük her tek sayı ise en küçük asal böleninin asal indeksine karşılık gelen kovaya eklenir.
Bundan sonra implementasyon, bu frekans vektörünü uzunluğu \(2\) kuvveti olan bir arabelleğe kopyalar ve XOR Walsh-Hadamard dönüşümünü uygular. Dönüşmüş her katsayı \(10^9+7\) modunda \(K\). kuvvete çıkarılır. Ters ölçekleme adımından sonra \(0\). konumdaki değer kaybeden durum sayısını verir. C++ implementasyonu ayrıca, kapalı form ile konvolüsyon sonucunu küçük girdiler üzerinde doğrulamak için brute-force karşılaştırmaları ve sabit kontrol değerleri de içerir.
\(L=N-1\) olsun; \(m\), \(m\ge \pi(L)+1\) koşulunu sağlayan en küçük \(2\) kuvveti olsun. Lineer sieve ve frekans üretimi \(O(L)\) zamanda tamamlanır. Walsh-Hadamard dönüşümü \(O(m\log m)\), noktasal üs alma ise ikili üs alma kullanıldığı için \(O(m\log K)\) zaman alır. Toplam bellek kullanımı \(O(L+m)\) olup pratikte baskın terim sieve dizileridir.
Para una pila de tamaño \(n\), un movimiento consiste en elegir un número \(a\) con \(1 \le a \le n\) y \(\gcd(a,n)=1\), y sustituir la pila por \(n-a\). Para valores fijos \(N\) y \(K\), consideramos \(K\)-tuplas ordenadas de tamaños de pila tomadas de \(\{1,2,\dots,N-1\}\). La tarea es contar cuántas de esas posiciones de \(K\) pilas son perdedoras, es decir, cuántas tienen xor de valores de Grundy igual a \(0\), y devolver el resultado módulo \(10^9+7\).
Un programa dinámico directo sobre todos los estados de \(K\) pilas es inviable para el tamaño real del problema. Por eso la solución primero clasifica por completo el juego de una pila y después transforma el conteo de varias pilas en un problema de convolución XOR.
Sea \(g(n)\) el valor de Grundy de una pila de tamaño \(n\). La regla de movimiento da
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$$
Una vez conocida la distribución de estos valores sobre \(\{1,\dots,N-1\}\), el teorema de Sprague-Grundy reduce el problema completo a contar sumas XOR.
La posición de \(K\) pilas \((x_1,\dots,x_K)\) es perdedora exactamente cuando
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
Así que la dificultad real está en entender \(g(n)\) para una sola pila. Una vez resuelto eso, cada pila aporta solo su etiqueta de Grundy y el resto del problema pasa a ser combinatorio.
Las implementaciones usan la forma cerrada
$$g(1)=1,$$
$$g(n)=0 \quad \text{para } n \text{ par},$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{para } n \text{ impar y } n>1,$$
donde \(\operatorname{spf}(n)\) es el menor factor primo de \(n\), y \(\pi(t)\) es el número de primos menores o iguales que \(t\). Para un primo \(p\), \(\pi(p)\) es por tanto su índice primo empezando en \(1\).
La justificación sale directamente de la estructura de movimientos:
Para \(n=1\), el único movimiento legal va a \(0\), así que el mex vale \(1\).
Si \(n\) es par, todo \(a\) legal debe ser impar; por tanto, todo valor alcanzable \(n-a\) es un número impar positivo. Todo impar positivo tiene valor de Grundy positivo. En consecuencia, \(0\) no aparece entre los hijos y se obtiene \(g(n)=0\).
Ahora sea \(n>1\) impar y escribamos \(p=\operatorname{spf}(n)\). El movimiento \(a=1\) lleva a \(n-1\), que es par, así que el valor \(0\) es alcanzable. El movimiento \(a=n-1\) lleva a \(1\), de modo que el valor \(1\) también es alcanzable. Más generalmente, para cada primo impar \(q<p\), el movimiento que lleva a la pila \(q\) es legal porque
$$\gcd(n,n-q)=\gcd(n,q)=1,$$
ya que \(q\) no divide a \(n\). Ese objetivo tiene valor de Grundy \(\pi(q)\). Por lo tanto, todos los valores menores que \(\pi(p)\) aparecen entre los movimientos legales.
En cambio, ningún movimiento legal puede llegar a un impar cuyo menor factor primo sea exactamente \(p\). Si existiera tal objetivo \(m\), entonces \(p\mid n\) y \(p\mid m\), así que
$$\gcd(n,n-m)=\gcd(n,m)\ge p,$$
lo cual contradice la condición de coprimalidad del movimiento. Por eso el valor \(\pi(p)\) está ausente y el mex es exactamente \(\pi(p)\).
Pueden aparecer valores de Grundy mayores entre algunos hijos, pero ya no afectan al mex una vez que todos los menores están presentes y \(\pi(p)\) falta.
Definimos
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
Entonces \(c_t\) es la cantidad de tamaños de pila con etiqueta de Grundy \(t\). La clasificación anterior implica inmediatamente
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$$
porque exactamente los tamaños pares tienen valor \(0\), y también
$$c_1=1,$$
porque la única pila con valor de Grundy \(1\) es \(1\). Cada impar \(x>1\) se coloca en el grupo determinado por el índice primo de su menor factor primo.
Las implementaciones obtienen estas frecuencias con una criba lineal que almacena para cada entero hasta \(N-1\) su menor factor primo y, además, la función prefijo \(\pi\).
Sea \(L(N,K)\) el número de \(K\)-tuplas ordenadas perdedoras. Si una pila aporta el valor de Grundy \(u\) de \(c_u\) maneras y otra aporta \(v\) de \(c_v\) maneras, entonces el par aporta el xor \(u\oplus v\). Eso es exactamente una convolución XOR.
Para dos secuencias \(f\) y \(h\), definimos
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$$
Por tanto, la distribución de xores para \(K\) pilas es la convolución XOR \(K\)-veces de \(c\) consigo misma, y la cantidad buscada es
$$L(N,K)=c^{(*K)}(0).$$
Esta identidad no es más que el teorema de Sprague-Grundy expresado como conteo: las elecciones de las pilas son independientes y una posición es perdedora exactamente cuando el xor total es \(0\).
Formar directamente la convolución XOR \(K\) veces todavía sería demasiado lento. Por eso las implementaciones usan la transformada de Walsh-Hadamard para convolución XOR. Si \(\widehat{c}\) denota la transformada XOR de \(c\), entonces
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$$
Así, todo el cálculo queda reducido a:
Rellenar el vector de frecuencias hasta una longitud \(m\) que sea potencia de \(2\).
Aplicar la transformada XOR de Walsh-Hadamard.
Elevar cada componente transformada a la potencia \(K\) módulo \(10^9+7\).
Aplicar otra vez la misma transformada.
Multiplicar cada entrada por \(m^{-1}\pmod{10^9+7}\), porque para XOR la transformada es su propia inversa salvo por el factor \(m\).
La entrada de índice \(0\) es entonces exactamente \(L(N,K)\).
Para \(N=5\), los tamaños permitidos son \(1,2,3,4\). Sus valores de Grundy son
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$$
Por tanto, el vector de frecuencias es
$$c_0=2,\qquad c_1=1,\qquad c_2=1.$$
Con dos pilas, el xor vale \(0\) exactamente cuando ambas pilas tienen el mismo valor de Grundy, de modo que
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$$
Esto coincide con el punto de control usado por la implementación y muestra por qué el problema queda gobernado por la distribución de Grundy y no por los tamaños brutos de las pilas.
Las implementaciones en C++, Python y Java siguen la misma secuencia. Primero construyen una criba lineal hasta \(N-1\), almacenando para cada número su menor factor primo y también el prefijo de conteo de primos necesario para convertir ese menor factor primo en su índice primo. Después construyen directamente el vector de frecuencias de Grundy a partir de la forma cerrada: todos los tamaños pares contribuyen a Grundy \(0\), la pila \(1\) contribuye a Grundy \(1\), y cada tamaño impar mayor que \(1\) se envía al grupo determinado por el índice primo de su menor factor primo.
A continuación, la implementación copia ese vector a un búfer de longitud potencia de \(2\) y aplica la transformada XOR de Walsh-Hadamard. Cada coeficiente transformado se eleva a la potencia \(K\) módulo \(10^9+7\). Tras el paso de escala inversa, la entrada de índice \(0\) da el número de posiciones perdedoras. La implementación en C++ además incorpora comparaciones por fuerza bruta en tamaños pequeños y varios valores de control fijos para verificar tanto la forma cerrada como el resultado de la convolución en casos manejables.
Sea \(L=N-1\), y sea \(m\) la menor potencia de \(2\) que satisface \(m\ge \pi(L)+1\). La criba lineal y la construcción de frecuencias cuestan \(O(L)\) tiempo. La transformada de Walsh-Hadamard cuesta \(O(m\log m)\) tiempo, y la potenciación punto a punto cuesta \(O(m\log K)\) al usar exponenciación binaria. La memoria total es \(O(L+m)\), dominada en la práctica por los arreglos de la criba.
对一个大小为 \(n\) 的单堆，合法操作是选择一个满足 \(1 \le a \le n\) 且 \(\gcd(a,n)=1\) 的整数 \(a\)，然后把该堆变成 \(n-a\)。对固定的 \(N\) 和 \(K\)，我们考察所有从 \(\{1,2,\dots,N-1\}\) 中选出的有序 \(K\) 元组作为堆大小。题目要求统计其中多少个 \(K\) 堆局面是必败态，也就是这些堆的 Grundy 值异或和等于 \(0\) 的局面，并对 \(10^9+7\) 取模。
如果直接在所有 \(K\) 堆状态上做动态规划，规模会大得无法承受。因此解法先把单堆游戏的 Grundy 结构完全刻画出来，再把多堆计数转化为异或卷积问题。
设 \(g(n)\) 表示大小为 \(n\) 的单堆的 Grundy 值。根据操作规则，有
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$$
一旦我们知道 \(\{1,\dots,N-1\}\) 上这些 Grundy 值的分布，Sprague-Grundy 定理就会把整个题目化简为对异或和的计数。
一个 \(K\) 堆局面 \((x_1,\dots,x_K)\) 是必败态，当且仅当
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
因此真正的核心是理解单堆函数 \(g(n)\)。只要单堆结构被完全掌握，每一堆就只需要用自己的 Grundy 标签表示，剩下的问题便是纯粹的组合计数。
三个实现所依据的闭式结论是
$$g(1)=1,$$
$$g(n)=0 \quad \text{当 } n \text{ 为偶数时},$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{当 } n \text{ 为奇数且 } n>1 \text{ 时}.$$
这里 \(\operatorname{spf}(n)\) 表示 \(n\) 的最小质因子，\(\pi(t)\) 表示不超过 \(t\) 的质数个数。对质数 \(p\) 来说，\(\pi(p)\) 就是它从 \(1\) 开始计数的质数序号。
这个结论可以直接从操作规则推出：
当 \(n=1\) 时，唯一合法操作是走到 \(0\)，所以 mex 为 \(1\)。
若 \(n\) 为偶数，那么任何与 \(n\) 互素的 \(a\) 都必须是奇数，因此所有可达状态 \(n-a\) 都是正奇数。每个正奇数状态的 Grundy 值都大于 \(0\)。于是可达集合中没有 \(0\)，从而 \(g(n)=0\)。
再看奇数 \(n>1\)。记 \(p=\operatorname{spf}(n)\)。取 \(a=1\) 时会到达 \(n-1\)，它是偶数，因此 Grundy 值 \(0\) 可以到达。取 \(a=n-1\) 时会到达 \(1\)，所以 Grundy 值 \(1\) 也可以到达。更一般地，对每个满足 \(q<p\) 的奇质数 \(q\)，都可以合法地走到大小为 \(q\) 的堆，因为
$$\gcd(n,n-q)=\gcd(n,q)=1,$$
这是由于 \(q\) 不是 \(n\) 的因子。该目标堆的 Grundy 值就是 \(\pi(q)\)。因此所有严格小于 \(\pi(p)\) 的值都会出现在合法后继中。
另一方面，不可能合法地走到一个最小质因子恰好等于 \(p\) 的奇数。如果存在这样的目标 \(m\)，那么 \(p\mid n\) 且 \(p\mid m\)，于是
$$\gcd(n,n-m)=\gcd(n,m)\ge p,$$
这与操作要求 \(\gcd(a,n)=1\) 相矛盾。所以值 \(\pi(p)\) 在后继中缺失，mex 恰好就是 \(\pi(p)\)。
某些后继可能还会出现更大的 Grundy 值，但只要所有更小的值都已经出现、而 \(\pi(p)\) 缺失，这些更大的值就不会影响 mex。
定义
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
也就是说，\(c_t\) 是 Grundy 值等于 \(t\) 的堆大小个数。由上面的分类可立即得到
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$$
因为恰好所有偶数堆大小对应 Grundy 值 \(0\)；同时
$$c_1=1,$$
因为 Grundy 值 \(1\) 只在堆大小 \(1\) 处出现。每个大于 \(1\) 的奇数 \(x\)，都会被归入由其最小质因子的质数序号决定的桶中。
实现中通过线性筛来得到这些桶：对每个不超过 \(N-1\) 的整数，记录其最小质因子，并同时维护前缀质数计数函数 \(\pi\)。
记 \(L(N,K)\) 为必败的有序 \(K\) 元组数量。如果一堆能以 \(c_u\) 种方式提供 Grundy 值 \(u\)，另一堆能以 \(c_v\) 种方式提供值 \(v\)，那么这一对对异或和 \(u\oplus v\) 的贡献就是 \(c_u c_v\)。这正是 XOR 卷积。
对两个序列 \(f\) 和 \(h\)，定义
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$$
于是，\(K\) 堆的异或和分布就是频率向量 \(c\) 自身的 \(K\) 次 XOR 卷积，而题目所求正是
$$L(N,K)=c^{(*K)}(0).$$
这只是把 Sprague-Grundy 定理翻译成计数语言：各堆的选择彼此独立，而局面必败当且仅当所有 Grundy 值的异或和为 \(0\)。
如果直接做 \(K\) 次 XOR 卷积，速度仍然不够。于是实现改用适合 XOR 卷积的 Walsh-Hadamard 变换。设 \(\widehat{c}\) 是 \(c\) 的 XOR 变换，则有
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$$
因此整个计算过程变成：
把频率向量补零到长度为 \(2\) 的幂的 \(m\)。
进行 XOR Walsh-Hadamard 正变换。
将每个变换后的分量都在模 \(10^9+7\) 下提升到 \(K\) 次幂。
再次执行同样的变换。
由于 XOR 情形下该变换除去一个系数 \(m\) 外就是自逆的，所以最后还要把每个分量乘上 \(m^{-1}\pmod{10^9+7}\)。
此时下标 \(0\) 处的值就恰好是 \(L(N,K)\)。
当 \(N=5\) 时，可选的堆大小为 \(1,2,3,4\)。它们的 Grundy 值分别是
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$$
因此频率向量为
$$c_0=2,\qquad c_1=1,\qquad c_2=1.$$
对于两堆情形，异或和为 \(0\) 当且仅当两堆的 Grundy 值相同，所以
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$$
这与实现中使用的校验值一致，也说明了为什么真正决定答案的是 Grundy 值的频率分布，而不是堆大小本身的原始数值。
C++、Python 和 Java 实现遵循同一条流水线。首先，它们在线性筛中处理到 \(N-1\)，为每个整数保存最小质因子，并同时维护质数计数前缀，从而把最小质因子转换成对应的质数序号。接着，程序直接根据上面的闭式构造 Grundy 频率向量：所有偶数大小归入 Grundy \(0\)，大小为 \(1\) 的堆归入 Grundy \(1\)，每个大于 \(1\) 的奇数则归入由其最小质因子质数序号决定的桶中。
之后，实现把频率向量复制到一个长度为 \(2\) 的幂的缓冲区，执行 XOR Walsh-Hadamard 变换。每个变换后的系数都在模 \(10^9+7\) 下做 \(K\) 次幂，再执行一次同样的变换，并进行逆向缩放。最终下标 \(0\) 的值就是必败局面的数量。C++ 实现还额外包含了若干小规模暴力对照和固定检查点，用来确认单堆闭式以及卷积结果在可控输入上的正确性。
令 \(L=N-1\)，再令 \(m\) 为满足 \(m\ge \pi(L)+1\) 的最小 \(2\) 的幂。线性筛和频率构造的时间复杂度都是 \(O(L)\)。Walsh-Hadamard 变换需要 \(O(m\log m)\) 时间，逐点快速幂需要 \(O(m\log K)\) 时间。总空间复杂度为 \(O(L+m)\)，实际中主要由筛法数组占据。
Для одной кучи размера \(n\) ход состоит в выборе числа \(a\), удовлетворяющего условиям \(1 \le a \le n\) и \(\gcd(a,n)=1\), после чего куча уменьшается до \(n-a\). Для фиксированных \(N\) и \(K\) рассматриваются упорядоченные \(K\)-кортежи размеров куч из множества \(\{1,2,\dots,N-1\}\). Нужно посчитать, сколько таких позиций из \(K\) куч являются проигрышными, то есть имеют xor значений Гранди, равный \(0\), и вернуть ответ по модулю \(10^9+7\).
Прямой динамический подсчет по всем состояниям \(K\) куч для реальных параметров невозможен. Поэтому решение сначала полностью описывает игру с одной кучей, а затем превращает многокучный подсчет в задачу XOR-свертки.
Пусть \(g(n)\) обозначает значение Гранди для одной кучи размера \(n\). Из правила хода следует
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$$
Как только распределение этих значений на \(\{1,\dots,N-1\}\) известно, теорема Шпрага-Гранди сводит всю задачу к подсчету xor-сумм.
Позиция из \(K\) куч \((x_1,\dots,x_K)\) проигрышна тогда и только тогда, когда
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
Значит, главное препятствие состоит в понимании функции \(g(n)\) для одной кучи. После этого каждая куча описывается лишь своей меткой Гранди, а оставшаяся часть задачи становится чисто комбинаторной.
Реализации используют замкнутую формулу
$$g(1)=1,$$
$$g(n)=0 \quad \text{для четных } n,$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{для нечетных } n>1,$$
где \(\operatorname{spf}(n)\) означает наименьший простой делитель числа \(n\), а \(\pi(t)\) обозначает количество простых чисел, не превосходящих \(t\). Для простого \(p\) число \(\pi(p)\) есть его индекс среди простых, начиная с \(1\).
Эта формула вытекает из структуры ходов:
Для \(n=1\) единственный легальный ход ведет в \(0\), поэтому mex равен \(1\).
Если \(n\) четно, любое допустимое \(a\) обязательно нечетно, следовательно, каждое достижимое состояние \(n-a\) является положительным нечетным числом. Любое положительное нечетное состояние имеет положительное значение Гранди. Значит, \(0\) отсутствует среди потомков и потому \(g(n)=0\).
Пусть теперь \(n>1\) нечетно, а \(p=\operatorname{spf}(n)\). Ход \(a=1\) приводит в \(n-1\), то есть в четное число, и тем самым делает достижимым значение \(0\). Ход \(a=n-1\) приводит в \(1\), так что достижимо и значение \(1\). Более того, для каждого нечетного простого \(q<p\) ход в кучу размера \(q\) легален, потому что
$$\gcd(n,n-q)=\gcd(n,q)=1,$$
так как \(q\) не делит \(n\). У этой цели значение Гранди равно \(\pi(q)\). Следовательно, среди легальных ходов встречаются все значения меньше \(\pi(p)\).
Напротив, ни один легальный ход не может привести к нечетному числу, у которого наименьший простой делитель равен \(p\). Если бы такая цель \(m\) существовала, то \(p\mid n\) и \(p\mid m\), а значит,
$$\gcd(n,n-m)=\gcd(n,m)\ge p,$$
что противоречит условию взаимной простоты в ходе. Значение \(\pi(p)\) отсутствует, и потому mex равен ровно \(\pi(p)\).
Некоторые потомки могут иметь и большие значения Гранди, но после появления всех меньших значений и отсутствия \(\pi(p)\) они уже не влияют на mex.
Определим
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
Тогда \(c_t\) есть число размеров куч с меткой Гранди \(t\). Из классификации сразу следует
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$$
поскольку ровно четные размеры дают значение \(0\), а также
$$c_1=1,$$
поскольку значение \(1\) имеет только куча размера \(1\). Каждое нечетное \(x>1\) попадает в корзину, определяемую индексом наименьшего простого делителя.
Реализации получают эти частоты с помощью линейного решета, которое хранит для каждого числа до \(N-1\) его наименьший простой делитель и одновременно префиксную функцию подсчета простых \(\pi\).
Пусть \(L(N,K)\) обозначает число проигрышных упорядоченных \(K\)-кортежей. Если одна куча дает значение Гранди \(u\) \(c_u\) способами, а другая дает значение \(v\) \(c_v\) способами, то пара вносит вклад в xor-значение \(u\oplus v\). Это и есть XOR-свертка.
Для двух последовательностей \(f\) и \(h\) зададим
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$$
Следовательно, распределение xor-сумм для \(K\) куч есть \(K\)-кратная XOR-свертка вектора \(c\) с самим собой, а искомое число равно
$$L(N,K)=c^{(*K)}(0).$$
Это просто формулировка теоремы Шпрага-Гранди на языке подсчета: выборы куч независимы, а позиция проигрышна тогда и только тогда, когда общий xor равен \(0\).
Непосредственно строить \(K\)-кратную XOR-свертку все еще слишком дорого. Поэтому реализации используют преобразование Уолша-Адамара для XOR-свертки. Если \(\widehat{c}\) обозначает XOR-преобразование вектора \(c\), то
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$$
Тем самым весь алгоритм становится таким:
Дополнить вектор частот нулями до длины \(m\), являющейся степенью двойки.
Применить XOR-преобразование Уолша-Адамара.
Возвести каждую преобразованную компоненту в степень \(K\) по модулю \(10^9+7\).
Снова применить то же преобразование.
Умножить все значения на \(m^{-1}\pmod{10^9+7}\), поскольку в случае XOR это преобразование обратно к самому себе с точностью до множителя \(m\).
Коэффициент с индексом \(0\) и есть \(L(N,K)\).
При \(N=5\) допустимые размеры куч равны \(1,2,3,4\). Их значения Гранди таковы:
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$$
Следовательно, вектор частот равен
$$c_0=2,\qquad c_1=1,\qquad c_2=1.$$
Для двух куч xor равен \(0\) тогда и только тогда, когда обе кучи имеют одинаковое значение Гранди, поэтому
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$$
Это совпадает с контрольным значением в реализации и наглядно показывает, почему ответ определяется именно распределением значений Гранди, а не исходными размерами куч.
Реализации на C++, Python и Java используют один и тот же конвейер. Сначала они строят линейное решето до \(N-1\), сохраняя для каждого числа его наименьший простой делитель и одновременно префикс подсчета простых, который переводит этот делитель в его индекс среди простых. Затем они напрямую формируют вектор частот значений Гранди из замкнутой формулы: все четные размеры отправляются в корзину для Grundy \(0\), куча размера \(1\) дает Grundy \(1\), а каждое нечетное число больше \(1\) попадает в корзину, определяемую индексом его наименьшего простого делителя.
После этого реализация копирует вектор частот в буфер длины степени двойки и применяет XOR-преобразование Уолша-Адамара. Каждая преобразованная компонента возводится в степень \(K\) по модулю \(10^9+7\). После обратного масштабирования значение в позиции \(0\) дает число проигрышных позиций. Реализация на C++ дополнительно включает малые переборные проверки и фиксированные контрольные точки, чтобы подтвердить формулу для одной кучи и результат свертки на небольших примерах.
Положим \(L=N-1\), а через \(m\) обозначим минимальную степень двойки, удовлетворяющую \(m\ge \pi(L)+1\). Линейное решето и построение частот требуют \(O(L)\) времени. Преобразование Уолша-Адамара работает за \(O(m\log m)\), а покомпонентное возведение в степень требует \(O(m\log K)\) благодаря бинарному быстрому возведению в степень. Общая память равна \(O(L+m)\) и на практике определяется главным образом массивами решета.
في كومة واحدة حجمها \(n\)، تتكوّن الحركة القانونية من اختيار عدد \(a\) بحيث \(1 \le a \le n\) و\(\gcd(a,n)=1\)، ثم تصبح الكومة بحجم \(n-a\). عند تثبيت \(N\) و\(K\)، ننظر إلى جميع الترتيبات المرتبة ذات \(K\) أكوام، حيث يؤخذ حجم كل كومة من المجموعة \(\{1,2,\dots,N-1\}\). المطلوب هو عدّ عدد الأوضاع الخاسرة، أي الأوضاع التي يكون فيها XOR لقيم Grundy مساويًا للصفر، مع أخذ النتيجة بترديد \(10^9+7\).
العد المباشر على جميع أوضاع \(K\) أكوام غير عملي إطلاقًا عند القيم الكبيرة المقصودة. لذلك يبدأ الحل بفهم لعبة الكومة الواحدة بالكامل، ثم يحوّل عدّ الأوضاع متعددة الأكوام إلى مسألة التفاف XOR.
لنرمز إلى قيمة Grundy لكومة واحدة بالحجم \(n\) بالرمز \(g(n)\). من قاعدة الحركة نحصل على
$$g(n)=\operatorname{mex}\left\{g(n-a): 1 \le a \le n,\ \gcd(a,n)=1\right\}.$$
وبمجرد معرفة توزيع هذه القيم على المجموعة \(\{1,\dots,N-1\}\)، فإن مبرهنة Sprague-Grundy تختزل المسألة كلها إلى عدّ مجاميع XOR.
الوضع المكوّن من \(K\) أكوام \((x_1,\dots,x_K)\) يكون خاسرًا إذا وفقط إذا تحقق
$$g(x_1)\oplus g(x_2)\oplus \cdots \oplus g(x_K)=0.$$
إذًا جوهر المسألة هو فهم \(g(n)\) لكومة واحدة. بعد ذلك، لا يهم كل كومة إلا من خلال وسم Grundy الخاص بها، وتتحول بقية المهمة إلى حسابات توافقية بحتة.
الصيغة المغلقة التي تعتمدها التطبيقات هي
$$g(1)=1,$$
$$g(n)=0 \quad \text{for even } n,$$
$$g(n)=\pi(\operatorname{spf}(n)) \quad \text{for odd } n>1.$$
هنا ترمز \(\operatorname{spf}(n)\) إلى أصغر عامل أولي للعدد \(n\)، بينما \(\pi(t)\) تمثل عدد الأعداد الأولية التي لا تتجاوز \(t\). لذلك إذا كان \(p\) عددًا أوليًا فإن \(\pi(p)\) هو ترتيبه بين الأعداد الأولية بدءًا من \(1\).
هذه الصيغة ناتجة مباشرة من بنية الحركات:
عندما \(n=1\)، فالحركة القانونية الوحيدة تذهب إلى \(0\)، ولذلك تكون قيمة mex مساوية لـ \(1\).
إذا كان \(n\) زوجيًا، فإن أي \(a\) قانوني لا بد أن يكون فرديًا، ومن ثم فإن كل حالة يمكن الوصول إليها \(n-a\) تكون عددًا فرديًا موجبًا. وكل حالة فردية موجبة لها قيمة Grundy موجبة. لذلك لا تظهر القيمة \(0\) بين الأبناء، ومن ثم \(g(n)=0\).
الآن ليكن \(n>1\) فرديًا، ولنكتب \(p=\operatorname{spf}(n)\). الحركة \(a=1\) تصل إلى \(n-1\)، وهو عدد زوجي، وبالتالي فإن القيمة \(0\) قابلة للوصول. والحركة \(a=n-1\) تصل إلى \(1\)، ولذلك فإن القيمة \(1\) قابلة للوصول أيضًا. وبشكل أعم، لكل عدد أولي فردي \(q<p\)، تكون الحركة إلى الكومة \(q\) قانونية لأن
$$\gcd(n,n-q)=\gcd(n,q)=1,$$
وذلك لأن \(q\) لا يقسم \(n\). والهدف \(q\) يحمل قيمة Grundy مساوية لـ \(\pi(q)\). إذًا تظهر كل القيم الأصغر من \(\pi(p)\) بين الحركات القانونية.
أما القيمة \(\pi(p)\) نفسها فلا يمكن أن تظهر. فلو وُجد هدف فردي \(m\) أصغر عامل أولي له هو \(p\)، لكان \(p\mid n\) و\(p\mid m\)، وبالتالي
$$\gcd(n,n-m)=\gcd(n,m)\ge p,$$
وهو تناقض مع شرط أن تكون الحركة أولية نسبيًا مع \(n\). لذلك تغيب القيمة \(\pi(p)\)، ومن ثم يكون mex مساويًا لها تمامًا.
قد تظهر قيم Grundy أكبر ضمن بعض الأبناء، لكنها لا تؤثر في mex بعد أن تكون كل القيم الأصغر موجودة بينما تظل \(\pi(p)\) غائبة.
نعرّف
$$c_t=\#\left\{x\in\{1,\dots,N-1\}: g(x)=t\right\}.$$
إذًا \(c_t\) هو عدد أحجام الأكوام التي تحمل وسم Grundy مقداره \(t\). ومن التصنيف السابق نحصل مباشرة على
$$c_0=\left\lfloor\frac{N-1}{2}\right\rfloor,$$
لأن الأحجام الزوجية وحدها هي التي تعطي القيمة \(0\)، كما أن
$$c_1=1,$$
لأن الكومة الوحيدة ذات القيمة \(1\) هي الكومة ذات الحجم \(1\). وكل عدد فردي \(x>1\) يُرسل إلى الفئة التي يحددها ترتيب أصغر عامل أولي له.
وتحصل التطبيقات على هذه التكرارات باستخدام منخل خطي يخزن لكل عدد حتى \(N-1\) أصغر عامل أولي له، إلى جانب دالة العد التراكمية للأعداد الأولية \(\pi\).
لنرمز إلى عدد الترتيبات الخاسرة المرتبة ذات \(K\) أكوام بالرمز \(L(N,K)\). إذا كانت كومة واحدة تعطي قيمة Grundy مقدارها \(u\) بعدد \(c_u\) من الأحجام، وكومة أخرى تعطي القيمة \(v\) بعدد \(c_v\) من الأحجام، فإن الزوج يساهم في قيمة XOR مقدارها \(u\oplus v\). وهذا بالضبط هو التفاف XOR.
لأي سلسلتين \(f\) و\(h\) نعرّف
$$\left(f *_{\oplus} h\right)(s)=\sum_{u\oplus v=s} f(u)h(v).$$
وبالتالي فإن توزيع مجاميع XOR لعدد \(K\) من الأكوام هو التفاف XOR للمتجه \(c\) مع نفسه \(K\) مرة، والعدد المطلوب هو
$$L(N,K)=c^{(*K)}(0).$$
هذا مجرد ترجمة لمبرهنة Sprague-Grundy إلى لغة العد: اختيارات الأكوام مستقلة، والوضع خاسر بالضبط عندما يكون XOR الكلي مساويًا للصفر.
تنفيذ التفاف XOR عدد \(K\) من المرات مباشرة ما يزال بطيئًا. لذلك تستخدم التطبيقات تحويل Walsh-Hadamard الخاص بتفاف XOR. إذا رمزنا إلى تحويل \(c\) بالرمز \(\widehat{c}\)، فإن
$$\widehat{c^{(*K)}}(i)=\widehat{c}(i)^K.$$
وهكذا يصبح الحساب كله كالتالي:
توسيع متجه التكرارات بالأصفار حتى يصل إلى طول \(m\) وهو قوة للعدد \(2\).
تطبيق تحويل XOR Walsh-Hadamard.
رفع كل مركبة محوّلة إلى القوة \(K\) بترديد \(10^9+7\).
تطبيق التحويل نفسه مرة ثانية.
ضرب كل القيم في \(m^{-1}\pmod{10^9+7}\)، لأن هذا التحويل في حالة XOR يعكس نفسه حتى عامل القياس \(m\).
بعد ذلك تكون المركبة ذات الفهرس \(0\) مساوية تمامًا لـ \(L(N,K)\).
عندما \(N=5\)، تكون أحجام الأكوام المسموح بها هي \(1,2,3,4\). قيم Grundy المقابلة لها هي
$$g(1)=1,\qquad g(2)=0,\qquad g(3)=2,\qquad g(4)=0.$$
ومن ثم يكون متجه التكرارات
$$c_0=2,\qquad c_1=1,\qquad c_2=1.$$
في حالة كومتين، يكون XOR مساويًا للصفر إذا وفقط إذا امتلكت الكومتان القيمة نفسها من Grundy، ولذلك
$$L(5,2)=c_0^2+c_1^2+c_2^2=2^2+1^2+1^2=6.$$
وهذا يطابق نقطة التحقق المستخدمة في التنفيذ، ويبيّن بوضوح أن المسألة تتحكم فيها تكرارات قيم Grundy لا القيم الخام لأحجام الأكوام نفسها.
تتبع تطبيقات C++ وPython وJava المسار نفسه. أولًا، تبني منخلًا خطيًا حتى \(N-1\)، وتخزن لكل عدد أصغر عامل أولي له، كما تحفظ العد التراكمي للأعداد الأولية اللازم لتحويل هذا العامل إلى ترتيبه بين الأعداد الأولية. بعد ذلك تُبنى متجهات التكرار مباشرة من الصيغة المغلقة السابقة: كل الأحجام الزوجية تضاف إلى فئة Grundy \(0\)، والحجم \(1\) يذهب إلى فئة Grundy \(1\)، وكل حجم فردي أكبر من \(1\) يذهب إلى الفئة التي يحددها ترتيب أصغر عامل أولي له.
ثم تنسخ الشيفرة متجه التكرارات إلى مصفوفة طولها قوة للعدد \(2\)، وتطبق تحويل XOR Walsh-Hadamard. بعد ذلك تُرفع كل مركبة محوّلة إلى القوة \(K\) بترديد \(10^9+7\). وبعد خطوة القياس العكسي، تعطي الخانة ذات الفهرس \(0\) عدد الأوضاع الخاسرة. كما أن تنفيذ C++ يتضمن فحوصًا صغيرة بالقوة الغاشمة ونقاط تحقق ثابتة للتأكد من صحة الصيغة المغلقة ونتيجة الالتفاف على مدخلات صغيرة يمكن السيطرة عليها.
لنضع \(L=N-1\)، ولتكن \(m\) أصغر قوة للعدد \(2\) تحقق \(m\ge \pi(L)+1\). المنخل الخطي وبناء التكرارات يحتاجان إلى زمن \(O(L)\). أما تحويل Walsh-Hadamard فيحتاج إلى \(O(m\log m)\)، والرفع النقطي إلى القوى يحتاج إلى \(O(m\log K)\) باستعمال الأس السريع الثنائي. واستهلاك الذاكرة الكلي هو \(O(L+m)\)، ويهيمن عليه عمليًا تخزين بيانات المنخل.