For each positive integer \(n\), let \(t(n)\) be the smallest offset \(k\) such that the DistribuNim II position consisting of \(n\) piles of size \(n\) and one additional pile of size \(n+k\) is a losing position. The problem asks for
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$$
A direct search over game states is hopeless for large \(N\). The efficient solution therefore avoids game-tree exploration and instead uses a closed formula for each \(t(n)\), followed by an exact summation over bit-length blocks.
The key fact used by the optimized solution is that the losing offset is controlled by the low bits of \(n^2\).
Let
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
Define
$$\varepsilon(n)=\begin{cases} 0, & n\text{ even},\\ 2^m-1, & n\text{ odd}. \end{cases}$$
Then the implementations use the identity
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$$
Equivalently,
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ even},\\ (-n^2-1)\bmod 2^m, & n\text{ odd}. \end{cases}$$
So once the bit-length \(m\) is known, we only need the lowest \(m\) bits of \(n^2\).
For each \(m\ge 1\), define the block sum
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$$
If \(n=2^r\), then \(n\) is even and \(n^2=2^{2r}\) is divisible by \(2^{r+1}\), so \(t(2^r)=0\). Therefore the endpoint \(n=2^N\) contributes nothing, and
$$S(N)=\sum_{m=1}^{N} B_m.$$
Now write
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$$
Then
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$$
because both \(2^{2m-2}\) and \(2^m j\) are multiples of \(2^m\). For \(m\ge 2\), the number \(2^{m-1}\) is even, so \(n\) and \(j\) have the same parity. Hence
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ even},\\ (-j^2-1)\bmod 2^m, & j\text{ odd}. \end{cases}$$
Split the block into even and odd offsets:
$$j=2u\quad\text{or}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
Then the even contribution is built from residues of \(4u^2\), while the odd contribution is built from residues of \(4u(u+1)+1\). Summing those two parity classes over a complete block gives exact formulas
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$$
The first few values are
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$$
which already shows the geometric structure that the code exploits.
Every block contributes a \(4^{m-1}\) term, so
$$\sum_{m=1}^{N} 4^{m-1}=\frac{4^N-1}{3}.$$
The \(8\)-power corrections come in adjacent pairs. Block \(2k+1\) contributes \(8^k\), and block \(2k+2\) contributes \(2\cdot 8^k\), so one complete pair contributes \(3\cdot 8^k\). If
$$K=\left\lfloor \frac{N}{2}\right\rfloor,$$
then the total \(8\)-power contribution is
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^K.$$
The subtractive pieces add up to
$$\sum_{m=1}^{N}2^m=2^{N+1}-2.$$
Therefore
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
Take \(n=6\). Here \(m=3\) because \(4\le 6<8\). Since \(6\) is even,
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
Take \(n=5\). Again \(m=3\), but now \(5\) is odd, so
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
For \(N=4\), the block totals are
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$$
hence
$$S(4)=0+2+16+64=82.$$
This matches the direct sum of \(t(n)\) for \(1\le n\le 16\).
The C++, Python, and Java implementations all follow the same fast path. First they compute the modular inverses needed for the fractions \(1/3\) and \(1/7\). Next they evaluate \(4^N\), \(8^{\lfloor N/2\rfloor}\), and \(2^{N+1}\) with fast modular exponentiation. Those three powers are then assembled into
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2,$$
and the final answer is \(\text{sumA}+\text{sumB}-\text{sumC}\) modulo \(900497239\). The C++ implementation also keeps small-scale validation logic: it compares the closed form with direct summation for small \(N\) and checks the first few losing offsets against brute force, but the production result is obtained entirely from the closed formula.
The optimized method uses only a constant number of modular exponentiations, so the running time is \(O(\log N)\) and the memory usage is \(O(1)\). By contrast, the defining sum already has \(2^N\) terms before considering any game-state search, so the closed form is what makes the problem tractable.
Für jede positive ganze Zahl \(n\) sei \(t(n)\) der kleinste Offset \(k\), so dass die DistribuNim-II-Stellung aus \(n\) Stapeln der Größe \(n\) und einem zusätzlichen Stapel der Größe \(n+k\) eine Verluststellung ist. Gesucht ist
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$$
Eine direkte Spielbaumsuche ist für große \(N\) unbrauchbar. Deshalb verwendet die effiziente Lösung keine vollständige Suche, sondern zuerst eine geschlossene Formel für jedes \(t(n)\) und summiert diese danach exakt über Blöcke fester Bitlänge.
Die zentrale Tatsache der optimierten Lösung ist, dass der Verlust-Offset nur von der Bitlänge von \(n\), der Parität von \(n\) und den unteren Bits von \(n^2\) abhängt.
Sei
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
Weiter definieren wir
$$\varepsilon(n)=\begin{cases} 0, & n\text{ gerade},\\ 2^m-1, & n\text{ ungerade}. \end{cases}$$
Dann lautet die verwendete Identität
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$$
Also äquivalent
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ gerade},\\ (-n^2-1)\bmod 2^m, & n\text{ ungerade}. \end{cases}$$
Ist \(m\) bekannt, braucht man also nur die unteren \(m\) Bits von \(n^2\).
Für jedes \(m\ge 1\) definieren wir
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$$
Für \(n=2^r\) gilt wegen Geradheit und \(n^2=2^{2r}\), dass \(2^{r+1}\mid n^2\), also \(t(2^r)=0\). Daher trägt auch der Endpunkt \(n=2^N\) nichts bei, und somit
$$S(N)=\sum_{m=1}^{N} B_m.$$
Schreibe nun
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$$
Dann folgt
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$$
weil sowohl \(2^{2m-2}\) als auch \(2^m j\) Vielfache von \(2^m\) sind. Für \(m\ge 2\) ist \(2^{m-1}\) gerade, also haben \(n\) und \(j\) dieselbe Parität. Daher
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ gerade},\\ (-j^2-1)\bmod 2^m, & j\text{ ungerade}. \end{cases}$$
Man zerlegt den Block in gerade und ungerade Offsets:
$$j=2u\quad\text{oder}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
Der gerade Anteil beruht auf Resten der Form \(4u^2\), der ungerade Anteil auf Resten der Form \(4u(u+1)+1\). Summiert man beide Paritätsklassen über einen vollständigen Block, erhält man exakt
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$$
Die ersten Werte sind
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$$
und machen die geometrische Struktur der Lösung bereits sichtbar.
Jeder Block enthält einen Term \(4^{m-1}\). Daher
$$\sum_{m=1}^{N} 4^{m-1}=\frac{4^N-1}{3}.$$
Die \(8\)-Potenz-Korrekturen treten paarweise auf. Block \(2k+1\) liefert \(8^k\), der folgende Block \(2k+2\) liefert \(2\cdot 8^k\). Ein vollständiges Paar trägt also \(3\cdot 8^k\) bei. Mit
$$K=\left\lfloor \frac{N}{2}\right\rfloor$$
ergibt das insgesamt
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ ungerade}}\,8^K.$$
Die subtraktiven Terme summieren sich zu
$$\sum_{m=1}^{N}2^m=2^{N+1}-2.$$
Damit folgt
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ ungerade}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
Betrachte \(n=6\). Dann ist \(m=3\), weil \(4\le 6<8\). Da \(6\) gerade ist, gilt
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
Für \(n=5\) gilt ebenfalls \(m=3\), aber \(5\) ist ungerade. Also
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
Für \(N=4\) sind die Blocksummen
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$$
also
$$S(4)=0+2+16+64=82.$$
Das stimmt mit der direkten Auswertung von \(t(n)\) für \(1\le n\le 16\) überein.
Die C++-, Python- und Java-Implementierungen benutzen denselben schnellen Rechenweg. Zuerst werden die modularen Inversen für die Brüche \(1/3\) und \(1/7\) bestimmt. Danach werden \(4^N\), \(8^{\lfloor N/2\rfloor}\) und \(2^{N+1}\) mit schneller modularer Exponentiation berechnet. Diese drei Werte werden dann zu
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ ungerade}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2$$
zusammengesetzt, und die Endantwort ist \(\text{sumA}+\text{sumB}-\text{sumC}\) modulo \(900497239\). Die C++-Implementierung enthält zusätzlich kleine Prüfungen: Sie vergleicht die geschlossene Formel für kleine \(N\) mit direkter Summation und testet die ersten Verlust-Offsets per Brute Force. Das eigentliche Ergebnis wird jedoch vollständig aus der geschlossenen Formel berechnet.
Die optimierte Methode benötigt nur eine konstante Anzahl modularer Potenzrechnungen. Damit liegt die Laufzeit bei \(O(\log N)\), der Speicherverbrauch bei \(O(1)\). Im Gegensatz dazu besitzt schon die definierende Summe \(2^N\) Terme, noch bevor irgendeine Spielbaumsuche betrachtet wird.
Her pozitif \(n\) için \(t(n)\), DistribuNim II oyununda \(n\) tane \(n\) büyüklüğünde yığın ve bir tane de \(n+k\) büyüklüğünde ek yığın içeren konumu kaybeden konum yapan en küçük \(k\) değeri olsun. Sorulan toplam
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}$$
şeklindedir. Büyük \(N\) için oyun ağacını doğrudan taramak mümkün olmadığından, verimli çözüm oyun araması yapmaz; her \(t(n)\) için kapalı form kullanır ve ardından bu formülü bit uzunluğu blokları üzerinde toplar.
Hızlı çözümün dayandığı temel gerçek, kaybeden ofsetin \(n\)'in bit uzunluğu, \(n\)'in tek-çift oluşu ve \(n^2\)'nin alt bitleri tarafından belirlenmesidir.
Şöyle tanımlayalım:
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
Ayrıca
$$\varepsilon(n)=\begin{cases} 0, & n\text{ çift},\\ 2^m-1, & n\text{ tek}. \end{cases}$$
olsun. O zaman kullanılan özdeşlik
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m$$
şeklindedir. Başka bir deyişle
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ çift},\\ (-n^2-1)\bmod 2^m, & n\text{ tek}. \end{cases}$$
Dolayısıyla \(m\) belli olduğunda gereken tek bilgi, \(n^2\)'nin en düşük \(m\) bitidir.
Her \(m\ge 1\) için
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n)$$
tanımını yapalım. Eğer \(n=2^r\) ise \(n\) çifttir ve \(n^2=2^{2r}\), yani \(2^{r+1}\) sayısı \(n^2\)'yi böler. Bu yüzden \(t(2^r)=0\). Son uç nokta olan \(n=2^N\) da katkı vermez ve
$$S(N)=\sum_{m=1}^{N} B_m$$
olur. Şimdi
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}$$
yazalım. O zaman
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m}$$
elde edilir; çünkü hem \(2^{2m-2}\) hem de \(2^m j\), \(2^m\)'in katıdır. \(m\ge 2\) için \(2^{m-1}\) çift olduğundan \(n\) ile \(j\) aynı pariteye sahiptir. Böylece
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ çift},\\ (-j^2-1)\bmod 2^m, & j\text{ tek}. \end{cases}$$
Bloğu çift ve tek ofsetlere ayıralım:
$$j=2u\quad\text{veya}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
Çift kısım \(4u^2\) tipindeki kalıntılardan, tek kısım ise \(4u(u+1)+1\) tipindeki kalıntılardan oluşur. Bu iki parite sınıfı tam blok boyunca toplandığında kapalı biçim olarak
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0$$
bulunur. İlk birkaç blok değeri
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288$$
olup, çözümün geometrik yapısını açıkça gösterir.
Her blokta bir \(4^{m-1}\) terimi vardır, dolayısıyla
$$\sum_{m=1}^{N} 4^{m-1}=\frac{4^N-1}{3}.$$
\(8\) kuvvetli düzeltmeler komşu çiftler halinde gelir. \(2k+1\). blok \(8^k\), onu izleyen \(2k+2\). blok ise \(2\cdot 8^k\) katkısı verir. Yani tam bir blok çifti \(3\cdot 8^k\) getirir. Eğer
$$K=\left\lfloor \frac{N}{2}\right\rfloor$$
ise toplam düzeltme
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ tek}}\,8^K$$
olur. Çıkarılan terimler de
$$\sum_{m=1}^{N}2^m=2^{N+1}-2$$
şeklinde toplanır. Sonuç olarak
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ tek}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
\(n=6\) için \(m=3\) çünkü \(4\le 6<8\). \(6\) çift olduğu için
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
\(n=5\) için yine \(m=3\), fakat bu kez \(5\) tektir. Bu yüzden
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
\(N=4\) alındığında blok toplamları
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64$$
olur ve
$$S(4)=0+2+16+64=82$$
elde edilir. Bu değer, \(1\le n\le 16\) için doğrudan \(t(n)\) toplamıyla aynıdır.
C++, Python ve Java implementasyonları aynı hızlı yolu izler. Önce \(1/3\) ve \(1/7\) için modüler tersler hesaplanır. Sonra hızlı modüler üs alma ile \(4^N\), \(8^{\lfloor N/2\rfloor}\) ve \(2^{N+1}\) bulunur. Bu üç değer
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ tek}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2$$
ifadelerine yerleştirilir ve son cevap \(900497239\) modunda \(\text{sumA}+\text{sumB}-\text{sumC}\) olarak üretilir. C++ implementasyonunda ayrıca küçük ölçekli doğrulamalar bulunur: kapalı form küçük \(N\) için doğrudan toplamla karşılaştırılır ve ilk birkaç kaybeden ofset kaba kuvvetle kontrol edilir. Ancak asıl üretim hesabı tamamen kapalı formülle yapılır.
Optimize yöntem sadece sabit sayıda modüler üs alma çağrısı yapar. Bu nedenle çalışma süresi \(O(\log N)\), bellek kullanımı ise \(O(1)\)'dir. Buna karşılık tanımdaki toplam zaten \(2^N\) terim içerir; kapalı form olmasa problem pratik olarak çözülemez.
Para cada entero positivo \(n\), sea \(t(n)\) el menor desplazamiento \(k\) tal que la posicion de DistribuNim II formada por \(n\) montones de tamano \(n\) y un monton adicional de tamano \(n+k\) sea perdedora. El problema pide calcular
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$$
Buscar directamente en el arbol del juego es inviable para \(N\) grande. Por eso la solucion eficiente no explora estados grandes: usa una formula cerrada para cada \(t(n)\) y luego suma esa formula por bloques de longitud binaria fija.
La idea decisiva es que el desplazamiento perdedor queda determinado por la longitud binaria de \(n\), la paridad de \(n\) y los bits bajos de \(n^2\).
Sea
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
Definimos
$$\varepsilon(n)=\begin{cases} 0, & n\text{ par},\\ 2^m-1, & n\text{ impar}. \end{cases}$$
Entonces la identidad usada por la implementacion es
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$$
Es decir,
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ par},\\ (-n^2-1)\bmod 2^m, & n\text{ impar}. \end{cases}$$
Una vez conocida la longitud binaria \(m\), solo importa el residuo de \(n^2\) modulo \(2^m\).
Para cada \(m\ge 1\), definimos
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$$
Si \(n=2^r\), entonces \(n\) es par y \(n^2=2^{2r}\) es divisible por \(2^{r+1}\), de modo que \(t(2^r)=0\). Por lo tanto el extremo \(n=2^N\) tampoco aporta nada y
$$S(N)=\sum_{m=1}^{N} B_m.$$
Escribamos
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$$
Entonces
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$$
porque tanto \(2^{2m-2}\) como \(2^m j\) son multiplos de \(2^m\). Para \(m\ge 2\), el numero \(2^{m-1}\) es par, asi que \(n\) y \(j\) tienen la misma paridad. En consecuencia,
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ par},\\ (-j^2-1)\bmod 2^m, & j\text{ impar}. \end{cases}$$
Separamos el bloque en desplazamientos pares e impares:
$$j=2u\quad\text{o}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
La parte par depende de residuos de la forma \(4u^2\), mientras que la parte impar depende de residuos de la forma \(4u(u+1)+1\). Al sumar ambas familias sobre un bloque completo, se obtiene exactamente
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$$
Los primeros valores son
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$$
y ya muestran la estructura geometrica que aprovecha el programa.
Cada bloque aporta un termino \(4^{m-1}\), por lo que
$$\sum_{m=1}^{N}4^{m-1}=\frac{4^N-1}{3}.$$
Las correcciones con potencias de \(8\) aparecen por parejas. El bloque \(2k+1\) aporta \(8^k\), y el bloque siguiente \(2k+2\) aporta \(2\cdot 8^k\). Una pareja completa contribuye, por tanto, \(3\cdot 8^k\). Si
$$K=\left\lfloor \frac{N}{2}\right\rfloor,$$
la correccion total es
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ impar}}\,8^K.$$
Los terminos sustractivos suman
$$\sum_{m=1}^{N}2^m=2^{N+1}-2.$$
Por consiguiente,
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ impar}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
Tomemos \(n=6\). Aqui \(m=3\) porque \(4\le 6<8\). Como \(6\) es par,
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
Ahora \(n=5\). De nuevo \(m=3\), pero \(5\) es impar, asi que
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
Para \(N=4\), los totales de bloque son
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$$
y por tanto
$$S(4)=0+2+16+64=82.$$
Eso coincide con la suma directa de \(t(n)\) para \(1\le n\le 16\).
Las implementaciones en C++, Python y Java siguen exactamente la misma ruta rapida. Primero calculan los inversos modulares necesarios para \(1/3\) y \(1/7\). Despues obtienen \(4^N\), \(8^{\lfloor N/2\rfloor}\) y \(2^{N+1}\) mediante exponenciacion modular rapida. Esos valores se ensamblan en
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ impar}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2,$$
y la respuesta final es \(\text{sumA}+\text{sumB}-\text{sumC}\) modulo \(900497239\). La implementacion en C++ ademas conserva verificaciones pequenas: compara la formula cerrada con una suma directa para valores pequenos de \(N\) y contrasta los primeros desplazamientos perdedores con fuerza bruta. Pero el calculo final de produccion usa solo la forma cerrada.
El metodo optimizado necesita solo un numero constante de exponenciaciones modulares, por lo que su tiempo es \(O(\log N)\) y su memoria es \(O(1)\). En cambio, la definicion original ya contiene \(2^N\) terminos incluso antes de considerar cualquier exploracion del juego.
对每个正整数 \(n\)，记 \(t(n)\) 为最小偏移量 \(k\)，使得 DistribuNim II 中由 \(n\) 个大小为 \(n\) 的堆以及一个大小为 \(n+k\) 的额外堆组成的局面成为必败态。题目要求计算
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$$
如果直接搜索博弈状态，规模会随着 \(N\) 爆炸式增长，因此高效解法并不在大规模状态空间中做搜索，而是先得到每个 \(t(n)\) 的闭式表达，再按二进制位长分块求和。
优化解的核心事实是：决定必败偏移量的，不是整个局面的完整展开，而是 \(n\) 的位长、奇偶性，以及 \(n^2\) 的低位比特。
设
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
再定义
$$\varepsilon(n)=\begin{cases} 0, & n\text{ 为偶数},\\ 2^m-1, & n\text{ 为奇数}. \end{cases}$$
则实现中使用的关键恒等式是
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$$
把它写成分段形式，就是
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ 为偶数},\\ (-n^2-1)\bmod 2^m, & n\text{ 为奇数}. \end{cases}$$
因此，只要知道 \(n\) 的位长 \(m\)，再取出 \(n^2\) 的最低 \(m\) 位，就能立刻得到 \(t(n)\)。
对每个 \(m\ge 1\)，定义块和
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$$
如果 \(n=2^r\)，那么 \(n\) 是偶数，而且 \(n^2=2^{2r}\) 一定能被 \(2^{r+1}\) 整除，所以 \(t(2^r)=0\)。因此上界点 \(n=2^N\) 本身没有贡献，从而
$$S(N)=\sum_{m=1}^{N} B_m.$$
现在写成
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$$
那么
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$$
因为展开式中的 \(2^{2m-2}\) 与 \(2^m j\) 都是 \(2^m\) 的倍数。当 \(m\ge 2\) 时，\(2^{m-1}\) 是偶数，所以 \(n\) 与 \(j\) 具有相同的奇偶性。于是可以把公式改写为
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ 为偶数},\\ (-j^2-1)\bmod 2^m, & j\text{ 为奇数}. \end{cases}$$
把偏移 \(j\) 再拆成偶数与奇数两类：
$$j=2u\quad\text{或}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
偶数部分对应的是 \(4u^2\) 形式的平方剩余，奇数部分对应的是 \(4u(u+1)+1\) 形式的平方剩余。把这两类在整个块内全部求和以后，可以得到精确公式
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$$
前几个块和为
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$$
从这些数值已经可以看出后续求和中会出现等比级数结构。
每个块都含有一个 \(4^{m-1}\) 项，因此
$$\sum_{m=1}^{N}4^{m-1}=\frac{4^N-1}{3}.$$
与 \(8\) 有关的修正项按相邻块成对出现。第 \(2k+1\) 块贡献 \(8^k\)，紧接着的第 \(2k+2\) 块贡献 \(2\cdot 8^k\)，因此一对完整相邻块总共贡献 \(3\cdot 8^k\)。若记
$$K=\left\lfloor \frac{N}{2}\right\rfloor,$$
那么全部 \(8\) 次幂修正项之和为
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ 为奇数}}\,8^K.$$
所有减去的幂次项加总后正好是
$$\sum_{m=1}^{N}2^m=2^{N+1}-2.$$
于是得到最终闭式
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ 为奇数}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
先看 \(n=6\)。此时 \(m=3\)，因为 \(4\le 6<8\)。又因为 \(6\) 是偶数，所以
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
再看 \(n=5\)。这里仍然是 \(m=3\)，但 \(5\) 是奇数，因此
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
如果取 \(N=4\)，块和分别为
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$$
所以
$$S(4)=0+2+16+64=82.$$
这与直接把 \(1\le n\le 16\) 的 \(t(n)\) 全部算出后再求和的结果完全一致。
C++、Python 和 Java 实现都走同一条快速路径。首先求出分数 \(1/3\) 与 \(1/7\) 在模 \(900497239\) 下对应的模逆；然后通过快速模幂计算 \(4^N\)、\(8^{\lfloor N/2\rfloor}\) 和 \(2^{N+1}\)。接下来把这些量代入
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ 为奇数}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2,$$
最后输出 \(\text{sumA}+\text{sumB}-\text{sumC}\) 对 \(900497239\) 取模后的结果。C++ 实现还保留了小规模验证逻辑：一方面把闭式与小 \(N\) 的直接求和做对比，另一方面对前几个 \(t(n)\) 做暴力核对；但真正的正式计算完全依赖闭式本身。
优化后的方法只需要常数次快速模幂，因此时间复杂度为 \(O(\log N)\)，空间复杂度为 \(O(1)\)。相比之下，原始定义中的求和本身就有 \(2^N\) 项，更不用说若再附加博弈状态搜索，规模会远远超出可计算范围。
Для каждого положительного целого \(n\) обозначим через \(t(n)\) минимальный сдвиг \(k\), при котором позиция DistribuNim II, состоящая из \(n\) куч размера \(n\) и еще одной кучи размера \(n+k\), является проигрышной. Требуется вычислить
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$$
Прямой перебор игровых состояний слишком дорог уже для умеренных значений \(N\). Поэтому эффективное решение не строит игровой граф на больших данных, а использует явную формулу для каждого \(t(n)\), после чего суммирует ее по блокам фиксированной двоичной длины.
Главное наблюдение состоит в том, что проигрышный сдвиг определяется длиной двоичной записи числа \(n\), его четностью и младшими битами числа \(n^2\).
Пусть
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
Определим
$$\varepsilon(n)=\begin{cases} 0, & n\text{ четно},\\ 2^m-1, & n\text{ нечетно}. \end{cases}$$
Тогда используемое тождество имеет вид
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$$
То же самое можно записать так:
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ четно},\\ (-n^2-1)\bmod 2^m, & n\text{ нечетно}. \end{cases}$$
Значит, после определения длины двоичной записи \(m\) достаточно знать только остаток \(n^2\) по модулю \(2^m\).
Для каждого \(m\ge 1\) введем
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$$
Если \(n=2^r\), то \(n\) четно, а \(n^2=2^{2r}\) делится на \(2^{r+1}\), поэтому \(t(2^r)=0\). Следовательно, крайняя точка \(n=2^N\) ничего не добавляет, и
$$S(N)=\sum_{m=1}^{N} B_m.$$
Теперь представим
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$$
Тогда
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$$
поскольку и \(2^{2m-2}\), и \(2^m j\) кратны \(2^m\). При \(m\ge 2\) число \(2^{m-1}\) четно, так что \(n\) и \(j\) имеют одинаковую четность. Поэтому
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ четно},\\ (-j^2-1)\bmod 2^m, & j\text{ нечетно}. \end{cases}$$
Разделим блок на четные и нечетные сдвиги:
$$j=2u\quad\text{или}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
Четная часть строится из квадратов вида \(4u^2\), а нечетная часть из выражений вида \(4u(u+1)+1\). Суммирование по обеим классам четности на полном блоке дает точные формулы
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$$
Первые значения таковы:
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$$
и уже по ним видно, почему дальше возникают геометрические прогрессии.
Каждый блок содержит слагаемое \(4^{m-1}\), поэтому
$$\sum_{m=1}^{N}4^{m-1}=\frac{4^N-1}{3}.$$
Поправки с основанием \(8\) возникают парами. Блок \(2k+1\) дает вклад \(8^k\), следующий блок \(2k+2\) дает \(2\cdot 8^k\), так что одна полная пара дает \(3\cdot 8^k\). Если
$$K=\left\lfloor \frac{N}{2}\right\rfloor,$$
то суммарная поправка равна
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ нечетно}}\,8^K.$$
Вычитаемые степени суммируются в
$$\sum_{m=1}^{N}2^m=2^{N+1}-2.$$
Следовательно,
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ нечетно}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
Возьмем \(n=6\). Здесь \(m=3\), потому что \(4\le 6<8\). Поскольку \(6\) четно, получаем
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
Теперь \(n=5\). Снова \(m=3\), но \(5\) нечетно, значит
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
Для \(N=4\) имеем блоковые суммы
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$$
поэтому
$$S(4)=0+2+16+64=82.$$
Это совпадает с прямым суммированием \(t(n)\) для всех \(1\le n\le 16\).
Реализации на C++, Python и Java используют один и тот же быстрый путь. Сначала находятся модульные обратные для дробей \(1/3\) и \(1/7\). Затем с помощью быстрого возведения в степень по модулю вычисляются \(4^N\), \(8^{\lfloor N/2\rfloor}\) и \(2^{N+1}\). После этого формируются выражения
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ нечетно}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2,$$
и окончательный ответ равен \(\text{sumA}+\text{sumB}-\text{sumC}\) по модулю \(900497239\). В C++-версии также сохранены небольшие проверки: закрытая формула сравнивается с прямой суммой для малых \(N\), а первые значения \(t(n)\) сверяются с перебором. Но боевой результат целиком получается из закрытого выражения.
Оптимизированный метод использует лишь постоянное число модульных возведений в степень, поэтому время работы равно \(O(\log N)\), а память \(O(1)\). В исходном определении уже присутствует \(2^N\) слагаемых, и без закрытой формулы задача была бы практически недостижима.
لكل عدد صحيح موجب \(n\)، نعرّف \(t(n)\) بأنه أصغر إزاحة \(k\) تجعل وضعية DistribuNim II المؤلفة من \(n\) أكوام حجم كل منها \(n\)، مع كومة إضافية حجمها \(n+k\)، وضعية خاسرة. المطلوب هو حساب
$$S(N)=\sum_{n=1}^{2^N} t(n)\pmod{900497239}.$$
البحث المباشر في شجرة اللعب غير عملي تماما عندما يكبر \(N\). لذلك لا يعتمد الحل السريع على استكشاف الحالات الكبيرة، بل على صيغة مغلقة لكل \(t(n)\)، ثم على جمع دقيق لهذه الصيغة على كتل ذات طول ثنائي ثابت.
الفكرة الأساسية في الحل المحسن هي أن الإزاحة الخاسرة تحددها ثلاثة أمور فقط: طول التمثيل الثنائي للعدد \(n\)، وكونه زوجيا أو فرديا، والبتات الدنيا للعدد \(n^2\).
لنضع
$$m=\lfloor \log_2 n \rfloor+1,\qquad 2^{m-1}\le n<2^m.$$
ولنعرّف كذلك
$$\varepsilon(n)=\begin{cases} 0, & n\text{ even},\\ 2^m-1, & n\text{ odd}. \end{cases}$$
عندئذ تصبح الهوية المستخدمة في التنفيذ هي
$$t(n)=\bigl(\varepsilon(n)-n^2\bigr)\bmod 2^m.$$
وبشكل مكافئ،
$$t(n)=\begin{cases} (-n^2)\bmod 2^m, & n\text{ even},\\ (-n^2-1)\bmod 2^m, & n\text{ odd}. \end{cases}$$
وهذا يعني أن معرفة \(m\) تكفي مع البتات الدنيا لـ \(n^2\) لاستخراج قيمة \(t(n)\) مباشرة.
لكل \(m\ge 1\)، نعرّف
$$B_m=\sum_{n=2^{m-1}}^{2^m-1} t(n).$$
إذا كان \(n=2^r\)، فإن \(n\) زوجي و\(n^2=2^{2r}\) يقبل القسمة على \(2^{r+1}\)، ومن ثم \(t(2^r)=0\). لذلك الحد الطرفي \(n=2^N\) لا يضيف شيئا، وبالتالي
$$S(N)=\sum_{m=1}^{N} B_m.$$
اكتب الآن
$$n=2^{m-1}+j,\qquad 0\le j<2^{m-1}.$$
فنحصل على
$$n^2=(2^{m-1}+j)^2\equiv j^2 \pmod{2^m},$$
لأن كلا من \(2^{2m-2}\) و\(2^m j\) مضاعف لـ \(2^m\). وعندما يكون \(m\ge 2\)، فإن \(2^{m-1}\) عدد زوجي، ولذلك تكون فردية \(n\) هي نفسها فردية \(j\). إذن
$$t(2^{m-1}+j)=\begin{cases} (-j^2)\bmod 2^m, & j\text{ even},\\ (-j^2-1)\bmod 2^m, & j\text{ odd}. \end{cases}$$
نقسم الإزاحات إلى زوجية وفردية:
$$j=2u\quad\text{or}\quad j=2u+1,\qquad 0\le u<2^{m-2}.$$
المساهمة الزوجية تبنى من بواقي على شكل \(4u^2\)، أما المساهمة الفردية فتأتي من بواقي على شكل \(4u(u+1)+1\). وعند جمع هاتين الفئتين على كتلة كاملة نحصل على الصيغ الدقيقة
$$B_{2k}=4^{2k-1}+2\cdot 8^{k-1}-2^{2k},\qquad k\ge 1,$$
$$B_{2k+1}=4^{2k}+8^k-2^{2k+1},\qquad k\ge 0.$$
وأول القيم هي
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,\qquad B_5=288,$$
وهذا يوضح مباشرة لماذا تظهر متسلسلات هندسية في الصيغة النهائية.
كل كتلة تحتوي على حد من الشكل \(4^{m-1}\)، ولذلك
$$\sum_{m=1}^{N}4^{m-1}=\frac{4^N-1}{3}.$$
أما تصحيحات قوى \(8\) فتأتي على شكل أزواج متجاورة. الكتلة \(2k+1\) تضيف \(8^k\)، والكتلة التي تليها \(2k+2\) تضيف \(2\cdot 8^k\)، أي أن كل زوج كامل يضيف \(3\cdot 8^k\). وإذا وضعنا
$$K=\left\lfloor \frac{N}{2}\right\rfloor,$$
فإن مجموع هذه التصحيحات يساوي
$$\frac{3(8^K-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^K.$$
أما الحدود المطروحة فمجموعها
$$\sum_{m=1}^{N}2^m=2^{N+1}-2.$$
ومن ثم نحصل على الصيغة النهائية
$$\boxed{S(N)=\frac{4^N-1}{3}+\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^{\lfloor N/2\rfloor}-(2^{N+1}-2)\pmod{900497239}.}$$
خذ \(n=6\). هنا \(m=3\) لأن \(4\le 6<8\). وبما أن \(6\) زوجي، فإن
$$t(6)=(-6^2)\bmod 8=(-36)\bmod 8=4.$$
أما إذا أخذنا \(n=5\)، فلدينا أيضا \(m=3\)، لكن \(5\) فردي، ولذلك
$$t(5)=(-5^2-1)\bmod 8=(-26)\bmod 8=6.$$
ولحالة \(N=4\) تكون مجاميع الكتل
$$B_1=0,\qquad B_2=2,\qquad B_3=16,\qquad B_4=64,$$
ومن ثم
$$S(4)=0+2+16+64=82.$$
وهذه القيمة تطابق تماما الجمع المباشر لـ \(t(n)\) من \(1\) إلى \(16\).
تتبع تطبيقات C++ وPython وJava المسار السريع نفسه. أولا تحسب المعكوسات المعيارية اللازمة للكسرين \(1/3\) و\(1/7\). بعد ذلك تحسب \(4^N\) و\(8^{\lfloor N/2\rfloor}\) و\(2^{N+1}\) باستعمال الأسس المعيارية السريعة. ثم تجمع هذه القيم في
$$\text{sumA}=\frac{4^N-1}{3},\qquad \text{sumB}=\frac{3(8^{\lfloor N/2\rfloor}-1)}{7}+\mathbf{1}_{N\text{ odd}}\,8^{\lfloor N/2\rfloor},\qquad \text{sumC}=2^{N+1}-2,$$
ويكون الناتج النهائي هو \(\text{sumA}+\text{sumB}-\text{sumC}\) بترديد \(900497239\). كما تحتفظ نسخة C++ بطبقة تحقق صغيرة: فهي تقارن الصيغة المغلقة مع جمع مباشر عندما يكون \(N\) صغيرا، وتراجع أولى قيم \(t(n)\) بمقارنة مع brute force. لكن الحساب الإنتاجي النهائي يعتمد كليا على الصيغة المغلقة.
الطريقة المحسنة تحتاج فقط إلى عدد ثابت من عمليات الأسس المعيارية السريعة، ولذلك فإن الزمن \(O(\log N)\) والذاكرة \(O(1)\). أما الصياغة الأصلية للمجموع فتحتوي بنفسها على \(2^N\) حدا قبل أي بحث في فضاء اللعب، ولهذا كانت الصيغة المغلقة ضرورية.