For each \(n\), the repository code computes a value \(m(n)\) and then adds \(m(n)^3\) to the global sum $$\sum_{n=1}^{1000} m(n)^3.$$ The important point is that the local solutions do not use a short closed form. Instead they model the game by repeatedly composing residue maps on \(R_n=\{0,1,\dots,n\}\) and stop as soon as the diagonal row becomes constant. The checkpoints hard-coded in all three implementations are \(m(2)=2\), \(m(7)=1\), \(m(20)=4\), and \(\sum_{n=1}^{20} m(n)^3=8150\).
Fix \(n\) and set \(M=n+1\). Every table entry is a function value on the residue set \(R_n=\{0,1,\dots,n\}\). The code does not use ordinary addition modulo \(M\). Instead it uses the truncated shift
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
That distinction matters: ordinary modular addition would send \(M-1+k\) to \(k-1\), but the program sends every overflow directly to \(0\). This is exactly what the line if (value >= step) value = 0; implements in C++, Python, and Java.
Let \(F_s^{(m)}:R_n \to R_n\) denote the map stored in row \(m\) after stage \(s\) has finished. Row \(0\) is always the identity map:
$$F_s^{(0)}(v)=v.$$
The code initializes stage \(0\) with \(F_0^{(0)}=\mathrm{id}\), and for every later stage it builds row \(m\) from the previous row of the current stage and the previous row of the previous stage. Written mathematically, the update is
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
Evaluated at a residue \(v\), this becomes
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$$
In particular, \(F_s^{(1)}=\sigma_s\), so the first row of every stage is just the raw truncated shift. This recurrence is the mathematical core of the implementation; there is no hidden algebraic shortcut in the source files.
After stage \(s\), the program inspects the diagonal row \(F_s^{(s)}\). If every residue gives the same output, then the row has collapsed to a constant map:
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
The solver then returns that constant \(c\), which is exactly the value denoted by \(m(n)\) in the code path. So the algorithm searches for the first stage at which repeated composition of these truncated shifts destroys all dependence on the starting residue.
The search is guaranteed to succeed by stage \(M=n+1\). Indeed, \(\sigma_M\) is already the constant-zero map, hence \(F_M^{(1)}\) is constant. If \(F_M^{(m-1)}\) is constant, then \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) is also constant, so applying \(F_{M-1}^{(m-1)}\) still gives a constant. By induction, every row of stage \(M\) is constant, especially the diagonal row \(F_M^{(M)}\).
For \(n=2\), we work on \(R_2=\{0,1,2\}\) with \(M=3\). The first-stage row is simply \(F_1^{(1)}=\sigma_1\), so
$$F_1^{(1)}=[1,2,0].$$
At stage \(2\), the first row is \(F_2^{(1)}=\sigma_2=[2,0,0]\). The second row becomes
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$$
which yields
$$F_2^{(2)}=[1,2,2].$$
This row is not constant, so the algorithm continues. At stage \(3\), \(\sigma_3\) is the constant-zero map, hence
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
The diagonal row is now constant, so \(m(2)=2\), exactly matching the validation embedded in every solution file.
The outer driver runs this procedure for every \(1 \le n \le 1000\) and accumulates
$$\sum_{n=1}^{1000} m(n)^3.$$
Before trusting the long run, the implementations verify the small checkpoints \(m(2)=2\), \(m(7)=1\), \(m(20)=4\), and the partial cube-sum \(8150\) through \(n=20\). Those checks are important because the recurrence is subtle and because the allocated table buffers are reused across successive \(n\)-values for efficiency.
The C++ version stores the two tables in flat arrays and addresses row \(m\), column \(v\) by index(m, v) = (m << SHIFT) + v with SHIFT = 10. Since \(2^{10}=1024 > 1000\), each logical row fits in a fixed stride of 1024 entries. Python uses the same flattened indexing, and Java mirrors the same memory layout with two int[] buffers.
Inside compute_m or computeM, row 0 is the identity map. For each stage s, the code fills rows 1 through s using the recurrence above, tests whether row s is constant, and swaps the two work buffers if another stage is needed. The three languages therefore implement the same mathematics with only syntactic differences: pointer swapping in C++, tuple reassignment in Python, and reference swapping in Java.
For a fixed \(n\), the inner update performs one constant-time transition for every triple \((s,m,v)\) with \(1 \le s \le n+1\), \(1 \le m \le s\), and \(0 \le v \le n\). Therefore
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
The constant-row check adds only \(O(n)\) per stage and does not change the order. The logical table size is two arrays of roughly \((n+1)^2\) entries, so the working memory is \(O(n^2)\). In the repository implementation, this is realized with two fixed \(1024 \times 1024\) buffers because the maximum requested \(n\) is \(1000\).
Für jedes \(n\) berechnet der Repository-Code einen Wert \(m(n)\) und addiert anschließend \(m(n)^3\) zur Gesamtsumme $$\sum_{n=1}^{1000} m(n)^3.$$ Entscheidend ist, dass die lokalen Lösungen keine kurze geschlossene Formel verwenden. Stattdessen modellieren sie das Spiel durch wiederholte Komposition von Restklassenabbildungen auf \(R_n=\{0,1,\dots,n\}\) und stoppen, sobald die Diagonalzeile konstant wird. In allen drei Implementierungen sind die Kontrollwerte \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) und \(\sum_{n=1}^{20} m(n)^3=8150\) fest eingebaut.
Fixiere \(n\) und setze \(M=n+1\). Jeder Tabelleneintrag ist ein Funktionswert auf der Restmenge \(R_n=\{0,1,\dots,n\}\). Der Code verwendet keine gewöhnliche Addition modulo \(M\), sondern die abgeschnittene Verschiebung
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
Dieser Unterschied ist wesentlich: Normale Modulo-Addition würde \(M-1+k\) auf \(k-1\) abbilden, das Programm schickt jeden Überlauf jedoch direkt auf \(0\). Genau das wird durch die Zeile if (value >= step) value = 0; in C++, Python und Java umgesetzt.
Sei \(F_s^{(m)}:R_n \to R_n\) die Abbildung, die nach Abschluss der Stufe \(s\) in Zeile \(m\) gespeichert ist. Zeile \(0\) ist stets die Identität:
$$F_s^{(0)}(v)=v.$$
Der Code initialisiert Stufe \(0\) mit \(F_0^{(0)}=\mathrm{id}\). Danach wird in jeder späteren Stufe Zeile \(m\) aus der vorherigen Zeile der aktuellen Stufe und der vorherigen Zeile der vorigen Stufe aufgebaut. Mathematisch lautet das Update
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
Ausgewertet an einem Rest \(v\) ist das
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$$
Insbesondere gilt \(F_s^{(1)}=\sigma_s\), also ist die erste Zeile jeder Stufe einfach die rohe abgeschnittene Verschiebung. Diese Rekurrenz ist der mathematische Kern der Implementierung; eine versteckte algebraische Abkürzung gibt es in den Quelldateien nicht.
Nach Stufe \(s\) untersucht das Programm die Diagonalzeile \(F_s^{(s)}\). Wenn jeder Rest denselben Ausgabewert liefert, ist diese Zeile zu einer konstanten Abbildung kollabiert:
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
Dann gibt der Solver genau diese Konstante \(c\) zurück; das ist der Wert, der im Code als \(m(n)\) erscheint. Der Algorithmus sucht also die erste Stufe, in der die wiederholte Komposition der abgeschnittenen Verschiebungen jede Abhängigkeit vom Startrest eliminiert.
Spätestens bei Stufe \(M=n+1\) muss die Suche erfolgreich sein. Denn \(\sigma_M\) ist bereits die konstante Nullabbildung, also ist \(F_M^{(1)}\) konstant. Ist \(F_M^{(m-1)}\) konstant, dann ist auch \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) konstant; nach Anwendung von \(F_{M-1}^{(m-1)}\) bleibt die Konstanz erhalten. Per Induktion sind somit alle Zeilen der Stufe \(M\) konstant, insbesondere die Diagonalzeile \(F_M^{(M)}\).
Für \(n=2\) arbeiten wir auf \(R_2=\{0,1,2\}\) mit \(M=3\). Die erste Zeile der ersten Stufe ist schlicht \(F_1^{(1)}=\sigma_1\), also
$$F_1^{(1)}=[1,2,0].$$
In Stufe \(2\) ist die erste Zeile \(F_2^{(1)}=\sigma_2=[2,0,0]\). Die zweite Zeile ist dann
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$$
und daraus ergibt sich
$$F_2^{(2)}=[1,2,2].$$
Diese Zeile ist noch nicht konstant, also geht der Algorithmus weiter. In Stufe \(3\) ist \(\sigma_3\) die konstante Nullabbildung, daher
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
Die Diagonalzeile ist nun konstant, also \(m(2)=2\), genau wie in jeder Lösungsdatei validiert.
Der äußere Treiber führt dieses Verfahren für alle \(1 \le n \le 1000\) aus und akkumuliert
$$\sum_{n=1}^{1000} m(n)^3.$$
Bevor der lange Lauf akzeptiert wird, prüfen die Implementierungen die kleinen Kontrollwerte \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) und die Teilsumme \(8150\) bis \(n=20\). Diese Tests sind wichtig, weil die Rekurrenz subtil ist und weil die allokierten Tabellenpuffer aus Effizienzgründen über aufeinanderfolgende \(n\)-Werte hinweg wiederverwendet werden.
Die C++-Version speichert die beiden Tabellen in flachen Arrays und adressiert Zeile \(m\), Spalte \(v\) über index(m, v) = (m << SHIFT) + v mit SHIFT = 10. Da \(2^{10}=1024 > 1000\), passt jede logische Zeile in einen festen Zeilensprung von 1024 Einträgen. Python verwendet dieselbe flache Indexierung, und Java spiegelt dasselbe Layout mit zwei int[]-Puffern.
Innerhalb von compute_m beziehungsweise computeM ist Zeile 0 die Identitätsabbildung. Für jede Stufe s füllt der Code die Zeilen 1 bis s gemäß der obigen Rekurrenz, prüft dann, ob Zeile s konstant ist, und vertauscht die beiden Arbeitspuffer, falls eine weitere Stufe nötig ist. Die drei Sprachen implementieren also dieselbe Mathematik mit nur syntaktischen Unterschieden: Zeiger-Tausch in C++, Tupel-artige Zuweisung in Python und Referenz-Tausch in Java.
Für festes \(n\) führt das innere Update genau einen konstanten Übergang für jedes Tripel \((s,m,v)\) mit \(1 \le s \le n+1\), \(1 \le m \le s\) und \(0 \le v \le n\) aus. Damit gilt
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
Die Prüfung auf Konstanz der Diagonalzeile fügt nur \(O(n)\) pro Stufe hinzu und ändert die Größenordnung nicht. Die logische Tabellengröße besteht aus zwei Arrays mit ungefähr \((n+1)^2\) Einträgen, also beträgt der Arbeitspeicher \(O(n^2)\). In der Repository-Implementierung wird dies durch zwei feste \(1024 \times 1024\)-Puffer realisiert, weil maximal \(n=1000\) verlangt wird.
Depodaki kod her \(n\) için bir \(m(n)\) değeri hesaplıyor ve sonra bu değerin küpünü toplamın içine ekliyor: $$\sum_{n=1}^{1000} m(n)^3.$$ Buradaki önemli nokta, yerel çözümlerin kısa bir kapalı form kullanmamasıdır. Bunun yerine oyun, \(R_n=\{0,1,\dots,n\}\) üzerinde tanımlı kalan-sınıfı dönüşümlerinin art arda bileşimi olarak modellenir ve köşegen satır sabit hale gelir gelmez işlem durur. Üç uygulamanın da içine gömülü kontrol değerleri \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) ve \(\sum_{n=1}^{20} m(n)^3=8150\) biçimindedir.
\(n\)'yi sabitleyip \(M=n+1\) alalım. Tablodaki her giriş, \(R_n=\{0,1,\dots,n\}\) kümesi üzerindeki bir fonksiyon değeridir. Kod, standart mod \(M\) toplaması yapmıyor; onun yerine şu kesilmiş kaydırmayı kullanıyor:
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
Bu fark kritiktir: Normal modüler toplama \(M-1+k\) değerini \(k-1\)'e indirgerdi, fakat program her taşmayı doğrudan \(0\)'a çevirir. C++, Python ve Java dosyalarındaki if (value >= step) value = 0; satırı tam olarak bunu uygular.
\(F_s^{(m)}:R_n \to R_n\) fonksiyonu, \(s\) aşaması tamamlandıktan sonra \(m\). satırda saklanan dönüşüm olsun. \(0\). satır her zaman özdeşliktir:
$$F_s^{(0)}(v)=v.$$
Kod, \(0\). aşamayı \(F_0^{(0)}=\mathrm{id}\) ile başlatır. Sonraki her aşamada ise \(m\). satır, hem mevcut aşamanın bir önceki satırından hem de bir önceki aşamanın bir önceki satırından üretilir. Matematiksel yazımı şöyledir:
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
Bir \(v\) kalıntısında bu ifade
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right)$$
şeklindedir. Özellikle \(F_s^{(1)}=\sigma_s\) olur; yani her aşamanın ilk satırı doğrudan kesilmiş kaydırmadır. Kaynak dosyalardaki matematiksel öz tam olarak bu yinelemedir; gizli bir cebirsel kısayol yoktur.
Her \(s\) aşamasının sonunda program köşegen satır \(F_s^{(s)}\)'yi kontrol eder. Eğer bütün kalıntılar aynı çıktıyı veriyorsa, bu satır sabit bir fonksiyona çökmüş demektir:
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
Çözücü bu sabit \(c\) değerini döndürür; kodda \(m(n)\) diye kullanılan nicelik tam olarak budur. Yani algoritma, kesilmiş kaydırmaların art arda bileşimlerinin başlangıç kalıntısına olan bağımlılığı ilk kez hangi aşamada tamamen yok ettiğini arar.
Arama en geç \(M=n+1\) aşamasında başarıya ulaşmak zorundadır. Çünkü \(\sigma_M\) zaten sabit-sıfır fonksiyonudur; dolayısıyla \(F_M^{(1)}\) sabittir. Eğer \(F_M^{(m-1)}\) sabitse, o zaman \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) da sabittir ve bunun üzerine \(F_{M-1}^{(m-1)}\) uygulanınca sonuç yine sabit kalır. Böylece tümevarım ile \(M\). aşamadaki bütün satırların, özellikle de köşegen satır \(F_M^{(M)}\)'in sabit olduğu görülür.
\(n=2\) için \(R_2=\{0,1,2\}\) ve \(M=3\) üzerinde çalışırız. İlk aşamanın tek satırı \(F_1^{(1)}=\sigma_1\) olduğundan
$$F_1^{(1)}=[1,2,0].$$
\(2\). aşamada ilk satır \(F_2^{(1)}=\sigma_2=[2,0,0]\) olur. İkinci satır ise
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right)$$
olduğundan
$$F_2^{(2)}=[1,2,2]$$
elde edilir. Bu satır sabit değildir; dolayısıyla algoritma devam eder. \(3\). aşamada \(\sigma_3\) sabit-sıfır fonksiyonu olduğu için
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
Köşegen satır artık sabittir; bu yüzden \(m(2)=2\). Bu da tüm çözüm dosyalarındaki doğrulama ile aynıdır.
Dış sürücü bu işlemi \(1 \le n \le 1000\) aralığındaki bütün \(n\)'ler için çalıştırır ve
$$\sum_{n=1}^{1000} m(n)^3$$
toplamını biriktirir. Uzun çalışmaya güvenmeden önce uygulamalar \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) ve \(n=20\)'ye kadarki küp toplamının \(8150\) olduğunu kontrol eder. Bu testler önemlidir; çünkü yineleme hassastır ve ayrılmış tablo tamponları verim için art arda gelen \(n\) değerlerinde yeniden kullanılır.
C++ sürümü iki tabloyu düz dizilerde saklar ve \(m\). satır ile \(v\). sütuna index(m, v) = (m << SHIFT) + v formülüyle erişir; burada SHIFT = 10'dur. \(2^{10}=1024 > 1000\) olduğundan her mantıksal satır sabit 1024 uzunluklu bir adım içinde yerleşir. Python aynı düz indekslemeyi kullanır; Java da iki int[] tamponuyla aynı düzeni tekrarlar.
compute_m ya da computeM içinde \(0\). satır özdeşliktir. Her s aşamasında kod, yukarıdaki yinelemeye göre 1'den s'ye kadar olan satırları doldurur, sonra s. satırın sabit olup olmadığını sınar ve gerekirse iki çalışma tamponunu yer değiştirir. Bu nedenle üç dil aynı matematiği uygular; farklar yalnızca söz dizimindedir: C++'ta işaretçi takası, Python'da çoklu atama ve Java'da referans takası.
Sabit bir \(n\) için iç güncelleme, \(1 \le s \le n+1\), \(1 \le m \le s\) ve \(0 \le v \le n\) koşullarını sağlayan her \((s,m,v)\) üçlüsü için bir sabit-zaman geçiş yapar. Dolayısıyla
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
Köşegen satırın sabitlik testi her aşamada yalnızca \(O(n)\) ekler ve mertebeyi değiştirmez. Mantıksal tablo boyutu yaklaşık \((n+1)^2\) elemanlı iki dizi olduğundan çalışma belleği \(O(n^2)\)'dir. Depodaki uygulama bunu iki adet sabit \(1024 \times 1024\) tamponla gerçekleştirir; çünkü istenen en büyük değer \(n=1000\)'dir.
Para cada \(n\), el código del repositorio calcula un valor \(m(n)\) y después añade \(m(n)^3\) a la suma global $$\sum_{n=1}^{1000} m(n)^3.$$ Lo importante es que las soluciones locales no usan una fórmula cerrada corta. En su lugar, modelan el juego como composiciones repetidas de aplicaciones sobre residuos en \(R_n=\{0,1,\dots,n\}\) y se detienen en cuanto la fila diagonal se vuelve constante. Los puntos de control codificados en las tres implementaciones son \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) y \(\sum_{n=1}^{20} m(n)^3=8150\).
Fijemos \(n\) y pongamos \(M=n+1\). Cada entrada de la tabla es el valor de una función sobre el conjunto residual \(R_n=\{0,1,\dots,n\}\). El código no usa la suma ordinaria módulo \(M\); en cambio usa el desplazamiento truncado
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
La diferencia es esencial: la suma modular normal enviaría \(M-1+k\) a \(k-1\), pero el programa envía cualquier desbordamiento directamente a \(0\). Eso es exactamente lo que implementa la línea if (value >= step) value = 0; en C++, Python y Java.
Sea \(F_s^{(m)}:R_n \to R_n\) la aplicación almacenada en la fila \(m\) tras terminar la etapa \(s\). La fila \(0\) es siempre la identidad:
$$F_s^{(0)}(v)=v.$$
El código inicia la etapa \(0\) con \(F_0^{(0)}=\mathrm{id}\), y en cada etapa posterior construye la fila \(m\) a partir de la fila anterior de la etapa actual y de la fila anterior de la etapa previa. Escrito de forma matemática, la actualización es
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
Evaluada en un residuo \(v\), queda
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$$
En particular, \(F_s^{(1)}=\sigma_s\), así que la primera fila de cada etapa es simplemente el desplazamiento truncado puro. Esta recurrencia es el núcleo matemático de la implementación; los archivos fuente no esconden un atajo algebraico adicional.
Después de la etapa \(s\), el programa inspecciona la fila diagonal \(F_s^{(s)}\). Si todos los residuos producen la misma salida, esa fila se ha colapsado a una aplicación constante:
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
El solver devuelve entonces esa constante \(c\), que es precisamente el valor que el código llama \(m(n)\). En otras palabras, el algoritmo busca la primera etapa en la que la composición repetida de estos desplazamientos truncados elimina toda dependencia del residuo inicial.
La búsqueda está garantizada como máximo en la etapa \(M=n+1\). En efecto, \(\sigma_M\) ya es la aplicación constante cero, así que \(F_M^{(1)}\) es constante. Si \(F_M^{(m-1)}\) es constante, entonces \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) también lo es, y al aplicar \(F_{M-1}^{(m-1)}\) la constancia se conserva. Por inducción, todas las filas de la etapa \(M\) son constantes, en particular la diagonal \(F_M^{(M)}\).
Para \(n=2\) trabajamos en \(R_2=\{0,1,2\}\) con \(M=3\). La primera fila de la etapa 1 es simplemente \(F_1^{(1)}=\sigma_1\), por lo que
$$F_1^{(1)}=[1,2,0].$$
En la etapa 2, la primera fila es \(F_2^{(1)}=\sigma_2=[2,0,0]\). La segunda fila queda
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$$
lo que produce
$$F_2^{(2)}=[1,2,2].$$
Esa fila no es constante, así que el algoritmo continúa. En la etapa 3, \(\sigma_3\) es la aplicación constante cero, y por tanto
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
La fila diagonal ya es constante, de modo que \(m(2)=2\), exactamente como verifican todos los archivos de solución.
El controlador exterior ejecuta este procedimiento para todos los \(n\) con \(1 \le n \le 1000\) y acumula
$$\sum_{n=1}^{1000} m(n)^3.$$
Antes de confiar en la ejecución larga, las implementaciones comprueban los hitos pequeños \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) y la suma parcial de cubos \(8150\) hasta \(n=20\). Esas comprobaciones son importantes porque la recurrencia es delicada y porque los búferes de tabla ya reservados se reutilizan para sucesivos valores de \(n\).
La versión en C++ guarda las dos tablas en arreglos planos y direcciona la fila \(m\), columna \(v\) mediante index(m, v) = (m << SHIFT) + v con SHIFT = 10. Como \(2^{10}=1024 > 1000\), cada fila lógica cabe en un salto fijo de 1024 entradas. Python usa el mismo índice aplanado y Java reproduce exactamente el mismo diseño con dos búferes int[].
Dentro de compute_m o computeM, la fila 0 es la identidad. En cada etapa s, el código rellena las filas 1 hasta s con la recurrencia anterior, comprueba si la fila s es constante y, si hace falta otra etapa, intercambia los dos búferes de trabajo. Así, los tres lenguajes implementan la misma matemática con diferencias solo sintácticas: intercambio de punteros en C++, reasignación múltiple en Python e intercambio de referencias en Java.
Para un \(n\) fijo, la actualización interna realiza una transición de tiempo constante para cada triple \((s,m,v)\) con \(1 \le s \le n+1\), \(1 \le m \le s\) y \(0 \le v \le n\). Por tanto,
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
La comprobación de si la fila diagonal es constante añade solo \(O(n)\) por etapa y no cambia el orden dominante. El tamaño lógico de las tablas es el de dos arreglos de aproximadamente \((n+1)^2\) entradas, así que la memoria de trabajo es \(O(n^2)\). En la implementación del repositorio, esto se materializa con dos búferes fijos de \(1024 \times 1024\), porque el mayor valor solicitado es \(n=1000\).
对每个 \(n\)，仓库里的代码都会先算出一个 \(m(n)\)，再把 \(m(n)^3\) 加到总和里： $$\sum_{n=1}^{1000} m(n)^3.$$ 关键在于，本仓库的解法并没有使用一个简短的闭式公式。它把游戏转写成定义在 \(R_n=\{0,1,\dots,n\}\) 上的一族剩余类映射，并不断做函数复合；一旦对角行变成常值行，就立即返回。三份实现里写死的校验点是 \(m(2)=2\)、\(m(7)=1\)、\(m(20)=4\)，以及 \(\sum_{n=1}^{20} m(n)^3=8150\)。
固定 \(n\)，记 \(M=n+1\)。表中的每个条目都可以看成定义在剩余集合 \(R_n=\{0,1,\dots,n\}\) 上的函数值。代码并不是做普通的模 \(M\) 加法，而是使用下面这个截断平移：
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
这点非常重要。普通模运算会把 \(M-1+k\) 送到 \(k-1\)，而程序一旦发现越界，就直接压成 \(0\)。C++、Python、Java 中的 if (value >= step) value = 0; 正是在实现这个“溢出归零”规则。
设 \(F_s^{(m)}:R_n \to R_n\) 表示第 \(s\) 个阶段结束后，第 \(m\) 行里存放的映射。第 \(0\) 行永远是恒等映射：
$$F_s^{(0)}(v)=v.$$
代码用 \(F_0^{(0)}=\mathrm{id}\) 作为第 0 阶段的初始状态。之后在每个阶段里，第 \(m\) 行都由“当前阶段的上一行”和“上一阶段的上一行”共同生成。把代码改写成数学式，就是
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
对某个具体残值 \(v\) 来说，就是
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$$
特别地，\(F_s^{(1)}=\sigma_s\)，也就是说每个阶段的第一行就是最原始的截断平移。源码中的数学本体就是这套递推，而不是别的隐藏公式。
在阶段 \(s\) 结束后，程序会检查对角行 \(F_s^{(s)}\)。如果所有初始残值都得到同一个输出，那么这一行已经塌缩成常值映射：
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
此时求解器就返回这个常数 \(c\)，它正是代码里记作 \(m(n)\) 的量。换句话说，算法寻找的是“从哪个阶段开始，反复复合这些截断平移后，结果不再依赖起始残值”。
而且这个搜索最晚一定会在 \(M=n+1\) 时成功。因为 \(\sigma_M\) 本身就是恒为 \(0\) 的映射，所以 \(F_M^{(1)}\) 已经是常值。如果 \(F_M^{(m-1)}\) 是常值，那么 \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) 也是常值，再套上 \(F_{M-1}^{(m-1)}\) 后仍然是常值。对 \(m\) 做归纳，就知道第 \(M\) 阶段的每一行都是常值，尤其是对角行 \(F_M^{(M)}\)。
当 \(n=2\) 时，我们在 \(R_2=\{0,1,2\}\) 上工作，并且 \(M=3\)。第一阶段只有一行，而且 \(F_1^{(1)}=\sigma_1\)，所以
$$F_1^{(1)}=[1,2,0].$$
到第二阶段，第一行变成 \(F_2^{(1)}=\sigma_2=[2,0,0]\)。第二行满足
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$$
于是得到
$$F_2^{(2)}=[1,2,2].$$
这还不是常值行，所以算法继续。到了第三阶段，\(\sigma_3\) 已经是常零映射，因此
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
此时对角行成为常值，于是 \(m(2)=2\)。这与三份源码里的校验结果完全一致。
外层驱动会对所有 \(1 \le n \le 1000\) 重复上述过程，并累加
$$\sum_{n=1}^{1000} m(n)^3.$$
在进行完整长跑之前，程序会先检查 \(m(2)=2\)、\(m(7)=1\)、\(m(20)=4\)，以及到 \(n=20\) 为止的立方和 \(8150\)。这些校验很有必要，因为递推本身并不直观，而且为了效率，已经分配好的表缓冲区会在不同的 \(n\) 之间重复使用。
C++ 版本把两张表都存成一维数组，并用 index(m, v) = (m << SHIFT) + v 来定位第 \(m\) 行第 \(v\) 列，其中 SHIFT = 10。因为 \(2^{10}=1024 > 1000\)，所以每个逻辑行都能放进固定步长 1024 的存储布局里。Python 使用完全相同的扁平索引，Java 也用两个 int[] 缓冲区复现了同样的内存结构。
在 compute_m 或 computeM 中，第 0 行是恒等映射。对每个阶段 s，代码先按上面的递推填出第 1 到第 s 行，再检查第 s 行是否已经常值；如果还没有，就交换两块工作缓冲区。三种语言实现的数学内容完全一致，只是语法形式不同：C++ 交换指针，Python 交换变量绑定，Java 交换数组引用。
对固定的 \(n\)，内部更新会对所有满足 \(1 \le s \le n+1\)、\(1 \le m \le s\)、\(0 \le v \le n\) 的三元组 \((s,m,v)\) 各做一次常数时间操作。因此
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
每个阶段额外做一次常值检测，只需 \(O(n)\)，不会改变主导阶。逻辑上需要两张大约 \((n+1)^2\) 大小的表，所以工作内存为 \(O(n^2)\)。在仓库实现中，这被具体写成两个固定的 \(1024 \times 1024\) 缓冲区，因为题目只要求到 \(n=1000\)。
Для каждого \(n\) код в репозитории вычисляет значение \(m(n)\), а затем добавляет \(m(n)^3\) к общей сумме $$\sum_{n=1}^{1000} m(n)^3.$$ Важно, что локальные решения не опираются на короткую замкнутую формулу. Вместо этого игра кодируется как многократная композиция отображений на остатках из множества \(R_n=\{0,1,\dots,n\}\), и работа прекращается, как только диагональная строка становится константной. Во всех трёх реализациях зашиты проверки \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) и \(\sum_{n=1}^{20} m(n)^3=8150\).
Зафиксируем \(n\) и положим \(M=n+1\). Каждая запись таблицы является значением функции на множестве остатков \(R_n=\{0,1,\dots,n\}\). Код не использует обычное сложение по модулю \(M\); вместо этого применяется усечённый сдвиг
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
Это принципиально важно: стандартная модульная арифметика отправила бы \(M-1+k\) в \(k-1\), а программа переводит любое переполнение сразу в \(0\). Именно это делает строка if (value >= step) value = 0; в версиях на C++, Python и Java.
Пусть \(F_s^{(m)}:R_n \to R_n\) обозначает отображение, записанное в строке \(m\) после завершения этапа \(s\). Строка \(0\) всегда является тождественным отображением:
$$F_s^{(0)}(v)=v.$$
Код начинает с этапа \(0\), где \(F_0^{(0)}=\mathrm{id}\). Затем на каждом новом этапе строка \(m\) строится из предыдущей строки текущего этапа и предыдущей строки прошлого этапа. В математической форме обновление имеет вид
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
Если расписать это по остатку \(v\), получаем
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$$
В частности, \(F_s^{(1)}=\sigma_s\), то есть первая строка каждого этапа есть просто исходный усечённый сдвиг. Именно эта рекурсия и составляет математическое содержание реализации; никакой дополнительной скрытой формулы в исходниках нет.
После этапа \(s\) программа проверяет диагональную строку \(F_s^{(s)}\). Если все начальные остатки приводят к одному и тому же значению, то эта строка стала константным отображением:
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
Тогда решатель возвращает эту константу \(c\); именно она и называется \(m(n)\) в коде. Итак, алгоритм ищет первый этап, на котором многократная композиция усечённых сдвигов полностью уничтожает зависимость от стартового остатка.
Успех гарантирован не позднее этапа \(M=n+1\). Действительно, \(\sigma_M\) уже является постоянной нулевой функцией, значит \(F_M^{(1)}\) константна. Если \(F_M^{(m-1)}\) константна, то и \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) константна, а после применения \(F_{M-1}^{(m-1)}\) константность сохраняется. По индукции все строки этапа \(M\) константны, в частности диагональная строка \(F_M^{(M)}\).
При \(n=2\) мы работаем на \(R_2=\{0,1,2\}\) и имеем \(M=3\). Первая строка первого этапа равна \(F_1^{(1)}=\sigma_1\), то есть
$$F_1^{(1)}=[1,2,0].$$
На этапе \(2\) первая строка равна \(F_2^{(1)}=\sigma_2=[2,0,0]\). Вторая строка вычисляется по формуле
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$$
откуда получается
$$F_2^{(2)}=[1,2,2].$$
Эта строка ещё не константна, поэтому алгоритм идёт дальше. На этапе \(3\) отображение \(\sigma_3\) уже постоянно равно нулю, следовательно
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
Диагональная строка стала константной, значит \(m(2)=2\), что в точности совпадает со встроенной проверкой во всех файлах решения.
Внешний цикл запускает эту процедуру для всех \(1 \le n \le 1000\) и накапливает
$$\sum_{n=1}^{1000} m(n)^3.$$
Прежде чем доверять длинному прогону, реализации проверяют малые контрольные значения \(m(2)=2\), \(m(7)=1\), \(m(20)=4\) и частичную сумму кубов \(8150\) до \(n=20\). Эти проверки существенны, потому что сама рекурсия нетривиальна, а заранее выделенные табличные буферы для эффективности переиспользуются при последовательных значениях \(n\).
Версия на C++ хранит обе таблицы в плоских массивах и адресует строку \(m\), столбец \(v\) формулой index(m, v) = (m << SHIFT) + v при SHIFT = 10. Так как \(2^{10}=1024 > 1000\), каждая логическая строка помещается в фиксированный шаг длины 1024. Python использует ту же плоскую индексацию, а Java повторяет ту же схему памяти двумя буферами int[].
Внутри compute_m или computeM строка 0 является тождественной функцией. Для каждого этапа s код заполняет строки от 1 до s по приведённой выше рекурсии, затем проверяет, стала ли строка s константной, и при необходимости меняет местами два рабочих буфера. Тем самым все три языка реализуют одну и ту же математику, различаясь только синтаксисом: обмен указателей в C++, множественное присваивание в Python и обмен ссылок в Java.
Для фиксированного \(n\) внутреннее обновление выполняет один переход постоянной стоимости для каждого тройного индекса \((s,m,v)\), где \(1 \le s \le n+1\), \(1 \le m \le s\) и \(0 \le v \le n\). Поэтому
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
Проверка диагональной строки на константность добавляет лишь \(O(n)\) на этап и не меняет порядка роста. Логически требуется две таблицы примерно по \((n+1)^2\) ячеек, значит рабочая память равна \(O(n^2)\). В реализации репозитория это выражено как два фиксированных буфера размера \(1024 \times 1024\), поскольку максимальное требуемое значение равно \(n=1000\).
لكل \(n\) تحسب الشيفرة الموجودة في المستودع قيمة \(m(n)\)، ثم تضيف \(m(n)^3\) إلى المجموع الكلي $$\sum_{n=1}^{1000} m(n)^3.$$ والنقطة الأساسية هنا أن الحلول المحلية لا تعتمد على صيغة مغلقة قصيرة. بل تمثل اللعبة على هيئة تراكيب متكررة لدوال على مجموعة البواقي \(R_n=\{0,1,\dots,n\}\)، وتتوقف فور تحوّل الصف القطري إلى دالة ثابتة. قيم التحقق المضمنة في جميع التطبيقات الثلاثة هي \(m(2)=2\)، و\(m(7)=1\)، و\(m(20)=4\)، وكذلك \(\sum_{n=1}^{20} m(n)^3=8150\).
ثبّت \(n\) ولتكن \(M=n+1\). كل خانة في الجدول هي قيمة دالة على مجموعة البواقي \(R_n=\{0,1,\dots,n\}\). الشيفرة لا تستعمل الجمع العادي بترديد \(M\)، بل تستعمل الإزاحة المبتورة الآتية:
$$\sigma_k(x)=\begin{cases} x+k, & x+k \lt M,\\ 0, & x+k \ge M, \end{cases}\qquad 1 \le k \le M.$$
وهذا الفرق جوهري: فالجمع المعياري المعتاد كان سيرسل \(M-1+k\) إلى \(k-1\)، أما البرنامج فيرسل كل حالة تجاوز مباشرة إلى \(0\). وهذا هو بالضبط معنى السطر if (value >= step) value = 0; في C++ وPython وJava.
لتكن \(F_s^{(m)}:R_n \to R_n\) هي الدالة المخزنة في الصف \(m\) بعد اكتمال المرحلة \(s\). أما الصف \(0\) فهو دائمًا دالة الهوية:
$$F_s^{(0)}(v)=v.$$
تبدأ الشيفرة من المرحلة \(0\) مع \(F_0^{(0)}=\mathrm{id}\). وبعد ذلك، في كل مرحلة جديدة، يُبنى الصف \(m\) اعتمادًا على الصف السابق من المرحلة الحالية، وعلى الصف السابق من المرحلة السابقة. وبالترميز الرياضي نحصل على
$$F_s^{(m)} = F_{s-1}^{(m-1)} \circ \sigma_{s-m+1} \circ F_s^{(m-1)}, \qquad 1 \le m \le s.$$
وعند تقييم هذا على باقي محدد \(v\) يصبح
$$F_s^{(m)}(v)=F_{s-1}^{(m-1)}\!\left(\sigma_{s-m+1}\!\left(F_s^{(m-1)}(v)\right)\right).$$
وبصورة خاصة فإن \(F_s^{(1)}=\sigma_s\)، أي إن الصف الأول من كل مرحلة هو الإزاحة المبتورة الخام نفسها. وهذه العلاقة العودية هي الجوهر الرياضي الحقيقي للتنفيذ، ولا توجد في ملفات المصدر حيلة جبرية أقصر من ذلك.
بعد نهاية المرحلة \(s\) يفحص البرنامج الصف القطري \(F_s^{(s)}\). فإذا أعطت جميع البواقي الابتدائية القيمة نفسها، فهذا يعني أن الصف صار دالة ثابتة:
$$F_s^{(s)}(0)=F_s^{(s)}(1)=\cdots=F_s^{(s)}(n)=c.$$
عندها يعيد الحل هذه الثابتة \(c\)، وهي نفسها الكمية التي يسميها الكود \(m(n)\). لذلك فالمعنى الفعلي للخوارزمية هو البحث عن أول مرحلة تُفقد فيها تراكيب هذه الإزاحات المبتورة كل اعتماد على باقي البداية.
وهذا البحث مضمون النجاح في موعد أقصاه المرحلة \(M=n+1\). ذلك أن \(\sigma_M\) هي أصلًا الدالة الثابتة الصفرية، ومن ثم فإن \(F_M^{(1)}\) ثابتة. وإذا كانت \(F_M^{(m-1)}\) ثابتة، فإن \(\sigma_{M-m+1}\!\left(F_M^{(m-1)}(v)\right)\) تبقى ثابتة أيضًا، وبعد تطبيق \(F_{M-1}^{(m-1)}\) تبقى النتيجة ثابتة. وبالاستقراء تكون جميع صفوف المرحلة \(M\) ثابتة، وبخاصة الصف القطري \(F_M^{(M)}\).
عندما \(n=2\) نعمل على \(R_2=\{0,1,2\}\) ولدينا \(M=3\). الصف الوحيد في المرحلة الأولى هو \(F_1^{(1)}=\sigma_1\)، ولذلك
$$F_1^{(1)}=[1,2,0].$$
في المرحلة الثانية يكون الصف الأول \(F_2^{(1)}=\sigma_2=[2,0,0]\). أما الصف الثاني فيعطى بالعلاقة
$$F_2^{(2)}(v)=F_1^{(1)}\!\left(\sigma_1\!\left(F_2^{(1)}(v)\right)\right),$$
ومنها نحصل على
$$F_2^{(2)}=[1,2,2].$$
هذا الصف ليس ثابتًا بعد، ولذا تتابع الخوارزمية. في المرحلة الثالثة تصبح \(\sigma_3\) دالة صفرية ثابتة، ومن ثم
$$F_3^{(1)}=[0,0,0],\qquad F_3^{(2)}=[0,0,0],\qquad F_3^{(3)}=[2,2,2].$$
وهنا صار الصف القطري ثابتًا، وبالتالي \(m(2)=2\)، وهو تمامًا ما تتحقق منه جميع ملفات الحل.
تشغل الحلقة الخارجية هذا الإجراء لكل \(n\) من \(1\) إلى \(1000\)، ثم تجمع
$$\sum_{n=1}^{1000} m(n)^3.$$
وقبل الوثوق بالتشغيل الطويل، تتحقق التطبيقات من القيم الصغيرة \(m(2)=2\)، و\(m(7)=1\)، و\(m(20)=4\)، ومن أن مجموع المكعبات حتى \(n=20\) يساوي \(8150\). وهذه الاختبارات مهمة لأن العلاقة العودية دقيقة، ولأن مخازن الجداول المحجوزة مسبقًا يعاد استخدامها بين قيم \(n\) المتتالية من أجل الكفاءة.
نسخة C++ تخزن الجدولين في مصفوفتين خطيتين، وتصل إلى الصف \(m\) والعمود \(v\) بواسطة index(m, v) = (m << SHIFT) + v حيث SHIFT = 10. وبما أن \(2^{10}=1024 > 1000\)، فإن كل صف منطقي يدخل ضمن قفزة ثابتة مقدارها 1024 خانة. وتستعمل Python الفهرسة المسطحة نفسها، بينما تعيد Java البنية نفسها بمخزنين من النوع int[].
داخل compute_m أو computeM يكون الصف 0 هو دالة الهوية. وفي كل مرحلة s يملأ الكود الصفوف من 1 حتى s وفق العلاقة السابقة، ثم يفحص هل أصبح الصف s ثابتًا، وإذا احتاج إلى مرحلة جديدة بدّل بين مخزني العمل. لذلك فاللغات الثلاث تنفذ الرياضيات نفسها تمامًا، والاختلاف بينها نحوي فقط: تبديل المؤشرات في C++، وإعادة الإسناد المتعدد في Python، وتبديل المراجع في Java.
من أجل \(n\) ثابت، ينفذ التحديث الداخلي انتقالًا بزمن ثابت لكل ثلاثي \((s,m,v)\) يحقق \(1 \le s \le n+1\)، و\(1 \le m \le s\)، و\(0 \le v \le n\). ولذلك
$$T(n)=\sum_{s=1}^{n+1}\sum_{m=1}^{s}\sum_{v=0}^{n}1=(n+1)\sum_{s=1}^{n+1}s=\frac{(n+1)^2(n+2)}{2}=O(n^3).$$
أما فحص ثبات الصف القطري فيضيف فقط \(O(n)\) لكل مرحلة، فلا يغير الرتبة الكلية. وحجم الجداول المنطقي يعادل مصفوفتين فيهما تقريبًا \((n+1)^2\) عنصرًا، لذا فذاكرة العمل هي \(O(n^2)\). وفي تنفيذ المستودع يتحقق ذلك فعليًا عبر مخزنين ثابتين بحجم \(1024 \times 1024\)، لأن أكبر قيمة مطلوبة هي \(n=1000\).