In Divisor Nim, a move on a pile of size \(n\) chooses a proper divisor \(d\lt n\) and replaces the pile by \(n-d\). With three independent piles \((a,b,c)\), let \(S(N)\) be the number of winning starting triples with \(1\le a,b,c\le N\). The goal is to compute \(S(123456787654321)\) modulo \(1234567890\).
A direct search over all \(N^3\) triples is impossible. The key simplification is that the single-pile Sprague-Grundy value depends only on the exponent of 2 in the pile size, so the whole three-pile count becomes a short xor-based sum over valuation buckets.
Let \(g(n)\) denote the Sprague-Grundy value of one pile of size \(n\), and let \(M=1234567890\). The problem is to count three-pile positions whose xor is nonzero.
Divisor Nim is an impartial normal-play game, so the Sprague-Grundy theorem applies. Therefore
$$\text{the position }(a,b,c)\text{ is losing} \iff g(a)\oplus g(b)\oplus g(c)=0.$$
Once the single-pile function \(g(n)\) is known, the rest of the problem is just counting how often each Grundy value appears among the integers from \(1\) to \(N\).
Write
$$n=2^e q,\qquad q\text{ odd},\qquad e=v_2(n).$$
Any proper divisor of \(n\) has the form
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
with \((a,b)\ne (e,q)\) because \(d\lt n\).
If \(a\lt e\), then
$$n-d=2^a\left(2^{e-a}q-b\right).$$
Here \(2^{e-a}q\) is even and \(b\) is odd, so the bracket is odd. Hence
$$v_2(n-d)=a.$$
If \(a=e\), then \(d=2^e b\) with \(b\lt q\), so
$$n-d=2^e(q-b).$$
Both \(q\) and \(b\) are odd, so \(q-b\) is a positive even number. Therefore
$$v_2(n-d)>e.$$
So a move from \(n\) can reach every valuation \(0,1,\dots,e-1\), can sometimes reach valuations larger than \(e\), but can never reach valuation \(e\) itself. In particular, for each \(0\le a\lt e\), choosing \(d=2^a q\) gives
$$n-d=2^a q\left(2^{e-a}-1\right),$$
and the factor \(2^{e-a}-1\) is odd, so \(v_2(n-d)=a\).
Now induct on \(n\). Every move goes to a smaller pile, so the reachable Grundy values are exactly the reachable valuations of smaller positions. They include \(0,1,\dots,e-1\), they do not include \(e\), and any larger values do not change the mex. Thus
$$g(n)=e=v_2(n).$$
For odd \(n\), this says \(g(n)=0\), which is consistent because every move from an odd pile lands on an even pile.
Define
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$$
The integers with \(v_2(x)\ge k\) are exactly the multiples of \(2^k\), so
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Only finitely many buckets are nonzero. Once \(2^k>N\), the count vanishes, so only \(k\le \lfloor\log_2 N\rfloor\) matter.
A starting triple is losing exactly when
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
If the first two valuations are \(i\) and \(j\), then the third must be \(i\oplus j\). Therefore the number of losing triples is
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$$
The total number of triples is \(N^3\), so the winning count is
$$S(N)=N^3-L(N),$$
and the reported answer is \(S(N)\pmod{M}\).
For \(1\le x\le 10\), the buckets are
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$$
coming from the sets
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
Then
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$$
Since \(10^3=1000\), we obtain
$$S(10)=1000-308=692,$$
which matches the checkpoint used by the implementation.
The C++, Python, and Java implementations do not explore game trees. Instead, they first count how many integers in \([1,N]\) have valuation \(0,1,2,\dots\) using repeated divisions by powers of 2, which realizes
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
They then run a double loop over the nonzero buckets. For each pair \((i,j)\), they compute \(k=i\oplus j\) and add the contribution \(C_iC_jC_k\) to the losing total modulo \(1234567890\). Finally, they compute \(N^3\bmod M\) and subtract the losing total modulo \(M\).
The C++ implementation also performs small sanity checks before the final large evaluation: it confirms the Grundy pattern on an initial range, checks the benchmark values \(S(10)=692\) and \(S(100)=735494\), and compares the closed-form count with a brute-force computation for a small input. The Python and Java implementations apply the same counting formula directly.
There are only \(O(\log N)\) nonzero valuation buckets. Building the bucket counts takes \(O(\log N)\) time and \(O(\log N)\) memory. The xor-based counting stage uses a double loop over those buckets, so it costs \(O((\log N)^2)\) time. For the target input, a fixed table of 64 buckets is enough, so the practical running time is tiny.
Bei Divisor Nim wählt man für einen Haufen der Größe \(n\) einen echten Teiler \(d\lt n\) und ersetzt den Haufen durch \(n-d\). Für drei unabhängige Haufen \((a,b,c)\) sei \(S(N)\) die Anzahl der Gewinnstartpositionen mit \(1\le a,b,c\le N\). Gesucht ist also \(S(123456787654321)\) modulo \(1234567890\).
Ein direktes Durchprobieren aller \(N^3\) Tripel ist unmöglich. Der entscheidende Punkt ist, dass der Sprague-Grundy-Wert eines einzelnen Haufens nur vom Exponenten der 2 in der Primfaktorzerlegung abhängt. Dadurch reduziert sich das gesamte Zählproblem auf eine kurze xor-Summe über Bewertungs-Klassen.
Sei \(g(n)\) der Sprague-Grundy-Wert eines einzelnen Haufens der Größe \(n\), und sei \(M=1234567890\). Dann müssen wir genau die Dreierpositionen zählen, deren xor nicht verschwindet.
Divisor Nim ist ein imparzielles Spiel unter Normalspiel-Regeln, also gilt der Satz von Sprague und Grundy. Daher ist
$$\text{die Position }(a,b,c)\text{ genau dann verloren, wenn }g(a)\oplus g(b)\oplus g(c)=0.$$
Sobald \(g(n)\) für alle Einzelhaufen bekannt ist, bleibt nur noch die kombinatorische Frage, wie oft jeder Grundy-Wert im Bereich von \(1\) bis \(N\) vorkommt.
Schreibe
$$n=2^e q,\qquad q\text{ ungerade},\qquad e=v_2(n).$$
Jeder echte Teiler von \(n\) hat die Form
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
wobei \((a,b)\ne(e,q)\) gilt, weil \(d\lt n\) sein muss.
Falls \(a\lt e\), dann
$$n-d=2^a\left(2^{e-a}q-b\right).$$
Dabei ist \(2^{e-a}q\) gerade und \(b\) ungerade, also ist die Klammer ungerade. Somit folgt
$$v_2(n-d)=a.$$
Falls \(a=e\), dann ist \(d=2^e b\) mit \(b\lt q\), also
$$n-d=2^e(q-b).$$
Da sowohl \(q\) als auch \(b\) ungerade sind, ist \(q-b\) eine positive gerade Zahl. Deshalb gilt
$$v_2(n-d)>e.$$
Ein Zug aus \(n\) kann also jede Bewertung \(0,1,\dots,e-1\) erreichen, manchmal auch Bewertungen größer als \(e\), aber niemals die Bewertung \(e\) selbst. Dass alle kleineren Werte wirklich erreichbar sind, sieht man an der Wahl \(d=2^a q\) für \(0\le a\lt e\); dann ist
$$n-d=2^a q\left(2^{e-a}-1\right),$$
und \(2^{e-a}-1\) ist ungerade, also wieder \(v_2(n-d)=a\).
Nun induzieren wir über \(n\). Jeder Zug führt zu einer kleineren Zahl, also stimmen die erreichbaren Grundy-Werte mit den erreichbaren Bewertungen kleinerer Positionen überein. Sie enthalten \(0,1,\dots,e-1\), enthalten aber nicht \(e\); größere Werte ändern den mex nicht. Daher
$$g(n)=e=v_2(n).$$
Für ungerades \(n\) ergibt das \(g(n)=0\), was dazu passt, dass jeder Zug von einem ungeraden Haufen zu einem geraden Haufen führt.
Definiere
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$$
Die Zahlen mit \(v_2(x)\ge k\) sind genau die Vielfachen von \(2^k\). Daher
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Nur endlich viele Klassen sind ungleich null. Sobald \(2^k>N\) gilt, verschwindet der Beitrag, also sind nur \(k\le \lfloor\log_2 N\rfloor\) relevant.
Ein Starttripel ist genau dann verloren, wenn
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
Sind die ersten beiden Bewertungen \(i\) und \(j\), dann muss die dritte \(i\oplus j\) sein. Also ist die Anzahl der Verlusttripel
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$$
Insgesamt gibt es \(N^3\) Tripel. Damit ist
$$S(N)=N^3-L(N),$$
und ausgegeben wird \(S(N)\pmod{M}\).
Für \(1\le x\le 10\) erhält man die Klassen
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$$
denn die Zahlen zerfallen in
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
Dann ist
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$$
Wegen \(10^3=1000\) folgt
$$S(10)=1000-308=692,$$
genau der kleine Kontrollwert, den die Implementierung verwendet.
Die C++-, Python- und Java-Implementierungen bauen keinen Spielbaum auf. Stattdessen zählen sie zuerst mit Rechtsverschiebungen, wie viele Zahlen in \([1,N]\) die Bewertungen \(0,1,2,\dots\) besitzen. Das entspricht direkt der Formel
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Anschließend durchlaufen sie in einer Doppelschleife alle nichtleeren Klassen. Für jedes Paar \((i,j)\) wird \(k=i\oplus j\) berechnet und der Beitrag \(C_iC_jC_k\) modulo \(1234567890\) zur Verlustsumme addiert. Danach wird \(N^3\bmod M\) berechnet und die Verlustsumme modulo \(M\) abgezogen.
Die C++-Implementierung führt zusätzlich vor der Endauswertung kleine Plausibilitätsprüfungen aus: Sie bestätigt das Grundy-Muster auf einem Anfangsbereich, überprüft die Vergleichswerte \(S(10)=692\) und \(S(100)=735494\) und vergleicht die geschlossene Formel für eine kleine Eingabe mit einem vollständigen Bruteforce-Zähler. Die Python- und Java-Implementierungen wenden dieselbe Zählformel direkt an.
Es gibt nur \(O(\log N)\) nichtverschwindende Bewertungs-Klassen. Ihr Aufbau kostet \(O(\log N)\) Zeit und \(O(\log N)\) Speicher. Die xor-Zählung verwendet eine doppelte Schleife über diese Klassen und benötigt daher \(O((\log N)^2)\) Zeit. Für die konkrete Zieleingabe reicht bereits eine feste Tabelle mit 64 Einträgen, daher ist die praktische Laufzeit sehr klein.
Divisor Nim’de \(n\) büyüklüğündeki bir yığından hamle yapmak için \(d\lt n\) olacak şekilde bir gerçek bölen seçilir ve yığın \(n-d\) yapılır. Üç bağımsız yığın \((a,b,c)\) için \(1\le a,b,c\le N\) aralığındaki kazanan başlangıç üçlülerinin sayısını \(S(N)\) ile gösterelim. Amaç \(S(123456787654321)\) değerini \(1234567890\) modunda bulmaktır.
Tüm \(N^3\) üçlüyü doğrudan incelemek mümkün değildir. Asıl kolaylaştırıcı nokta, tek bir yığının Sprague-Grundy değerinin sadece o sayının 2-adik üssüne bağlı olmasıdır. Böylece üç yığınlı sayım, değer sınıfları üzerinde kısa bir xor toplamına dönüşür.
Bir yığının boyutu \(n\) iken Sprague-Grundy değerini \(g(n)\) ile, mod sabitini de \(M=1234567890\) ile gösterelim. O halde saymamız gerekenler xor’u sıfır olmayan üçlülerdir.
Divisor Nim tarafsız ve normal oyun kurallarına sahip bir oyundur; bu yüzden Sprague-Grundy teoremi geçerlidir. Dolayısıyla
$$\text{\((a,b,c)\) konumu kaybedendir} \iff g(a)\oplus g(b)\oplus g(c)=0.$$
Tek yığın için \(g(n)\) bilindiğinde, geriye sadece \(1\) ile \(N\) arasındaki sayıların hangi Grundy değerine kaç kez düştüğünü saymak kalır.
Şöyle yazalım:
$$n=2^e q,\qquad q\text{ tek},\qquad e=v_2(n).$$
\(n\)’in her gerçek böleni şu biçimdedir:
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
ve \(d\lt n\) olduğu için \((a,b)\ne(e,q)\) olmak zorundadır.
Eğer \(a\lt e\) ise
$$n-d=2^a\left(2^{e-a}q-b\right).$$
Burada \(2^{e-a}q\) çifttir, \(b\) tektir; dolayısıyla parantez içi tektir. Böylece
$$v_2(n-d)=a$$
olur. Eğer \(a=e\) ise \(d=2^e b\) ve \(b\lt q\) olduğundan
$$n-d=2^e(q-b).$$
\(q\) ve \(b\) tek olduğu için \(q-b\) pozitif bir çift sayıdır. O halde
$$v_2(n-d)>e.$$
Demek ki \(n\)’den yapılan hamleler \(0,1,\dots,e-1\) değerlerinin hepsine ulaşabilir, bazen \(e\)’den büyük değerlere de ulaşabilir, fakat tam olarak \(e\) değerine asla ulaşamaz. Üstelik her \(0\le a\lt e\) için \(d=2^a q\) seçilirse
$$n-d=2^a q\left(2^{e-a}-1\right)$$
elde edilir ve \(2^{e-a}-1\) tek olduğundan yine \(v_2(n-d)=a\) olur.
Şimdi \(n\) üzerinde tümevarım yapalım. Her hamle daha küçük bir sayıya indiği için erişilebilen Grundy değerleri, daha küçük konumların erişilebilen değerleridir. Bunlar \(0,1,\dots,e-1\) değerlerini içerir, \(e\)’yi içermez; daha büyük değerler ise mex’i değiştirmez. Sonuç olarak
$$g(n)=e=v_2(n).$$
\(n\) tek ise bu formül \(g(n)=0\) der; bu da tek bir sayıdan yapılan her hamlenin çift bir sayıya gitmesiyle tutarlıdır.
Şimdi
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}$$
tanımını yapalım. \(v_2(x)\ge k\) olması, \(x\)’in \(2^k\) katı olmasıyla aynıdır. O halde
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Sıfırdan farklı sadece sonlu sayıda sınıf vardır. \(2^k>N\) olduğunda katkı sıfır olur; yani sadece \(k\le \lfloor\log_2 N\rfloor\) önemlidir.
Bir başlangıç üçlüsü tam olarak şu durumda kaybedendir:
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
İlk iki değer \(i\) ve \(j\) ise üçüncü değer zorunlu olarak \(i\oplus j\) olur. Bu yüzden kaybeden üçlü sayısı
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}$$
şeklindedir. Toplam üçlü sayısı \(N^3\) olduğundan
$$S(N)=N^3-L(N),$$
ve yazdırılan sonuç \(S(N)\pmod{M}\) değeridir.
\(1\le x\le 10\) için sınıflar
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1$$
olur; çünkü sayılar şu şekilde gruplanır:
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
Buradan
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308$$
elde edilir. \(10^3=1000\) olduğuna göre
$$S(10)=1000-308=692$$
bulunur; bu da uygulamadaki küçük kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları oyun ağacını gezmez. Bunun yerine önce sağa kaydırma işlemleriyle \([1,N]\) aralığındaki sayıların kaç tanesinin \(0,1,2,\dots\) değerlerine sahip olduğunu sayarlar. Bu, doğrudan
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor$$
formülünü uygular.
Daha sonra sıfır olmayan sınıflar üzerinde çift döngü kurulur. Her \((i,j)\) çifti için \(k=i\oplus j\) hesaplanır ve \(C_iC_jC_k\) katkısı \(1234567890\) modunda kaybeden toplamına eklenir. Son adımda \(N^3\bmod M\) hesaplanır ve bu toplam mod \(M\) altında çıkarılır.
C++ uygulaması ayrıca büyük girdi hesaplanmadan önce küçük doğrulamalar yapar: Grundy örüntüsünü başlangıç aralığında test eder, \(S(10)=692\) ve \(S(100)=735494\) değerlerini denetler ve kapalı formülü küçük bir giriş için brute-force sayımla karşılaştırır. Python ve Java uygulamaları ise aynı sayım formülünü doğrudan uygular.
Sıfır olmayan değer sınıfı sayısı sadece \(O(\log N)\) kadardır. Bu sınıfları oluşturmak \(O(\log N)\) zaman ve \(O(\log N)\) bellek ister. xor tabanlı sayım aşaması bu sınıflar üzerinde çift döngü kullandığı için \(O((\log N)^2)\) zamanda çalışır. Hedef girdi için 64 elemanlı sabit bir tablo yeterli olduğundan pratik çalışma süresi çok küçüktür.
En Divisor Nim, un movimiento sobre una pila de tamaño \(n\) consiste en elegir un divisor propio \(d\lt n\) y reemplazar la pila por \(n-d\). Para tres pilas independientes \((a,b,c)\), definimos \(S(N)\) como el número de ternas iniciales ganadoras con \(1\le a,b,c\le N\). Hay que calcular \(S(123456787654321)\) módulo \(1234567890\).
Probar las \(N^3\) ternas de forma directa es inviable. La simplificación decisiva es que el valor de Sprague-Grundy de una sola pila depende únicamente del exponente de 2 en el número, así que el conteo completo se reduce a una suma corta basada en xor sobre cubos de valoración.
Sea \(g(n)\) el valor de Sprague-Grundy de una pila de tamaño \(n\), y sea \(M=1234567890\). Entonces el objetivo es contar exactamente las posiciones de tres pilas cuyo xor no sea cero.
Divisor Nim es un juego imparcial en modalidad normal, así que se aplica el teorema de Sprague-Grundy. Por tanto,
$$\text{la posición }(a,b,c)\text{ es perdedora} \iff g(a)\oplus g(b)\oplus g(c)=0.$$
Una vez conocida la función \(g(n)\), el resto del problema consiste solo en contar cuántas veces aparece cada valor de Grundy entre \(1\) y \(N\).
Escribimos
$$n=2^e q,\qquad q\text{ impar},\qquad e=v_2(n).$$
Cualquier divisor propio de \(n\) tiene la forma
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
con \((a,b)\ne(e,q)\) porque \(d\lt n\).
Si \(a\lt e\), entonces
$$n-d=2^a\left(2^{e-a}q-b\right).$$
Aquí \(2^{e-a}q\) es par y \(b\) es impar, así que el paréntesis es impar. Luego
$$v_2(n-d)=a.$$
Si \(a=e\), entonces \(d=2^e b\) con \(b\lt q\), de modo que
$$n-d=2^e(q-b).$$
Como \(q\) y \(b\) son impares, \(q-b\) es un entero positivo par. Por lo tanto,
$$v_2(n-d)>e.$$
Así, desde \(n\) se puede alcanzar cualquier valoración \(0,1,\dots,e-1\), a veces también valoraciones mayores que \(e\), pero nunca la valoración \(e\) misma. Además, para cada \(0\le a\lt e\), al elegir \(d=2^a q\) se obtiene
$$n-d=2^a q\left(2^{e-a}-1\right),$$
y como \(2^{e-a}-1\) es impar, vuelve a salir \(v_2(n-d)=a\).
Ahora hacemos inducción sobre \(n\). Cada movimiento lleva a una pila más pequeña, así que los valores de Grundy alcanzables coinciden con las valoraciones alcanzables de posiciones menores. Contienen \(0,1,\dots,e-1\), no contienen \(e\), y los valores mayores no modifican el mex. En consecuencia,
$$g(n)=e=v_2(n).$$
Cuando \(n\) es impar, esto afirma \(g(n)=0\), lo cual encaja con que todo movimiento desde una pila impar lleva a una pila par.
Definimos
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$$
Los enteros con \(v_2(x)\ge k\) son exactamente los múltiplos de \(2^k\). Por eso
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Solo hay un número finito de cubos no nulos. En cuanto \(2^k>N\), el conteo vale cero, así que solo importan los \(k\le \lfloor\log_2 N\rfloor\).
Una terna inicial es perdedora exactamente cuando
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
Si las dos primeras valoraciones son \(i\) y \(j\), la tercera debe ser \(i\oplus j\). Así, el número de ternas perdedoras es
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$$
Como el total de ternas es \(N^3\), el número de ternas ganadoras vale
$$S(N)=N^3-L(N),$$
y la salida final es \(S(N)\pmod{M}\).
Para \(1\le x\le 10\), los cubos son
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$$
porque los números se agrupan como
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
Entonces
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$$
Dado que \(10^3=1000\), obtenemos
$$S(10)=1000-308=692,$$
que coincide con el valor de comprobación usado por la implementación.
Las implementaciones en C++, Python y Java no recorren árboles de juego. En su lugar, primero cuentan cuántos enteros de \([1,N]\) tienen valoración \(0,1,2,\dots\) mediante divisiones sucesivas por potencias de 2, lo que implementa exactamente
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Después ejecutan un doble bucle sobre los cubos no vacíos. Para cada par \((i,j)\), calculan \(k=i\oplus j\) y añaden la contribución \(C_iC_jC_k\) al total perdedor módulo \(1234567890\). Al final calculan \(N^3\bmod M\) y restan ese total, siempre bajo el mismo módulo.
La implementación en C++ también realiza comprobaciones internas antes de la evaluación final grande: confirma el patrón de Grundy en un prefijo inicial, verifica los valores de referencia \(S(10)=692\) y \(S(100)=735494\), y compara la fórmula cerrada con un conteo por fuerza bruta para una entrada pequeña. Las versiones de Python y Java aplican directamente la misma fórmula de conteo.
Solo existen \(O(\log N)\) cubos de valoración no nulos. Construir esos conteos cuesta \(O(\log N)\) tiempo y \(O(\log N)\) memoria. La fase de conteo basada en xor usa un doble bucle sobre esos cubos, así que cuesta \(O((\log N)^2)\) tiempo. Para la entrada objetivo basta una tabla fija de 64 posiciones, de modo que el tiempo real de ejecución es muy pequeño.
在 Divisor Nim 中，如果一堆石子的大小为 \(n\)，一次合法操作是选取一个真因子 \(d\lt n\)，然后把这堆变成 \(n-d\)。对于三个彼此独立的石堆 \((a,b,c)\)，记 \(S(N)\) 为所有满足 \(1\le a,b,c\le N\) 的必胜初始三元组个数。题目要求计算 \(S(123456787654321)\) 对 \(1234567890\) 取模后的结果。
如果直接枚举全部 \(N^3\) 个三元组，规模根本无法接受。真正的突破点在于：单堆游戏的 Sprague-Grundy 值只由该数中 2 的指数决定。这样一来，三堆问题就不再是状态搜索，而变成了对若干个 \(2\)-进赋值桶做一个很短的 xor 求和。
记单堆大小为 \(n\) 时的 Sprague-Grundy 值为 \(g(n)\)，并记模数为 \(M=1234567890\)。那么我们需要统计的正是三堆 Grundy 值异或结果非零的起始位置数。
Divisor Nim 是一个无偏博弈，并且采用正常结束规则，所以可以直接应用 Sprague-Grundy 定理。因此
$$\text{位置 }(a,b,c)\text{ 为必败态} \iff g(a)\oplus g(b)\oplus g(c)=0.$$
所以只要能够求出每个单堆大小 \(n\) 的 \(g(n)\)，剩下的工作就只是统计区间 \([1,N]\) 中每个 Grundy 值出现了多少次。
把 \(n\) 写成
$$n=2^e q,\qquad q\text{ 为奇数},\qquad e=v_2(n).$$
\(n\) 的任意真因子都可以写成
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
并且由于 \(d\lt n\)，不可能同时有 \((a,b)=(e,q)\)。
如果 \(a\lt e\)，那么
$$n-d=2^a\left(2^{e-a}q-b\right).$$
这里 \(2^{e-a}q\) 是偶数，而 \(b\) 是奇数，所以括号中的量一定是奇数。因此
$$v_2(n-d)=a.$$
如果 \(a=e\)，则 \(d=2^e b\) 且 \(b\lt q\)，于是
$$n-d=2^e(q-b).$$
因为 \(q\) 和 \(b\) 都是奇数，所以 \(q-b\) 是正的偶数，从而
$$v_2(n-d)>e.$$
这说明：从 \(n\) 出发的合法一步，可以到达所有赋值 \(0,1,\dots,e-1\)，有时还会到达大于 \(e\) 的赋值，但绝不会恰好到达赋值 \(e\)。而且对于每个 \(0\le a\lt e\)，取 \(d=2^a q\) 时就有
$$n-d=2^a q\left(2^{e-a}-1\right),$$
由于 \(2^{e-a}-1\) 是奇数，马上得到 \(v_2(n-d)=a\)。
现在对 \(n\) 做归纳。因为每一步都会把石堆变小，所以所有可达位置都比 \(n\) 小，归纳假设允许我们把“可达 Grundy 值”直接看成“可达的 \(2\)-进赋值”。这些可达值包含 \(0,1,\dots,e-1\)，不包含 \(e\)，而比 \(e\) 更大的值不会影响 mex。于是
$$g(n)=e=v_2(n).$$
特别地，当 \(n\) 为奇数时，结论给出 \(g(n)=0\)；这也和事实一致，因为奇数堆的任何一步都会落到偶数堆上。
定义
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$$
满足 \(v_2(x)\ge k\) 的整数，恰好就是 \(2^k\) 的倍数，所以
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
只有有限多个桶是非零的。一旦 \(2^k>N\)，这个桶就为空，因此真正需要处理的只有 \(k\le \lfloor\log_2 N\rfloor\)。
一个初始三元组是必败态，当且仅当
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
如果前两个赋值分别是 \(i\) 和 \(j\)，那么第三个赋值就必须是 \(i\oplus j\)。因此必败三元组个数为
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$$
而总三元组个数是 \(N^3\)，所以必胜三元组个数为
$$S(N)=N^3-L(N),$$
最终输出的是 \(S(N)\pmod{M}\)。
当 \(1\le x\le 10\) 时，各个赋值桶为
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$$
对应的分组是
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
于是
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$$
由于 \(10^3=1000\)，所以
$$S(10)=1000-308=692,$$
这与实现中使用的小规模校验值完全一致。
C++、Python 和 Java 实现都不会去显式搜索博弈状态图。它们首先通过不断除以 2 或等价的位移方式，统计区间 \([1,N]\) 中有多少个数具有赋值 \(0,1,2,\dots\)，这正对应公式
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
接着，它们在所有非空桶上做一个双重循环。对于每一对 \((i,j)\)，先求 \(k=i\oplus j\)，再把贡献 \(C_iC_jC_k\) 加到必败总数中，并始终对 \(1234567890\) 取模。最后再计算 \(N^3\bmod M\)，减去刚才得到的必败总数。
C++ 实现还在最终大输入计算前做了若干内部校验：它先验证单堆 Grundy 模式在一个小前缀上成立，再检查参考值 \(S(10)=692\) 与 \(S(100)=735494\)，并把闭式计数结果与一个小输入上的暴力枚举结果进行对比。Python 与 Java 实现则直接使用同样的闭式计数公式。
非零赋值桶的数量只有 \(O(\log N)\) 个。建立这些桶需要 \(O(\log N)\) 时间和 \(O(\log N)\) 空间。随后 xor 计数阶段是在这些桶上做双重循环，因此时间复杂度为 \(O((\log N)^2)\)。对题目的目标输入而言，只需要一个长度为 64 的固定表，所以实际运行时间非常小。
В Divisor Nim ход из кучи размера \(n\) состоит в выборе собственного делителя \(d\lt n\) и переходе в состояние \(n-d\). Для трёх независимых куч \((a,b,c)\) обозначим через \(S(N)\) число выигрышных стартовых троек при \(1\le a,b,c\le N\). Нужно вычислить \(S(123456787654321)\) по модулю \(1234567890\).
Полный перебор всех \(N^3\) троек невозможен. Основное упрощение состоит в том, что значение Шпрага-Гранди для одной кучи зависит только от показателя двойки в разложении числа. Поэтому вся задача сводится к короткой xor-сумме по классам \(2\)-адической оценки.
Обозначим через \(g(n)\) значение Шпрага-Гранди одной кучи размера \(n\), а через \(M=1234567890\) — модуль. Тогда требуется посчитать именно те стартовые позиции из трёх куч, у которых xor не равен нулю.
Divisor Nim — это беспристрастная игра в нормальной форме, поэтому применима теорема Шпрага-Гранди. Следовательно,
$$\text{позиция }(a,b,c)\text{ проигрышна} \iff g(a)\oplus g(b)\oplus g(c)=0.$$
Как только мы понимаем формулу для \(g(n)\), остаётся лишь подсчитать, сколько чисел от \(1\) до \(N\) даёт каждый возможный Grundy-уровень.
Запишем
$$n=2^e q,\qquad q\text{ нечётно},\qquad e=v_2(n).$$
Любой собственный делитель числа \(n\) имеет вид
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
причём \((a,b)\ne(e,q)\), потому что \(d\lt n\).
Если \(a\lt e\), то
$$n-d=2^a\left(2^{e-a}q-b\right).$$
Здесь \(2^{e-a}q\) чётно, а \(b\) нечётно, значит выражение в скобках нечётно. Поэтому
$$v_2(n-d)=a.$$
Если \(a=e\), то \(d=2^e b\) с \(b\lt q\), и тогда
$$n-d=2^e(q-b).$$
Так как \(q\) и \(b\) нечётны, разность \(q-b\) является положительным чётным числом. Следовательно,
$$v_2(n-d)>e.$$
Итак, из \(n\) можно попасть во все оценки \(0,1,\dots,e-1\), иногда и в оценки больше \(e\), но никогда ровно в оценку \(e\). Более того, для каждого \(0\le a\lt e\) можно взять \(d=2^a q\), и тогда
$$n-d=2^a q\left(2^{e-a}-1\right),$$
а множитель \(2^{e-a}-1\) нечётен, так что снова \(v_2(n-d)=a\).
Теперь проводим индукцию по \(n\). Любой ход ведёт к меньшему числу, поэтому доступные значения Гранди совпадают с доступными оценками меньших позиций. Среди них есть \(0,1,\dots,e-1\), нет \(e\), а значения больше \(e\) не влияют на mex. Значит,
$$g(n)=e=v_2(n).$$
Для нечётного \(n\) это даёт \(g(n)=0\), что согласуется с тем, что любой ход из нечётной кучи приводит к чётной.
Определим
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$$
Числа с условием \(v_2(x)\ge k\) — это в точности кратные \(2^k\). Поэтому
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
Ненулевых классов только конечное число. Как только \(2^k>N\), соответствующий класс пуст, так что учитывать нужно лишь \(k\le \lfloor\log_2 N\rfloor\).
Стартовая тройка проигрышна тогда и только тогда, когда
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
Если первые две оценки равны \(i\) и \(j\), то третья обязана быть \(i\oplus j\). Значит, число проигрышных троек равно
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$$
Всего троек \(N^3\), поэтому число выигрышных стартов равно
$$S(N)=N^3-L(N),$$
а в ответ выводится \(S(N)\pmod{M}\).
Для \(1\le x\le 10\) получаем классы
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$$
потому что числа разбиваются на группы
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
Тогда
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$$
Поскольку \(10^3=1000\), имеем
$$S(10)=1000-308=692,$$
и это в точности совпадает с контрольным значением, используемым в реализации.
Реализации на C++, Python и Java не строят дерево игры. Вместо этого они сначала считают, сколько чисел из \([1,N]\) имеют оценки \(0,1,2,\dots\), используя деление на степени двойки или эквивалентные сдвиги. Это напрямую реализует формулу
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
После этого выполняется двойной цикл по непустым классам. Для каждой пары \((i,j)\) вычисляется \(k=i\oplus j\), и вклад \(C_iC_jC_k\) добавляется к сумме проигрышных троек по модулю \(1234567890\). Затем программа вычисляет \(N^3\bmod M\) и вычитает найденную проигрышную сумму по тому же модулю.
Реализация на C++ дополнительно запускает несколько внутренних проверок перед финальным большим вычислением: подтверждает паттерн Grundy на небольшом префиксе, проверяет значения \(S(10)=692\) и \(S(100)=735494\), а также сравнивает формулу с полным перебором на маленьком входе. Версии на Python и Java используют ту же самую формулу подсчёта напрямую.
Ненулевых классов оценки всего \(O(\log N)\). Их построение занимает \(O(\log N)\) времени и \(O(\log N)\) памяти. Затем xor-подсчёт использует двойной цикл по этим классам и работает за \(O((\log N)^2)\). Для целевого входа достаточно фиксированной таблицы из 64 ячеек, поэтому фактическое время работы очень мало.
في Divisor Nim تكون الحركة على كومة حجمها \(n\) باختيار قاسم صحيح غير كامل \(d\lt n\)، ثم استبدال الكومة بالعدد \(n-d\). ومع ثلاث أكوام مستقلة \((a,b,c)\)، نرمز بـ \(S(N)\) إلى عدد الثلاثيات الابتدائية الرابحة التي تحقق \(1\le a,b,c\le N\). المطلوب هو حساب \(S(123456787654321)\) بترديد \(1234567890\).
العدّ المباشر لجميع الثلاثيات وعددها \(N^3\) غير عملي إطلاقًا. الفكرة الحاسمة هي أن قيمة Sprague-Grundy لكومة واحدة لا تعتمد إلا على أسّ العدد \(2\) في تحليل حجم الكومة، ولذلك يتحول عدّ الحالات الثلاثية إلى مجموع xor قصير على فئات التقييم \(2\)-العددي.
لنرمز إلى قيمة Sprague-Grundy لكومة مفردة حجمها \(n\) بالرمز \(g(n)\)، ولنكتب \(M=1234567890\) للمودولو. عندئذٍ فإن ما نحتاج إلى عده هو كل مواضع البداية ذات xor غير الصفري.
لأن Divisor Nim لعبة غير متحيزة وتخضع لقواعد اللعب العادي، فإن مبرهنة Sprague-Grundy تنطبق مباشرة. لذلك تكون الثلاثية \((a,b,c)\) خاسرة إذا وفقط إذا
$$g(a)\oplus g(b)\oplus g(c)=0.$$
وبمجرد معرفة الصيغة الدقيقة لـ \(g(n)\) لكل كومة مفردة، يبقى فقط أن نعدّ عدد المرات التي يظهر فيها كل مقدار Grundy بين الأعداد من \(1\) إلى \(N\).
اكتب
$$n=2^e q,\qquad e=v_2(n).$$
بحيث يكون \(q\) عددًا فرديًا.
وأي قاسم صحيح غير كامل لـ \(n\) يمكن كتابته على الصورة
$$d=2^a b,\qquad 0\le a\le e,\qquad b\mid q,$$
مع استبعاد الحالة \((a,b)=(e,q)\) لأن هذا يعطي \(d=n\) وليس قاسمًا حقيقيًا أصغر من \(n\).
إذا كان \(a\lt e\)، فإن
$$n-d=2^a\left(2^{e-a}q-b\right).$$
الحد \(2^{e-a}q\) زوجي، بينما \(b\) فردي، ولذلك ما بين القوسين فردي. ومن ثم
$$v_2(n-d)=a.$$
أما إذا كان \(a=e\)، فلدينا \(d=2^e b\) مع \(b\lt q\)، وبالتالي
$$n-d=2^e(q-b).$$
وبما أن \(q\) و\(b\) كلاهما فردي، فإن \(q-b\) عدد زوجي موجب، لذا
$$v_2(n-d)>e.$$
إذن يمكن للحركة من \(n\) أن تصل إلى جميع التقييمات \(0,1,\dots,e-1\)، وقد تصل أحيانًا إلى تقييمات أكبر من \(e\)، لكنها لا تصل أبدًا إلى التقييم \(e\) نفسه. ولرؤية أن كل قيمة أصغر من \(e\) يمكن بلوغها بالفعل، نختار لكل \(0\le a\lt e\) القاسم \(d=2^a q\)، فنحصل على
$$n-d=2^a q\left(2^{e-a}-1\right),$$
وبما أن \(2^{e-a}-1\) فردي فإن \(v_2(n-d)=a\).
الآن نستخدم الاستقراء على \(n\). كل حركة تنقلنا إلى كومة أصغر، ومن ثم فإن قيم Grundy القابلة للوصول هي بالضبط التقييمات القابلة للوصول في المواضع الأصغر. هذه القيم تحتوي على \(0,1,\dots,e-1\)، ولا تحتوي على \(e\)، كما أن القيم الأكبر من \(e\) لا تؤثر في قيمة mex. لذلك نستنتج أن
$$g(n)=e=v_2(n).$$
وعندما يكون \(n\) فرديًا تصبح النتيجة \(g(n)=0\)، وهذا منسجم مع أن كل حركة من كومة فردية تنتهي في كومة زوجية.
لنعرّف
$$C_k=\#\{x\in[1,N]:v_2(x)=k\}.$$
الأعداد التي تحقق \(v_2(x)\ge k\) هي بالضبط مضاعفات \(2^k\)، ومن هنا نحصل على
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
ولا يوجد إلا عدد منتهٍ من الفئات غير الصفرية؛ فعندما يصبح \(2^k>N\) تختفي هذه الفئة تمامًا، ولذلك يكفي النظر إلى \(k\le \lfloor\log_2 N\rfloor\).
الثلاثية الابتدائية تكون خاسرة إذا وفقط إذا
$$v_2(a)\oplus v_2(b)\oplus v_2(c)=0.$$
فإذا كانت قيمتا التقييم لأول كومتين هما \(i\) و\(j\)، وجب أن تكون القيمة الثالثة مساوية لـ \(i\oplus j\). ولذلك فإن عدد الثلاثيات الخاسرة يساوي
$$L(N)=\sum_{i\ge 0}\sum_{j\ge 0} C_i\,C_j\,C_{i\oplus j}.$$
أما العدد الكلي للثلاثيات فهو \(N^3\)، ومن ثم يكون عدد الثلاثيات الرابحة
$$S(N)=N^3-L(N),$$
والنتيجة النهائية المطبوعة هي \(S(N)\pmod{M}\).
بالنسبة إلى \(1\le x\le 10\)، تكون الفئات
$$C_0=5,\qquad C_1=3,\qquad C_2=1,\qquad C_3=1,$$
وذلك لأن الأعداد تتوزع إلى المجموعات
$$\{1,3,5,7,9\},\quad \{2,6,10\},\quad \{4\},\quad \{8\}.$$
وعندئذٍ نحصل على
$$L(10)=\sum_{i,j=0}^{3} C_i\,C_j\,C_{i\oplus j}=308.$$
وبما أن \(10^3=1000\)، فإن
$$S(10)=1000-308=692,$$
وهو بالضبط مقدار التحقق الصغير المستخدم داخل التنفيذ.
تنفيذات C++ وPython وJava لا تستعرض شجرة اللعب. بدلًا من ذلك، تبدأ بعدّ عدد الأعداد في \([1,N]\) التي تملك تقييمًا مقداره \(0,1,2,\dots\)، وذلك باستعمال القسمة على قوى العدد \(2\) أو الإزاحات الثنائية المكافئة، وهو ما يحقق مباشرة الصيغة
$$C_k=\left\lfloor\frac{N}{2^k}\right\rfloor-\left\lfloor\frac{N}{2^{k+1}}\right\rfloor.$$
بعد ذلك يُنفَّذ دوران متداخلان على الفئات غير الفارغة. ولكل زوج \((i,j)\) تُحسب القيمة \(k=i\oplus j\)، ثم تُضاف المساهمة \(C_iC_jC_k\) إلى مجموع الحالات الخاسرة بترديد \(1234567890\). وفي النهاية يُحسب \(N^3\bmod M\) ثم يُطرح منه ذلك المجموع تحت نفس المودولو.
أما تنفيذ C++ فيضيف أيضًا بعض اختبارات السلامة قبل الحساب النهائي الكبير: فهو يؤكد نمط Grundy على مجال ابتدائي صغير، ويتحقق من القيمتين \(S(10)=692\) و\(S(100)=735494\)، كما يقارن العدّ المغلق مع عدّ brute force لمدخل صغير. أما تنفيذات Python وJava فتطبق الصيغة نفسها مباشرة.
عدد فئات التقييم غير الصفرية هو فقط \(O(\log N)\). بناء هذه الفئات يحتاج إلى \(O(\log N)\) زمنًا و\(O(\log N)\) ذاكرة. ثم تأتي مرحلة العدّ المعتمدة على xor، وهي حلقة مزدوجة على هذه الفئات، فتعمل في \(O((\log N)^2)\). وبالنسبة إلى الدخل المطلوب في المسألة، تكفي مصفوفة ثابتة من 64 خانة، لذا يكون الزمن العملي صغيرًا جدًا.