The task is to find the last ten decimal digits of
$$1^1+2^2+3^3+\cdots+1000^{1000}.$$
If we write
$$S_n=\sum_{k=1}^{n} k^k,$$
then the required quantity is simply \(S_{1000}\bmod 10^{10}\). The important point is that the problem is about the final ten-digit suffix, not about the full decimal expansion of the self powers themselves.
Set \(M=10^{10}\). The entire computation can be organized around the modular prefix sum
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M,$$
which satisfies the simple recurrence
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
So the real work is evaluating each self-power \(n^n\) modulo \(M\) quickly and safely.
Modular arithmetic respects both addition and multiplication:
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
Because of these identities, every term can be reduced as soon as it is formed, and the running sum can also be reduced after every addition. There is never any need to materialize the full number \(1000^{1000}\), whose decimal expansion is far larger than ten digits.
A direct computation of \(k^k\) would use \(k-1\) multiplications. The implementations instead use repeated squaring, which processes the binary expansion of the exponent \(k\). Starting from an accumulator equal to 1, they repeatedly square the current base, and whenever the current bit of the exponent is 1 they multiply that base into the accumulator.
The loop invariant is
$$\text{accumulator}\cdot \text{base}^{e}\equiv k^k \pmod M,$$
where \(e\) denotes the still-unprocessed part of the exponent. Each iteration preserves the invariant while cutting \(e\) roughly in half. When \(e=0\), the accumulator is exactly \(k^k\bmod M\).
This changes the cost of one term from \(O(k)\) multiplications to \(O(\log k)\) modular multiplications.
The implementations verify themselves on the smaller sum
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$$
Therefore
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$$
As a ten-digit suffix this is \(0405071317\). This example is useful because the unreduced sum already has more than ten digits, yet the modular method keeps only the information the problem actually asks for.
Even after reduction, each stored residue is below \(10^{10}\), so a product of two residues can be almost \(10^{20}\). That exceeds ordinary 64-bit multiplication. The mathematics is unchanged, but the implementations need different arithmetic strategies: the C++ version widens the intermediate product to 128 bits, the Java version performs the modular products with arbitrary-precision integers, and the Python version relies on built-in big integers.
The C++, Python, and Java implementations iterate through \(k=1,2,\dots,n\). For each \(k\), they compute \(k^k\bmod 10^{10}\) with binary exponentiation: initialize the residue as 1, reduce the base modulo \(10^{10}\), square the base every round, multiply it into the residue when the current exponent bit is odd, and then shift the exponent to the right.
After one modular self-power is obtained, it is added to the running total and the sum is reduced modulo \(10^{10}\) immediately. This implements the recurrence \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\) directly. The programs also include the checkpoint \(T_{10}=405071317\), which confirms that both the exponentiation routine and the summation logic behave correctly before the full case \(n=1000\) is evaluated.
Computing \(k^k\bmod M\) costs \(O(\log k)\) modular multiplications, so the whole algorithm for \(n\) terms runs in
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$$
For \(n=1000\), this is very small. The memory usage is \(O(1)\), because only a handful of integers are stored: the current base, the current exponent, one accumulator, and the running total.
Gesucht sind die letzten zehn Dezimalstellen von
$$1^1+2^2+3^3+\cdots+1000^{1000}.$$
Schreibt man
$$S_n=\sum_{k=1}^{n} k^k,$$
dann ist die gesuchte Größe einfach \(S_{1000}\bmod 10^{10}\). Entscheidend ist also nicht die vollständige Dezimaldarstellung der einzelnen Self Powers, sondern nur ihr gemeinsamer Zehnstellen-Suffix.
Setze \(M=10^{10}\). Dann kann man die gesamte Rechnung über die modulare Partialsumme
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M$$
organisieren. Sie erfüllt die Rekursion
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
Damit reduziert sich das Problem darauf, jede Potenz \(n^n\) modulo \(M\) schnell und ohne Überlauf zu berechnen.
Modulare Arithmetik verträgt sich mit Addition und Multiplikation:
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
Deshalb darf jeder Summand sofort nach seiner Entstehung reduziert werden, und auch die laufende Summe wird nach jedem Schritt wieder modulo \(M\) genommen. Man muss also nie die volle Zahl \(1000^{1000}\) konstruieren.
Eine naive Berechnung von \(k^k\) wuerde \(k-1\) Multiplikationen brauchen. Die Implementierungen benutzen stattdessen Exponentiation durch wiederholtes Quadrieren. Dazu liest man die Binardarstellung des Exponenten \(k\), quadriert in jeder Runde die aktuelle Basis und multipliziert sie genau dann in den Akkumulator, wenn das aktuelle Bit gleich 1 ist.
Die Schleifeninvariante lautet
$$\text{Akkumulator}\cdot \text{Basis}^{e}\equiv k^k \pmod M,$$
wobei \(e\) den noch nicht verarbeiteten Teil des Exponenten bezeichnet. Jede Iteration erhaelt diese Invariante und halbiert \(e\) im Wesentlichen. Wenn \(e=0\) ist, steht im Akkumulator genau \(k^k\bmod M\).
So sinkt der Aufwand fuer einen Summanden von \(O(k)\) auf \(O(\log k)\) modulare Multiplikationen.
Die Implementierungen pruefen sich selbst zuerst an der kleineren Summe
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$$
Daraus folgt
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$$
Als Zehnstellen-Suffix geschrieben ist das \(0405071317\). Das Beispiel zeigt gut, warum die Modulo-Rechnung ausreicht: Die unreduzierte Summe ist bereits laenger als zehn Stellen, aber die Aufgabe fragt nur nach dem Rest modulo \(10^{10}\).
Nach jeder Reduktion liegt jeder gespeicherte Rest zwar unter \(10^{10}\), aber das Produkt zweier solcher Reste kann fast \(10^{20}\) erreichen. Das ist fuer gewoehnliche 64-Bit-Multiplikation zu gross. Die Mathematik bleibt identisch, doch die Implementierungen sichern sich unterschiedlich ab: C++ verwendet 128-Bit-Zwischenprodukte, Java benutzt fuer die modularen Produkte Ganzzahlen mit beliebiger Praezision, und Python stuetzt sich auf eingebaute grosse Integer.
Die Implementierungen in C++, Python und Java durchlaufen \(k=1,2,\dots,n\). Fuer jedes \(k\) berechnen sie \(k^k\bmod 10^{10}\) mit binaerer Exponentiation: Der Rest startet bei 1, die Basis wird sofort modulo \(10^{10}\) reduziert, in jeder Runde quadriert man die Basis, multipliziert sie bei ungeradem Exponenten in den Rest und verschiebt anschliessend den Exponenten um ein Bit nach rechts.
Nach jeder berechneten Selbstpotenz wird der Wert direkt zur laufenden Summe addiert und wieder modulo \(10^{10}\) reduziert. Genau so wird die Rekursion \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\) umgesetzt. Ausserdem pruefen die Programme den bekannten Testfall \(T_{10}=405071317\), bevor sie den vollen Fall \(n=1000\) auswerten.
Die Berechnung von \(k^k\bmod M\) kostet \(O(\log k)\) modulare Multiplikationen. Fuer \(n\) Summanden ergibt das insgesamt
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$$
Bei \(n=1000\) ist das sehr klein. Der Speicherbedarf ist \(O(1)\), denn gespeichert werden nur wenige Ganzzahlen: aktuelle Basis, aktueller Exponent, ein Akkumulator und die laufende Summe.
Aranan sey,
$$1^1+2^2+3^3+\cdots+1000^{1000}$$
toplaminin son on basamagidir. Eger
$$S_n=\sum_{k=1}^{n} k^k$$
diye yazarsak, istenen deger \(S_{1000}\bmod 10^{10}\) olur. Yani problem, devasa sayilarin tam degerlerinden cok ortak on basamakli son kismina odaklanir.
\(M=10^{10}\) tanimini yapalim. Tum hesap,
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M$$
moduler kisim toplami uzerinden ilerler ve su bagintiyi saglar:
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
Dolayisiyla asil gorev, her \(n^n\) terimini \(M\) modunda hizli ve tasma guvenli bicimde bulmaktir.
Moduler aritmetik toplama ve carpma ile uyumludur:
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
Bu nedenle her terim uretilir uretilmez mod alinabilir, ara toplam da her eklemeden sonra tekrar mod \(M\) altina indirilebilir. Boylece \(1000^{1000}\) gibi sayilarin tam ondalik acilimini hicbir zaman olusturmaya gerek kalmaz.
\(k^k\) ifadesini dogrudan hesaplamak \(k-1\) carpma gerektirir. Bunun yerine uygulamalar, ussu ikilik yaziminda okuyup kare alma yontemini kullanir. Baslangicta akumulator 1'dir. Her turda mevcut taban karesi alinerek guncellenir; ussun o andaki biti 1 ise bu taban akumulatora da carpilir.
Korunan dongu degismezi sudur:
$$\text{akumulator}\cdot \text{taban}^{e}\equiv k^k \pmod M,$$
burada \(e\), ussun henuz islenmemis kismini gosterir. Her adim bu degismezi korurken \(e\)'yi yaklasik yariya indirir. \(e=0\) oldugunda akumulatorde tam olarak \(k^k\bmod M\) kalir.
Boylece bir terimin maliyeti \(O(k)\) yerine \(O(\log k)\) moduler carpma olur.
Uygulamalar once daha kucuk olan
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317$$
toplamini denetler. Buradan
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}$$
elde edilir. On basamakli sonek olarak bu deger \(0405071317\) seklindedir. Ornek, indirgenmemis toplam on basamagi assa bile sorunun yalnizca moduler kalani istedigini netlestirir.
Her kalanin \(10^{10}\)'dan kucuk olmasi yeterli degildir; iki boyle kalanin carpimi neredeyse \(10^{20}\) olabilir. Bu, siradan 64 bit carpma icin buyuktur. Matematik ayni kalir, fakat uygulamalar farkli aritmetik secimleri yapar: C++ ara carpimi 128 bite genisletir, Java moduler carpimlari keyfi buyuklukte tamsayilarla yapar, Python ise yerlesik buyuk tamsayilara guvenir.
C++, Python ve Java uygulamalari \(k=1,2,\dots,n\) uzerinden ilerler. Her \(k\) icin \(k^k\bmod 10^{10}\) degeri ikili us alma ile bulunur: sonuc 1'den baslar, taban hemen modulo \(10^{10}\) indirgenir, her turda tabanin karesi alinir, ussun en dusuk biti 1 ise bu taban sonuca carpilir ve sonra us bir bit saga kaydirilir.
Bulunan her self power, yurutulen toplama eklenir ve toplam tekrar modulo \(10^{10}\) alinır. Bu, \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\) bagintisinin dogrudan uygulanmis halidir. Programlar ayrica \(T_{10}=405071317\) kontrolunu yaparak hem us alma hem de toplama mantiginin dogru oldugunu test eder.
\(k^k\bmod M\) hesabinin maliyeti \(O(\log k)\) moduler carpimdir. Bu nedenle \(n\) terim icin toplam maliyet
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n)$$
olur. \(n=1000\) icin bu maliyet cok kucuktur. Bellek kullanimi \(O(1)\)'dir; cunku yalnizca mevcut taban, mevcut us, bir akumulator ve kosan toplam tutulur.
Hay que encontrar los ultimos diez digitos decimales de
$$1^1+2^2+3^3+\cdots+1000^{1000}.$$
Si definimos
$$S_n=\sum_{k=1}^{n} k^k,$$
entonces la cantidad pedida es \(S_{1000}\bmod 10^{10}\). El problema no exige expandir por completo esos numeros enormes, sino conservar solo el sufijo decimal de longitud diez.
Tomemos \(M=10^{10}\). Toda la solucion se organiza alrededor de la suma parcial modular
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M,$$
que satisface
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
Por tanto, el problema consiste en calcular cada termino \(n^n\) modulo \(M\) de forma rapida y con una multiplicacion segura.
La aritmetica modular es compatible con la suma y el producto:
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
Eso permite reducir cada termino apenas se obtiene y volver a reducir la suma acumulada en cada paso. Nunca hace falta construir el valor completo de \(1000^{1000}\); basta con su clase de congruencia modulo \(10^{10}\).
Calcular \(k^k\) mediante multiplicaciones sucesivas costaria \(k-1\) productos. Las implementaciones usan exponenciacion por cuadrados sucesivos. Se lee el exponente \(k\) en binario, se mantiene un acumulador que empieza en 1, se eleva al cuadrado la base en cada iteracion y, si el bit actual del exponente vale 1, se multiplica esa base en el acumulador.
La invariante del bucle es
$$\text{acumulador}\cdot \text{base}^{e}\equiv k^k \pmod M,$$
donde \(e\) representa la parte del exponente que aun no se ha procesado. Cada vuelta conserva esa invariante y reduce \(e\) aproximadamente a la mitad. Cuando \(e=0\), el acumulador ya es \(k^k\bmod M\).
Asi, el costo de un termino pasa de \(O(k)\) a \(O(\log k)\) multiplicaciones modulares.
Las implementaciones se verifican primero con la suma pequena
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$$
En consecuencia,
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$$
Escrito como sufijo de diez digitos, el resultado es \(0405071317\). Este ejemplo muestra por que la reduccion modular resuelve el problema correcto incluso cuando la suma real ya supera las diez cifras.
Aunque cada residuo almacenado sea menor que \(10^{10}\), el producto de dos residuos puede acercarse a \(10^{20}\). Eso es demasiado para una multiplicacion ordinaria de 64 bits. La matematica no cambia, pero cada lenguaje protege esa multiplicacion de un modo distinto: C++ usa productos intermedios de 128 bits, Java usa enteros de precision arbitraria para el producto modular y Python aprovecha sus enteros grandes incorporados.
Las implementaciones en C++, Python y Java recorren \(k=1,2,\dots,n\). Para cada \(k\), calculan \(k^k\bmod 10^{10}\) con exponenciacion binaria: comienzan con residuo 1, reducen la base modulo \(10^{10}\), la elevan al cuadrado en cada ronda, la multiplican en el residuo cuando el exponente actual es impar y luego desplazan el exponente un bit a la derecha.
Una vez obtenido un self power modular, se suma al total parcial y se vuelve a tomar modulo \(10^{10}\). Eso implementa directamente la recurrencia \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\). Ademas, los programas comprueban el caso \(T_{10}=405071317\), lo que valida tanto la rutina de exponenciacion como la suma antes de resolver el caso completo \(n=1000\).
Calcular \(k^k\bmod M\) cuesta \(O(\log k)\) multiplicaciones modulares. Sumando sobre \(k=1,\dots,n\), el tiempo total es
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$$
Para \(n=1000\) se trata de un trabajo muy pequeno. El uso de memoria es \(O(1)\), porque solo se guardan unos pocos enteros: la base actual, el exponente actual, un acumulador y el total parcial.
题目要求的是下面这个和的最后十位十进制数字：
$$1^1+2^2+3^3+\cdots+1000^{1000}.$$
如果记
$$S_n=\sum_{k=1}^{n} k^k,$$
那么真正要输出的量就是 \(S_{1000}\bmod 10^{10}\)。因此核心并不是把每个 \(k^k\) 的完整十进制展开都算出来，而是只保留与最后十位有关的模 \(10^{10}\) 信息。
设 \(M=10^{10}\)。整个问题可以写成一个模意义下的前缀和：
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M,$$
它满足非常直接的递推关系
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
所以真正需要解决的只有两件事：第一，怎样高效地求出每个 \(n^n\bmod M\)；第二，怎样在实现中避免中间乘法溢出。
模运算与加法、乘法兼容：
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
这意味着每一项 \(k^k\) 一旦求出模 \(M\) 的剩余，就可以立刻加入总和；而总和在每一步之后也都可以继续取模。于是整个算法始终只需要维护最后十位对应的剩余类，而不需要显式构造 \(1000^{1000}\) 这种极其巨大的整数。
如果直接做 \(k^k\)，那就需要连续乘 \(k-1\) 次。实现中采用的是二进制快速幂。把指数 \(k\) 写成二进制以后，维护一个初值为 1 的累积量；每轮把当前底数平方，如果当前指数的最低位是 1，就把这个底数乘进累积量里，然后把指数右移一位。
这个过程背后的不变量是
$$\text{accumulator}\cdot \text{base}^{e}\equiv k^k \pmod M,$$
其中 \(e\) 表示还没有处理完的那部分指数。每一次循环都保持这个关系不变，同时把 \(e\) 大约减半。等到 \(e=0\) 时，累积量里剩下的正是 \(k^k\bmod M\)。
因此，单项计算的代价从 \(O(k)\) 次乘法下降为 \(O(\log k)\) 次模乘。
三个实现都会先验证较小的前缀和
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$$
于是
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$$
如果把它写成完整的十位后缀，就是 \(0405071317\)。这个例子很有代表性，因为未取模的总和已经超过十位，但题目真正需要的只是它对 \(10^{10}\) 的余数，而这一点恰好与程序里的检查值完全一致。
虽然每个保存下来的剩余都小于 \(10^{10}\)，但两个这样的剩余相乘时仍然可能接近 \(10^{20}\)。这已经超出了普通 64 位乘法的安全范围。数学公式本身并没有变化，但不同语言需要不同的实现保护：C++ 用 128 位中间乘积，Java 用任意精度整数完成模乘，Python 则直接依赖内建大整数。三者算的都是同一个模 \(10^{10}\) 的结果。
C++、Python 和 Java 实现都会遍历 \(k=1,2,\dots,n\)。对于每个 \(k\)，它们都用快速幂求出 \(k^k\bmod 10^{10}\)：先把结果设为 1，把底数先对 \(10^{10}\) 取模；然后每一轮平方底数，若当前指数为奇数就把底数乘入结果，最后把指数右移一位。
每个 self power 的模值求出来之后，程序会立刻把它加到运行中的总和上，并再次对 \(10^{10}\) 取模。这正是递推式 \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\) 的直接实现。除此之外，程序还会先检查 \(T_{10}=405071317\) 这个已知值，用来确认快速幂和累加逻辑在进入 \(n=1000\) 之前都是正确的。
求 \(k^k\bmod M\) 需要 \(O(\log k)\) 次模乘，因此总时间复杂度为
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$$
对 \(n=1000\) 来说，这个规模非常小。空间复杂度为 \(O(1)\)，因为算法只保存当前底数、当前指数、一个累积量以及一个运行中的总和。
Нужно найти последние десять десятичных цифр суммы
$$1^1+2^2+3^3+\cdots+1000^{1000}.$$
Если обозначить
$$S_n=\sum_{k=1}^{n} k^k,$$
то искомая величина равна \(S_{1000}\bmod 10^{10}\). Значит, нас интересует не полная запись чудовищно больших степеней, а только их общий суффикс длины десять цифр.
Положим \(M=10^{10}\). Тогда всю задачу удобно описать через модульную частичную сумму
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M,$$
которая удовлетворяет рекуррентному соотношению
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
Следовательно, остается быстро вычислять каждый член \(n^n\bmod M\) и аккуратно складывать эти остатки.
Модульная арифметика совместима и со сложением, и с умножением:
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
Поэтому каждый член ряда можно сократить по модулю сразу после вычисления, а бегущую сумму тоже можно каждый раз приводить по модулю \(M\). Полное значение \(1000^{1000}\) при этом никогда не нужно строить явно.
Наивное вычисление \(k^k\) потребовало бы \(k-1\) умножений. Реализации используют двоичное возведение в степень. Экспонента \(k\) читается по битам, поддерживается аккумулятор, начинающийся с 1, текущая база в каждом шаге возводится в квадрат, а если текущий бит экспоненты равен 1, база дополнительно домножается в аккумулятор.
Инвариант цикла имеет вид
$$\text{accumulator}\cdot \text{base}^{e}\equiv k^k \pmod M,$$
где \(e\) обозначает еще не обработанную часть экспоненты. Каждая итерация сохраняет этот инвариант и примерно вдвое уменьшает \(e\). Когда \(e=0\), в аккумуляторе остается точное значение \(k^k\bmod M\).
Тем самым стоимость одного члена уменьшается с \(O(k)\) до \(O(\log k)\) модульных умножений.
Все реализации сначала проверяют более маленькую сумму
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$$
Отсюда получается
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$$
Если записать это как десятизначный суффикс, получится \(0405071317\). Пример полезен тем, что сама сумма уже длиннее десяти цифр, но модульная схема сохраняет именно ту информацию, которая требуется по условию.
Даже если каждый сохраненный остаток меньше \(10^{10}\), произведение двух таких остатков может быть почти \(10^{20}\). Обычное 64-битное умножение этого уже не выдерживает. Математика одна и та же, но способы защиты различаются: версия на C++ расширяет промежуточный продукт до 128 бит, версия на Java выполняет модульные произведения с помощью целых произвольной длины, а Python полагается на встроенные большие целые числа.
Реализации на C++, Python и Java проходят по \(k=1,2,\dots,n\). Для каждого \(k\) они вычисляют \(k^k\bmod 10^{10}\) бинарным возведением в степень: начинают с остатка 1, сразу уменьшают базу по модулю \(10^{10}\), затем в каждом раунде возводят базу в квадрат, при нечетном текущем значении экспоненты умножают ее в остаток и после этого сдвигают экспоненту вправо.
После вычисления очередной self power ее остаток немедленно прибавляется к бегущей сумме, которая снова сокращается по модулю \(10^{10}\). Это прямая реализация рекурсии \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\). Кроме того, программы проверяют известное значение \(T_{10}=405071317\), чтобы убедиться в корректности как процедуры возведения в степень, так и накопления суммы.
Вычисление \(k^k\bmod M\) требует \(O(\log k)\) модульных умножений, поэтому общее время работы равно
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$$
При \(n=1000\) это очень небольшой объем работы. Память равна \(O(1)\), потому что хранятся лишь несколько целых чисел: текущая база, текущая экспонента, один аккумулятор и бегущая сумма.
المطلوب هو إيجاد آخر عشرة أرقام عشرية للمجموع
$$1^1+2^2+3^3+\cdots+1000^{1000}.$$
إذا كتبنا
$$S_n=\sum_{k=1}^{n} k^k,$$
فإن الكمية المطلوبة هي \(S_{1000}\bmod 10^{10}\). لذلك لا نحتاج إلى التمثيل العشري الكامل لكل قيمة \(k^k\)، بل نحتاج فقط إلى الباقي الذي يحدد آخر عشرة أرقام.
لنضع \(M=10^{10}\). عندئذ يمكن تنظيم الحل كله حول المجموع الجزئي المعياري
$$T_n\equiv \sum_{k=1}^{n} k^k \pmod M,$$
والذي يحقق العلاقة
$$T_n\equiv T_{n-1}+n^n \pmod M,\qquad T_0=0.$$
إذن جوهر المسألة هو حساب كل حد من نوع \(n^n\bmod M\) بسرعة، ثم جمع هذه البواقي مع المحافظة على سلامة الضربات الوسيطة.
الحساب المعياري يحافظ على عمليتي الجمع والضرب:
$$ (a+b)\bmod M = \bigl((a\bmod M)+(b\bmod M)\bigr)\bmod M,$$
$$ (ab)\bmod M = \bigl((a\bmod M)(b\bmod M)\bigr)\bmod M.$$
ولهذا يمكن اختزال كل حد مباشرة بعد حسابه، ويمكن أيضا اختزال المجموع الجاري بعد كل إضافة. لا حاجة أبدا إلى تكوين العدد الكامل \(1000^{1000}\)، لأن المطلوب في النهاية هو فقط الباقي modulo \(10^{10}\).
الحساب المباشر لـ \(k^k\) يحتاج إلى \(k-1\) عملية ضرب. أما التطبيقات فتستخدم الرفع الثنائي للاس. نكتب الاس \(k\) بالثنائي، ونحافظ على مُجمِّع يبدأ من 1. في كل دورة نربّع القاعدة الحالية، وإذا كان البت الحالي في الاس يساوي 1 نضرب هذه القاعدة في المُجمِّع.
ثابت الحلقة هو
$$\text{accumulator}\cdot \text{base}^{e}\equiv k^k \pmod M,$$
حيث تمثل \(e\) الجزء الذي لم يُعالج بعد من الاس. كل تكرار يحافظ على هذا الثابت ويقلص \(e\) تقريبا إلى النصف. وعندما يصبح \(e=0\)، تكون قيمة المُجمِّع هي بالضبط \(k^k\bmod M\).
وبذلك تنخفض كلفة الحد الواحد من \(O(k)\) ضربات إلى \(O(\log k)\) ضربات معيارية.
التطبيقات تتحقق أولا من المجموع الأصغر
$$S_{10}=1^1+2^2+\cdots+10^{10}=10405071317.$$
ومن ثم
$$T_{10}\equiv 10405071317 \equiv 405071317 \pmod{10^{10}}.$$
وإذا كتبنا الناتج على صورة لاحقة من عشرة أرقام فسنحصل على \(0405071317\). هذا المثال يوضح الفكرة جيدا: المجموع الحقيقي تجاوز بالفعل عشر خانات، لكن الباقي modulo \(10^{10}\) ما زال يحمل بالضبط المعلومة التي يطلبها السؤال.
صحيح أن كل باق محفوظ أصغر من \(10^{10}\)، لكن حاصل ضرب باقيين من هذا النوع قد يقترب من \(10^{20}\). وهذا أكبر من المجال الآمن للضرب العادي ذي 64 بت. الصيغة الرياضية نفسها لا تتغير، لكن اساليب التنفيذ تختلف: نسخة C++ توسع حاصل الضرب الوسيط إلى 128 بت، ونسخة Java تستخدم أعدادا صحيحة ذات دقة غير محدودة في الضرب المعياري، ونسخة Python تعتمد على الأعداد الصحيحة الكبيرة المدمجة.
تسير تطبيقات C++ وPython وJava على القيم \(k=1,2,\dots,n\). ولكل \(k\) تحسب \(k^k\bmod 10^{10}\) باستعمال الرفع الثنائي للاس: تبدأ النتيجة من 1، وتخفض القاعدة مباشرة modulo \(10^{10}\)، ثم تربع القاعدة في كل دورة، وتضربها في النتيجة إذا كان الاس الحالي فرديا، وبعد ذلك تزاح قيمة الاس بمقدار بت واحد إلى اليمين.
بعد الحصول على قيمة self power المعيارية، تُضاف مباشرة إلى المجموع الجاري ثم يؤخذ هذا المجموع modulo \(10^{10}\) مرة أخرى. هذا تنفيذ مباشر للعلاقة \(T_n\equiv T_{n-1}+n^n\pmod{10^{10}}\). كما تتضمن البرامج نقطة فحص معروفة هي \(T_{10}=405071317\)، وذلك للتأكد من أن آلية الرفع السريع وآلية التجميع كلتيهما تعملان كما ينبغي قبل الانتقال إلى الحالة الكاملة \(n=1000\).
حساب \(k^k\bmod M\) يحتاج إلى \(O(\log k)\) ضربات معيارية، ولذلك يكون الزمن الكلي
$$O\!\left(\sum_{k=1}^{n}\log k\right)=O(n\log n).$$
وعندما يكون \(n=1000\) فهذه كلفة صغيرة جدا. أما الذاكرة فهي \(O(1)\)، لأن الخوارزمية تحتفظ فقط بالقاعدة الحالية، والاس الحالي، ومُجمِّع واحد، والمجموع الجاري.