The quantity of interest is
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$
For this problem, the target input is \(n=10^{18}\), and the required output is the residue of \(S(10^{18})\) modulo
$$M=83^3\cdot 89^3\cdot 97^3.$$
A direct summation is hopeless, so the solution rewrites the sum into a form where only a short range of indices matters modulo each prime cube.
The key idea is to replace the ordinary power \(k^n\) by a falling-factorial expansion, evaluate the resulting binomial convolution exactly, and then solve the problem separately modulo \(83^3\), \(89^3\), and \(97^3\).
Let
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
denote the falling factorial. The standard Stirling expansion is
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$
where \(\left\{{n \atop j}\right\}\) is a Stirling number of the second kind. Substituting into the original sum gives
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$
For \(n>0\), the \(j=0\) term vanishes, so the effective sum starts at \(j=1\).
Since \((k)_j=j!\binom{k}{j}\), we obtain
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$
Use the identity
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$
to rewrite the sum as
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$
Because \(j!\binom{n}{j}=n^{\underline{j}}\), the whole problem becomes
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$
This is the central transformation used by the implementations.
Fix one of the primes \(p\in\{83,89,97\}\). We want the transformed sum modulo \(p^3\).
If \(j\ge 3p\), then the falling factorial
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
contains at least three multiples of \(p\), because any block of \(3p\) consecutive integers contains three such multiples. Therefore
$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$
so the entire \(j\)-th term is \(0\pmod{p^3}\). Hence
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
This short cutoff is what makes the computation feasible.
The finite-difference formula gives
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$
Call the right-hand side \(D_j\). Directly dividing by \(j!\) modulo \(p^3\) is dangerous when \(p\mid j!\). So write
$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$
Then \(q_j\) is invertible modulo \(p^3\), and
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$
To do this safely, we need \(D_j\) modulo \(p^{3+a_j}\). In the active range \(j<3p\), we have \(a_j\le 2\), so a uniform modulus \(p^5\) is enough for every \(j\). That is why the implementation builds the finite-difference numerator modulo \(p^5\), strips the exact power of \(p\), and only then multiplies by the inverse of the unit part \(q_j\) modulo \(p^3\).
For each \(p\in\{83,89,97\}\), compute
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
The three moduli \(83^3\), \(89^3\), and \(97^3\) are pairwise coprime, so the Chinese Remainder Theorem reconstructs the unique residue \(R\) modulo
$$M=83^3\cdot 89^3\cdot 97^3$$
such that
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$
That residue is the required answer.
Directly,
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
Now use the transformed formula. The relevant Stirling numbers are
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$$
Also,
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$
Therefore
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
This confirms the transformation on a small case before the modular machinery is applied to \(n=10^{18}\).
The implementation handles the three prime cubes \(83^3\), \(89^3\), and \(97^3\) separately. For one prime \(p\), it sets \(J=\min(n,3p-1)\), because terms beyond that point are already zero modulo \(p^3\).
Next it builds a Pascal-style table of \(\binom{j}{i}\) for \(0\le i\le j\le J\) modulo \(p^5\), and it precomputes \(i^n\bmod p^5\) for every \(0\le i\le J\). It also tabulates, for each \(j\), the \(p\)-adic valuation of \(j!\) and the remaining unit factor of \(j!\) modulo \(p^3\).
During the main loop, the implementation updates \(n^{\underline{j}}\) multiplicatively by appending the next factor \(n-j+1\), and it updates \(2^{n-j}\) by multiplying once per step by the inverse of \(2\) modulo \(p^3\). It then evaluates the finite-difference numerator \(D_j\), removes the exact power of \(p\) contributed by \(j!\), multiplies by the inverse of the unit part of \(j!\), and accumulates the resulting term modulo \(p^3\).
After obtaining the three residues, the implementation combines them with the Chinese Remainder Theorem. The C++ implementation evaluates the three prime channels in parallel, while the Python and Java implementations process them sequentially. The C++ implementation also performs a small validation at \(n=10\), where \(S(10)=142469423360\), and checks that the modular pipeline reproduces the same residue modulo \(M\).
For one prime \(p\), let \(J=\min(n,3p-1)\). Building the binomial table up to row \(J\) costs \(O(J^2)\) time and \(O(J^2)\) memory. Precomputing the powers \(i^n\bmod p^5\) for \(0\le i\le J\) costs \(O(J\log n)\) time.
The main summation also costs \(O(J^2)\) time, because the finite-difference formula for the \(j\)-th Stirling term sums over all \(i=0,\dots,j\). Thus one prime channel costs
$$O(J^2+J\log n)$$
time and \(O(J^2)\) memory. Since the actual primes are fixed and \(J<3p\), the total workload across \(83\), \(89\), and \(97\) is effectively constant for the target input \(n=10^{18}\).
Gesucht ist die Größe
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$
Im Problem ist \(n=10^{18}\), und ausgegeben werden soll der Rest von \(S(10^{18})\) modulo
$$M=83^3\cdot 89^3\cdot 97^3.$$
Direktes Aufsummieren ist völlig unrealistisch. Deshalb wird die Summe in eine Form umgeschrieben, in der modulo jeder Primzahlpotenz nur ein sehr kurzer Indexbereich relevant bleibt.
Die Grundidee ist, die gewöhnliche Potenz \(k^n\) in der Basis der fallenden Fakultäten zu entwickeln, die entstehende Binomialfaltung exakt auszuwerten und anschließend getrennt modulo \(83^3\), \(89^3\) und \(97^3\) zu rechnen.
Sei
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
die fallende Fakultät. Dann gilt die Stirling-Entwicklung
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$
wobei \(\left\{{n \atop j}\right\}\) eine Stirling-Zahl zweiter Art ist. Nach Einsetzen erhält man
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$
Für \(n>0\) verschwindet der Term \(j=0\), daher beginnt die effektive Summe bei \(j=1\).
Aus \((k)_j=j!\binom{k}{j}\) folgt
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$
Mit der Identität
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$
wird daraus
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$
Weil \(j!\binom{n}{j}=n^{\underline{j}}\) ist, erhalten wir die zentrale Formel
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$
Fixiere nun eines der Primzahlen \(p\in\{83,89,97\}\). Wir wollen die transformierte Summe modulo \(p^3\) berechnen.
Falls \(j\ge 3p\), enthält
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
mindestens drei Vielfache von \(p\), denn jeder Block von \(3p\) aufeinanderfolgenden ganzen Zahlen enthält drei solche Vielfache. Daher gilt
$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$
also ist der gesamte \(j\)-te Summand \(0\pmod{p^3}\). Somit
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Dieses kurze Abschneiden macht die Berechnung überhaupt erst praktikabel.
Die Formel der endlichen Differenzen lautet
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$
Bezeichne die rechte Seite mit \(D_j\). Eine direkte Division durch \(j!\) modulo \(p^3\) ist heikel, sobald \(p\mid j!\). Deshalb schreiben wir
$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$
Dann ist \(q_j\) modulo \(p^3\) invertierbar, und
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$
Dazu braucht man \(D_j\) modulo \(p^{3+a_j}\). Im aktiven Bereich \(j<3p\) gilt \(a_j\le 2\), also genügt ein einheitlicher Arbeitsmodul \(p^5\). Genau deshalb berechnet die Implementierung den Zähler der Differenzformel modulo \(p^5\), entfernt die exakte \(p\)-Potenz und invertiert erst danach den Einheitsteil \(q_j\) modulo \(p^3\).
Für jedes \(p\in\{83,89,97\}\) berechnet man
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Die Moduli \(83^3\), \(89^3\) und \(97^3\) sind paarweise teilerfremd. Der chinesische Restsatz liefert also genau eine Restklasse \(R\) modulo
$$M=83^3\cdot 89^3\cdot 97^3$$
mit
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$
Diese Restklasse ist die gesuchte Antwort.
Direkt erhält man
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
Nun mit der transformierten Formel. Die relevanten Stirling-Zahlen sind
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$$
Außerdem gilt
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$
Also
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
Das bestätigt die Umformung an einem kleinen Beispiel, bevor die modulare Rechnung auf \(n=10^{18}\) angewandt wird.
Die Implementierung behandelt die drei Primzahlwürfel \(83^3\), \(89^3\) und \(97^3\) getrennt. Für ein fixes \(p\) setzt sie \(J=\min(n,3p-1)\), weil alle Terme dahinter bereits \(0\pmod{p^3}\) sind.
Danach wird bis zur Zeile \(J\) eine Pascal-Tafel der Binomialkoeffizienten \(\binom{j}{i}\) modulo \(p^5\) aufgebaut. Zusätzlich werden alle Werte \(i^n\bmod p^5\) für \(0\le i\le J\) vorbereitet. Ebenso wird für jedes \(j\) sowohl die \(p\)-adische Bewertung von \(j!\) als auch der verbleibende Einheitsteil von \(j!\) modulo \(p^3\) tabelliert.
In der Hauptschleife aktualisiert die Implementierung \(n^{\underline{j}}\) multiplikativ durch den nächsten Faktor \(n-j+1\), und \(2^{n-j}\) wird schrittweise durch Multiplikation mit dem Inversen von \(2\) modulo \(p^3\) fortgeführt. Anschließend wird der endliche-Differenzen-Zähler \(D_j\) ausgewertet, die exakte \(p\)-Potenz aus \(j!\) entfernt, mit dem Inversen des Einheitsteils multipliziert und der Summand modulo \(p^3\) akkumuliert.
Nach den drei Einzelresten setzt die Implementierung diese per chinesischem Restsatz zusammen. Die C++-Implementierung bearbeitet die drei Primkanäle parallel, während die Python- und Java-Implementierungen sie nacheinander ausführen. Zusätzlich validiert die C++-Implementierung den kleinen Test \(S(10)=142469423360\) und prüft, dass die modulare Pipeline denselben Rest modulo \(M\) liefert.
Für eine Primzahl \(p\) sei \(J=\min(n,3p-1)\). Der Aufbau der Binomialtabelle bis Zeile \(J\) kostet \(O(J^2)\) Zeit und \(O(J^2)\) Speicher. Die Vorberechnung der Potenzen \(i^n\bmod p^5\) für \(0\le i\le J\) kostet \(O(J\log n)\) Zeit.
Die Hauptsumme kostet ebenfalls \(O(J^2)\) Zeit, denn in der Formel der endlichen Differenzen summiert der \(j\)-te Stirling-Term über alle \(i=0,\dots,j\). Damit benötigt ein Primkanal insgesamt
$$O(J^2+J\log n)$$
Zeit und \(O(J^2)\) Speicher. Da die tatsächlichen Primzahlen fest sind und \(J<3p\) gilt, ist der Gesamtaufwand über \(83\), \(89\) und \(97\) für das Ziel \(n=10^{18}\) praktisch konstant.
İncelenen büyüklük
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n$$
ifadesidir. Bu problemde hedef girdi \(n=10^{18}\) olup istenen çıktı, \(S(10^{18})\) değerinin
$$M=83^3\cdot 89^3\cdot 97^3$$
modundaki kalıntısıdır. Doğrudan toplama yapmak olanaksız olduğu için çözüm, toplamı her asal küp için yalnızca kısa bir indis aralığının önemli olduğu bir biçime dönüştürür.
Ana fikir, sıradan kuvvet \(k^n\) ifadesini düşen faktöriyel tabanında açmak, ortaya çıkan binom toplamını kapalı biçimde değerlendirmek ve ardından hesabı ayrı ayrı \(83^3\), \(89^3\) ve \(97^3\) modlarında yapmaktır.
Şunu tanımlayalım:
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
düşen faktöriyeli göstersin. Standart Stirling açılımı
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j$$
şeklindedir; burada \(\left\{{n \atop j}\right\}\) ikinci tür Stirling sayısıdır. Bunu asıl toplama koyarsak
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j$$
elde edilir. \(n>0\) için \(j=0\) terimi sıfır olduğundan etkin toplam \(j=1\)'den başlar.
\((k)_j=j!\binom{k}{j}\) olduğundan
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}$$
yazarız. Burada
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$
özdeşliğini kullanınca
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}$$
çıkar. Ayrıca \(j!\binom{n}{j}=n^{\underline{j}}\) olduğundan temel dönüşüm
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}$$
olur. Uygulamanın merkezindeki eşitlik budur.
Şimdi \(p\in\{83,89,97\}\) asallarından birini sabitleyelim. Dönüştürülmüş toplamı \(p^3\) modunda istiyoruz.
Eğer \(j\ge 3p\) ise
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
çarpımında en az üç tane \(p\)'nin katı bulunur; çünkü art arda gelen \(3p\) tam sayılık her blokta üç kat vardır. Bu yüzden
$$v_p\!\left(n^{\underline{j}}\right)\ge 3$$
ve dolayısıyla \(j\). terim \(p^3\) modunda sıfır olur. Sonuç olarak
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Hesabı yapılabilir kılan kısa kesim tam olarak budur.
Sonlu fark formülü
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n$$
eşitliğini verir. Sağ tarafa \(D_j\) diyelim. \(p\mid j!\) olduğunda \(j!\)'ye doğrudan bölmek \(p^3\) modunda güvenli değildir. Bunun için
$$j!=p^{a_j}q_j,\qquad p\nmid q_j$$
şeklinde ayırırız. Böylece \(q_j\), \(p^3\) modunda terslenebilir olur ve
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}$$
yazabiliriz. Bunu güvenli yapmak için \(D_j\)'yi \(p^{3+a_j}\) modunda bilmek gerekir. Etkin aralıkta \(j<3p\) olduğundan \(a_j\le 2\), dolayısıyla bütün \(j\) değerleri için tek bir çalışma modülü \(p^5\) yeterlidir. Uygulama bu yüzden sonlu fark payını \(p^5\) modunda hesaplar, tam \(p\)-üsünü ayırır ve ancak sonra birim kısım \(q_j\)'nin tersini \(p^3\) modunda kullanır.
Her \(p\in\{83,89,97\}\) için
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}$$
hesaplanır. \(83^3\), \(89^3\) ve \(97^3\) modülleri ikişerli aralarında asaldır. Bu yüzden Çin Kalan Teoremi,
$$M=83^3\cdot 89^3\cdot 97^3$$
modunda tek bir \(R\) kalıntısı verir ve
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}$$
koşullarını sağlar. Aranan cevap bu \(R\)'dir.
Doğrudan hesaplayalım:
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
Şimdi dönüştürülmüş formülü kullanalım. Gerekli Stirling sayıları
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1$$
olup
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6$$
değerlerine sahibiz. Dolayısıyla
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
Böylece büyük modüler mekanizmaya geçmeden önce dönüşümün küçük bir örnekte doğru çalıştığı görülür.
Uygulama üç asal küp olan \(83^3\), \(89^3\) ve \(97^3\) modüllerini ayrı ayrı işler. Sabit bir \(p\) için \(J=\min(n,3p-1)\) seçilir; çünkü bu noktanın ötesindeki terimler zaten \(p^3\) modunda sıfırdır.
Ardından \(0\le i\le j\le J\) için \(\binom{j}{i}\) katsayılarını \(p^5\) modunda veren Pascal benzeri bir tablo kurulur. Ayrıca her \(0\le i\le J\) için \(i^n\bmod p^5\) önceden hesaplanır. Bunun yanında her \(j\) için \(j!\)'nin \(p\)-adik değeri ve \(j!\)'nin \(p^3\) modundaki birim kısmı tablolara yazılır.
Ana döngü sırasında \(n^{\underline{j}}\), her adımda yeni \(n-j+1\) çarpanı eklenerek güncellenir; \(2^{n-j}\) ise \(2\)'nin \(p^3\) modundaki tersiyle çarpılarak bir adım ilerletilir. Sonra sonlu fark payı \(D_j\) hesaplanır, \(j!\)'den gelen tam \(p\)-kuvveti ayıklanır, birim kısmın tersiyle çarpılır ve terim \(p^3\) modunda toplama eklenir.
Üç kalıntı elde edilince uygulama bunları Çin Kalan Teoremi ile tek bir sonuca dönüştürür. C++ uygulaması üç asal kanalını paralel iş parçacıklarıyla yürütür; Python ve Java uygulamaları ise bunları sıralı işler. Ayrıca C++ uygulaması \(n=10\) için \(S(10)=142469423360\) eşitliğiyle küçük bir doğrulama yapar ve modüler hattın da aynı kalıntıyı ürettiğini kontrol eder.
Bir asal \(p\) için \(J=\min(n,3p-1)\) olsun. \(J\)'ye kadar binom tablosunu kurmak \(O(J^2)\) zaman ve \(O(J^2)\) bellek ister. \(0\le i\le J\) için \(i^n\bmod p^5\) önhesabı ise \(O(J\log n)\) zamana mal olur.
Ana toplam da \(O(J^2)\) zamanda tamamlanır; çünkü sonlu fark formülünde \(j\). Stirling terimi için \(i=0,\dots,j\) üzerinden toplanır. Dolayısıyla tek bir asal kanalı için toplam maliyet
$$O(J^2+J\log n)$$
zaman ve \(O(J^2)\) bellektir. Gerçek asallar sabit ve \(J<3p\) olduğundan, \(83\), \(89\) ve \(97\) üzerindeki toplam iş yükü hedef girdi \(n=10^{18}\) için pratikte sabittir.
La cantidad estudiada es
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$
En este problema se toma \(n=10^{18}\), y hay que obtener el residuo de \(S(10^{18})\) módulo
$$M=83^3\cdot 89^3\cdot 97^3.$$
La suma directa es imposible. Por eso la solución la transforma en una expresión donde, módulo cada cubo primo, solo importa un intervalo corto de índices.
La idea central es reescribir la potencia ordinaria \(k^n\) en la base de factoriales descendentes, evaluar exactamente la convolución binomial resultante y luego resolver el problema por separado módulo \(83^3\), \(89^3\) y \(97^3\).
Sea
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
el factorial descendente. La expansión estándar con números de Stirling es
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$
donde \(\left\{{n \atop j}\right\}\) es un número de Stirling de segunda especie. Al sustituirlo en la suma original se obtiene
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$
Para \(n>0\), el término con \(j=0\) desaparece, así que la suma efectiva empieza en \(j=1\).
Como \((k)_j=j!\binom{k}{j}\), tenemos
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$
Usando la identidad
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$
la suma pasa a ser
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$
Puesto que \(j!\binom{n}{j}=n^{\underline{j}}\), llegamos a la fórmula principal
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$
Fijemos ahora uno de los primos \(p\in\{83,89,97\}\). Queremos la suma transformada módulo \(p^3\).
Si \(j\ge 3p\), entonces
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
contiene al menos tres múltiplos de \(p\), porque cualquier bloque de \(3p\) enteros consecutivos contiene tres de ellos. Por tanto
$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$
y el término completo es \(0\pmod{p^3}\). En consecuencia,
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Ese recorte corto es lo que vuelve viable el cálculo.
La fórmula de diferencias finitas dice que
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$
Llamemos \(D_j\) al lado derecho. Dividir directamente por \(j!\) módulo \(p^3\) no es seguro cuando \(p\mid j!\). Por eso escribimos
$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$
Entonces \(q_j\) sí es invertible módulo \(p^3\), y
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$
Para hacerlo bien necesitamos conocer \(D_j\) módulo \(p^{3+a_j}\). En el rango activo \(j<3p\) se cumple \(a_j\le 2\), así que un módulo uniforme \(p^5\) basta para todos los \(j\). Por eso la implementación calcula el numerador de diferencias finitas módulo \(p^5\), elimina la potencia exacta de \(p\) y solo después multiplica por el inverso de la parte unitaria \(q_j\) módulo \(p^3\).
Para cada \(p\in\{83,89,97\}\), se calcula
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Los módulos \(83^3\), \(89^3\) y \(97^3\) son coprimos dos a dos, así que el Teorema Chino del Resto reconstruye el único residuo \(R\) módulo
$$M=83^3\cdot 89^3\cdot 97^3$$
que satisface
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$
Ese residuo es la respuesta final.
De forma directa,
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
Ahora usamos la fórmula transformada. Los números de Stirling relevantes son
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$$
Además,
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$
Entonces
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
Así se verifica la transformación en un caso pequeño antes de aplicar toda la maquinaria modular a \(n=10^{18}\).
La implementación trata por separado los tres cubos primos \(83^3\), \(89^3\) y \(97^3\). Para un primo fijo \(p\), define \(J=\min(n,3p-1)\), ya que a partir de ahí todos los términos son cero módulo \(p^3\).
Después construye una tabla tipo Pascal con los coeficientes \(\binom{j}{i}\) para \(0\le i\le j\le J\) módulo \(p^5\). También precomputa \(i^n\bmod p^5\) para todo \(0\le i\le J\). Además, guarda para cada \(j\) tanto la valoración \(p\)-ádica de \(j!\) como la parte unitaria restante de \(j!\) módulo \(p^3\).
Durante el bucle principal, la implementación actualiza \(n^{\underline{j}}\) multiplicando por el siguiente factor \(n-j+1\), y actualiza \(2^{n-j}\) multiplicando en cada paso por el inverso de \(2\) módulo \(p^3\). Luego evalúa el numerador de diferencias finitas \(D_j\), elimina la potencia exacta de \(p\) procedente de \(j!\), multiplica por el inverso de la parte unitaria y acumula el término módulo \(p^3\).
Una vez obtenidos los tres residuos, la implementación los combina con el Teorema Chino del Resto. La implementación en C++ procesa los tres canales primos en paralelo, mientras que las implementaciones en Python y Java los recorren de forma secuencial. La versión en C++ también valida el caso pequeño \(S(10)=142469423360\) y comprueba que la tubería modular produce el mismo residuo módulo \(M\).
Para un primo \(p\), sea \(J=\min(n,3p-1)\). Construir la tabla binomial hasta la fila \(J\) cuesta \(O(J^2)\) tiempo y \(O(J^2)\) memoria. Precomputar las potencias \(i^n\bmod p^5\) para \(0\le i\le J\) cuesta \(O(J\log n)\) tiempo.
La suma principal también cuesta \(O(J^2)\), porque la fórmula de diferencias finitas del término de Stirling con índice \(j\) suma sobre todos los \(i=0,\dots,j\). Por tanto, un canal primo requiere
$$O(J^2+J\log n)$$
tiempo y \(O(J^2)\) memoria. Como los primos reales son fijos y \(J<3p\), el coste total sobre \(83\), \(89\) y \(97\) es en la práctica constante para la entrada objetivo \(n=10^{18}\).
我们要研究的量是
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$
本题的目标输入是 \(n=10^{18}\)，要求输出 \(S(10^{18})\) 对
$$M=83^3\cdot 89^3\cdot 97^3$$
取模后的结果。直接按定义求和完全不可行，因此必须把原式改写成一种在每个素数立方模数下都只需要处理很短指标范围的形式。
核心思想有三步：先把普通幂 \(k^n\) 改写到下降阶乘基底上，再把出现的二项式卷积精确化简，最后分别在 \(83^3\)、\(89^3\)、\(97^3\) 下计算，并用中国剩余定理合并。
记
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
为下降阶乘。经典的 Stirling 展开为
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$
其中 \(\left\{{n \atop j}\right\}\) 是第二类 Stirling 数。把它代回原式，得到
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$
当 \(n>0\) 时，\(j=0\) 的那一项为零，所以真正需要处理的求和从 \(j=1\) 开始。
由于 \((k)_j=j!\binom{k}{j}\)，因此
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$
再利用恒等式
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$
就有
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$
而 \(j!\binom{n}{j}=n^{\underline{j}}\)，所以原问题被改写成
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$
这就是整套实现的核心公式。
固定一个素数 \(p\in\{83,89,97\}\)，现在只考虑模 \(p^3\) 的值。
如果 \(j\ge 3p\)，那么下降阶乘
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
一定包含至少三个 \(p\) 的倍数，因为任何长度为 \(3p\) 的连续整数块里至少有三个 \(p\) 的倍数。于是
$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$
所以整个第 \(j\) 项在模 \(p^3\) 下必为零。因此
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
这一步非常关键，因为它把原本长度约为 \(n\) 的求和，截成了长度只与 \(p\) 成正比的短和。
第二类 Stirling 数还满足有限差分公式
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$
把右边记为 \(D_j\)。难点在于：模 \(p^3\) 时，如果 \(p\mid j!\)，那么直接用 \(D_j/j!\) 并不安全。于是把阶乘拆成
$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$
这里 \(a_j\) 是 \(j!\) 的 \(p\)-进指数，\(q_j\) 是不含 \(p\) 的单位部分。由于 \(q_j\) 与 \(p\) 互素，所以它在模 \(p^3\) 下可逆，于是
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$
为了先除去 \(p^{a_j}\) 再取模，需要知道 \(D_j\) 在 \(p^{3+a_j}\) 模下的值。由于活跃区间满足 \(j<3p\)，所以 \(a_j\le 2\)。这说明统一在 \(p^5\) 模下计算 \(D_j\) 就足够了。实现正是按这个思路操作：先在 \(p^5\) 下求有限差分分子，再剥掉精确的 \(p\) 幂，最后只对单位部分求逆。
对每个 \(p\in\{83,89,97\}\)，都计算
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
因为 \(83^3\)、\(89^3\)、\(97^3\) 两两互素，所以中国剩余定理保证存在唯一的模
$$M=83^3\cdot 89^3\cdot 97^3$$
的剩余类 \(R\)，满足
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$
这个 \(R\) 就是题目要求的最终答案。
先直接计算：
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
再看变形后的公式。需要的 Stirling 数为
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1,$$
而下降阶乘为
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$
代入后得到
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
这个小例子说明，变形后的求和与原始定义完全一致，只是更适合做模运算。
实现按三个素数立方 \(83^3\)、\(89^3\)、\(97^3\) 分开处理。对于固定的素数 \(p\)，先令 \(J=\min(n,3p-1)\)，因为从这个范围之外开始，所有项都已经在模 \(p^3\) 下消失。
接着，程序构造一个 Pascal 风格的二项式系数表，得到所有 \(0\le i\le j\le J\) 的 \(\binom{j}{i}\bmod p^5\)。同时，它还预计算全部 \(i^n\bmod p^5\)。此外，对每个 \(j\) 都记录 \(j!\) 的 \(p\)-进指数，以及去掉这些 \(p\) 因子之后剩下的单位部分在模 \(p^3\) 下的值。
在主循环中，\(n^{\underline{j}}\) 通过连续乘上新的因子 \(n-j+1\) 来递推；\(2^{n-j}\) 则通过每一步乘上 \(2\) 在模 \(p^3\) 下的逆元来递推。随后计算有限差分分子 \(D_j\)，除去其中来自 \(j!\) 的精确 \(p\) 次幂，再乘上单位部分的逆元，就得到模 \(p^3\) 下的 Stirling 项。最后把这个项与 \(n^{\underline{j}}2^{n-j}\) 相乘并累加。
三个模数的结果算完后，再用中国剩余定理拼接成模 \(M\) 的唯一结果。C++ 实现会并行处理三个素数通道，而 Python 和 Java 实现按顺序处理。C++ 实现还额外检查了一个小样例 \(S(10)=142469423360\)，并验证模运算管线得到的剩余与直接结果一致。
对单个素数 \(p\)，设 \(J=\min(n,3p-1)\)。构造到第 \(J\) 行的二项式表需要 \(O(J^2)\) 时间和 \(O(J^2)\) 空间。预计算所有 \(i^n\bmod p^5\) 需要 \(O(J\log n)\) 时间。
主求和同样是 \(O(J^2)\) 时间，因为第 \(j\) 个 Stirling 项的有限差分公式需要对 \(i=0,\dots,j\) 全部求和。因此，单个素数通道的总复杂度是
$$O(J^2+J\log n)$$
时间和 \(O(J^2)\) 空间。由于本题中的素数固定，而且总有 \(J<3p\)，所以在目标输入 \(n=10^{18}\) 上，总工作量实际上可以视为常数级。
Нужно исследовать величину
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$
В задаче берётся \(n=10^{18}\), а требуется остаток \(S(10^{18})\) по модулю
$$M=83^3\cdot 89^3\cdot 97^3.$$
Прямое суммирование здесь совершенно нереально. Поэтому решение переписывает сумму в форму, где по модулю каждого куба простого числа существенен только короткий диапазон индексов.
Главная идея состоит в том, чтобы разложить обычную степень \(k^n\) по базе падающих факториалов, точно вычислить возникающую биномиальную свёртку и затем считать отдельно по модулям \(83^3\), \(89^3\) и \(97^3\).
Обозначим
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
падающий факториал. Тогда стандартное разложение через числа Стирлинга имеет вид
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$
где \(\left\{{n \atop j}\right\}\) обозначает число Стирлинга второго рода. Подстановка в исходную сумму даёт
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$
При \(n>0\) слагаемое с \(j=0\) равно нулю, поэтому реально суммирование начинается с \(j=1\).
Из равенства \((k)_j=j!\binom{k}{j}\) получаем
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$
Далее используется тождество
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j},$$
после чего сумма превращается в
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$
Так как \(j!\binom{n}{j}=n^{\underline{j}}\), приходим к основной формуле
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$
Зафиксируем один из простых \(p\in\{83,89,97\}\). Теперь нас интересует сумма по модулю \(p^3\).
Если \(j\ge 3p\), то произведение
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
содержит как минимум три кратных \(p\), потому что любой блок из \(3p\) последовательных целых чисел содержит три таких числа. Следовательно,
$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$
и всё \(j\)-е слагаемое равно \(0\pmod{p^3}\). Значит,
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Именно это короткое отсечение делает вычисление осуществимым.
Формула конечных разностей даёт
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$
Обозначим правую часть через \(D_j\). Прямо делить на \(j!\) по модулю \(p^3\) нельзя, если \(p\mid j!\). Поэтому раскладываем
$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$
Тогда \(q_j\) обратим по модулю \(p^3\), и можно написать
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$
Чтобы сначала убрать множитель \(p^{a_j}\), нужно знать \(D_j\) по модулю \(p^{3+a_j}\). В рабочем диапазоне \(j<3p\) выполняется \(a_j\le 2\), поэтому единого модуля \(p^5\) достаточно для всех \(j\). Именно так и делает реализация: считает числитель конечных разностей по модулю \(p^5\), отделяет точную степень \(p\) и лишь затем умножает на обратный элемент к единичной части \(q_j\) по модулю \(p^3\).
Для каждого \(p\in\{83,89,97\}\) вычисляется
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
Модули \(83^3\), \(89^3\) и \(97^3\) попарно взаимно просты, поэтому китайская теорема об остатках восстанавливает единственный класс \(R\) по модулю
$$M=83^3\cdot 89^3\cdot 97^3$$
такой, что
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$
Этот класс и есть искомый ответ.
Непосредственно получаем
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
Теперь проверим преобразованную формулу. Нужные числа Стирлинга таковы:
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$$
Падающие факториалы равны
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$
Следовательно,
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
Тем самым преобразование проверяется на маленьком случае до того, как запускается вся модульная схема для \(n=10^{18}\).
Реализация обрабатывает отдельно три модуля \(83^3\), \(89^3\) и \(97^3\). Для фиксированного простого \(p\) она берёт \(J=\min(n,3p-1)\), потому что дальше все члены уже нулевые по модулю \(p^3\).
Затем строится таблица биномиальных коэффициентов \(\binom{j}{i}\) в стиле треугольника Паскаля для всех \(0\le i\le j\le J\) по модулю \(p^5\). Одновременно заранее вычисляются значения \(i^n\bmod p^5\) для всех \(0\le i\le J\). Кроме того, для каждого \(j\) табулируются \(p\)-адическая степень факториала \(j!\) и его единичная часть по модулю \(p^3\).
В основном цикле \(n^{\underline{j}}\) обновляется умножением на следующий множитель \(n-j+1\), а \(2^{n-j}\) поддерживается последовательным умножением на обратный к \(2\) элемент по модулю \(p^3\). После этого вычисляется числитель конечных разностей \(D_j\), из него убирается точная степень \(p\), и результат умножается на обратный элемент к единичной части факториала. Полученный член прибавляется по модулю \(p^3\).
После получения трёх остатков реализация объединяет их китайской теоремой об остатках. Вариант на C++ вычисляет три простых канала параллельно, а варианты на Python и Java делают это последовательно. Реализация на C++ также проверяет малый случай \(S(10)=142469423360\) и убеждается, что модульный алгоритм даёт тот же остаток по модулю \(M\).
Для одного простого \(p\) обозначим \(J=\min(n,3p-1)\). Построение биномиальной таблицы до строки \(J\) требует \(O(J^2)\) времени и \(O(J^2)\) памяти. Предварительное вычисление всех \(i^n\bmod p^5\) для \(0\le i\le J\) стоит \(O(J\log n)\) времени.
Основная сумма также требует \(O(J^2)\) времени, поскольку в формуле конечных разностей член с индексом \(j\) суммируется по всем \(i=0,\dots,j\). Значит, один простой канал стоит
$$O(J^2+J\log n)$$
по времени и \(O(J^2)\) по памяти. Так как фактические простые фиксированы и всегда \(J<3p\), суммарная трудоёмкость для \(83\), \(89\) и \(97\) практически постоянна на целевом входе \(n=10^{18}\).
الكمية المطلوب حسابها هي
$$S(n)=\sum_{k=0}^{n}\binom{n}{k}k^n.$$
في هذه المسألة نأخذ \(n=10^{18}\)، والمطلوب هو باقي \(S(10^{18})\) modulo
$$M=83^3\cdot 89^3\cdot 97^3.$$
الحساب المباشر للمجموع مستحيل عمليًا، لذلك تعيد الطريقة كتابة التعبير بحيث لا يبقى مؤثرًا modulo كل مكعب أولي إلا مجال قصير جدًا من الحدود.
الفكرة الأساسية هي تحويل القوة العادية \(k^n\) إلى توسعة على أساس العامل التنازلي، ثم تبسيط الالتفاف الثنائي الناتج تبسيطًا دقيقًا، وبعد ذلك حساب المسألة كلٌّ على حدة modulo \(83^3\) و\(89^3\) و\(97^3\).
لنكتب
$$(k)_j=k(k-1)\cdots(k-j+1)=k^{\underline{j}}$$
للدلالة على العامل التنازلي. عندئذ تكون توسعة Stirling القياسية هي
$$k^n=\sum_{j=0}^{n}\left\{{n \atop j}\right\}(k)_j,$$
حيث \(\left\{{n \atop j}\right\}\) هو عدد Stirling من النوع الثاني. وبالتعويض في المجموع الأصلي نحصل على
$$S(n)=\sum_{j=0}^{n}\left\{{n \atop j}\right\}\sum_{k=0}^{n}\binom{n}{k}(k)_j.$$
وعندما يكون \(n>0\) فإن الحد الموافق لـ \(j=0\) يساوي صفرًا، لذلك يبدأ المجموع الفعلي من \(j=1\).
بما أن \((k)_j=j!\binom{k}{j}\)، فإن
$$\sum_{k=0}^{n}\binom{n}{k}(k)_j=j!\sum_{k=j}^{n}\binom{n}{k}\binom{k}{j}.$$
وباستخدام الهوية
$$\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}$$
يتحول هذا إلى
$$j!\binom{n}{j}\sum_{k=j}^{n}\binom{n-j}{k-j}=j!\binom{n}{j}2^{n-j}.$$
ولأن \(j!\binom{n}{j}=n^{\underline{j}}\)، نصل إلى الصيغة المحورية
$$S(n)=\sum_{j=1}^{n}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}.$$
ثبّت أحد الأعداد الأولية \(p\in\{83,89,97\}\). نريد الآن قيمة المجموع المحوَّل modulo \(p^3\).
إذا كان \(j\ge 3p\)، فإن العامل التنازلي
$$n^{\underline{j}}=n(n-1)\cdots(n-j+1)$$
يحتوي على ثلاثة مضاعفات على الأقل للعدد \(p\)، لأن كل كتلة من \(3p\) أعداد صحيحة متتالية تحتوي على ثلاثة مضاعفات لـ \(p\). ومن ثم
$$v_p\!\left(n^{\underline{j}}\right)\ge 3,$$
فيصبح الحد كله مساويًا للصفر modulo \(p^3\). ولذلك
$$S(n)\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
هذا القطع القصير هو ما يجعل الحساب ممكنًا.
تعطي صيغة الفروق المنتهية العلاقة
$$j!\left\{{n \atop j}\right\}=\sum_{i=0}^{j}(-1)^{j-i}\binom{j}{i}i^n.$$
لنسمِّ الطرف الأيمن \(D_j\). لا يمكن القسمة مباشرة على \(j!\) modulo \(p^3\) عندما يكون \(p\mid j!\). لذلك نكتب
$$j!=p^{a_j}q_j,\qquad p\nmid q_j.$$
وبهذا يصبح \(q_j\) قابلاً للعكس modulo \(p^3\)، فنحصل على
$$\left\{{n \atop j}\right\}\equiv \frac{D_j}{p^{a_j}}\,q_j^{-1}\pmod{p^3}.$$
ولكي ننفذ هذه الخطوة بأمان نحتاج إلى معرفة \(D_j\) modulo \(p^{3+a_j}\). وفي المجال الفعّال \(j<3p\) يكون دائمًا \(a_j\le 2\)، لذلك يكفي العمل تحت modulo \(p^5\) لجميع الحدود. وهذا هو سبب بناء التنفيذ لبسط صيغة الفروق المنتهية modulo \(p^5\)، ثم إزالة قوة \(p\) الدقيقة، ثم أخذ معكوس الجزء الوحدوي فقط.
لكل \(p\in\{83,89,97\}\) نحسب
$$r_p\equiv \sum_{j=1}^{\min(n,\,3p-1)}\left\{{n \atop j}\right\}n^{\underline{j}}2^{n-j}\pmod{p^3}.$$
ولأن المقادير \(83^3\) و\(89^3\) و\(97^3\) متباينة أوليًا اثنين اثنين، فإن مبرهنة الباقي الصيني تعيد بناء الفئة الوحيدة \(R\) modulo
$$M=83^3\cdot 89^3\cdot 97^3$$
بحيث تحقق
$$R\equiv r_{83}\pmod{83^3},\qquad R\equiv r_{89}\pmod{89^3},\qquad R\equiv r_{97}\pmod{97^3}.$$
وهذه الفئة هي الجواب المطلوب.
بالحساب المباشر نجد
$$S(3)=\binom{3}{0}0^3+\binom{3}{1}1^3+\binom{3}{2}2^3+\binom{3}{3}3^3=0+3+24+27=54.$$
والآن نستخدم الصيغة المحوَّلة. أعداد Stirling اللازمة هي
$$\left\{{3 \atop 1}\right\}=1,\qquad \left\{{3 \atop 2}\right\}=3,\qquad \left\{{3 \atop 3}\right\}=1.$$
كما أن
$$3^{\underline{1}}=3,\qquad 3^{\underline{2}}=6,\qquad 3^{\underline{3}}=6.$$
إذًا
$$\begin{aligned} S(3) &=\left\{{3 \atop 1}\right\}3^{\underline{1}}2^2 +\left\{{3 \atop 2}\right\}3^{\underline{2}}2^1 +\left\{{3 \atop 3}\right\}3^{\underline{3}}2^0\\ &=1\cdot 3\cdot 4+3\cdot 6\cdot 2+1\cdot 6\cdot 1\\ &=12+36+6=54. \end{aligned}$$
وهذا يؤكد أن إعادة الصياغة مكافئة تمامًا للتعريف الأصلي قبل الانتقال إلى الحساب المعياري الكبير.
يعالج التنفيذ مكعبات الأعداد الأولية الثلاثة \(83^3\) و\(89^3\) و\(97^3\) كلًّا على حدة. ولعدد أولي ثابت \(p\)، يختار \(J=\min(n,3p-1)\)، لأن جميع الحدود بعد ذلك تختفي أصلًا modulo \(p^3\).
بعد ذلك تُبنى لوحة شبيهة بمثلث باسكال لتوليد معاملات \(\binom{j}{i}\) لكل \(0\le i\le j\le J\) modulo \(p^5\). كما تُحسب مسبقًا القيم \(i^n\bmod p^5\) لجميع \(i\) في هذا المجال. ويُخزَّن أيضًا لكل \(j\) كلٌّ من رتبة \(p\)-adic في \(j!\) والجزء الوحدوي المتبقي من \(j!\) modulo \(p^3\).
داخل الحلقة الرئيسية يُحدَّث \(n^{\underline{j}}\) بضربه في العامل التالي \(n-j+1\)، ويُحدَّث \(2^{n-j}\) بضربه في معكوس \(2\) modulo \(p^3\) في كل خطوة. ثم يُحسَب بسط الفروق المنتهية \(D_j\)، وتُزال منه قوة \(p\) الدقيقة القادمة من \(j!\)، ثم يُضرب في معكوس الجزء الوحدوي، وبعد ذلك يُجمع الحد الناتج modulo \(p^3\).
وبعد الحصول على البواقي الثلاثة، يدمجها التنفيذ بمبرهنة الباقي الصيني. تنفيذ C++ يعالج القنوات الثلاث بالتوازي، بينما يعالجها تنفيذا Python وJava على الترتيب. كما أن تنفيذ C++ يتحقق من الحالة الصغيرة \(S(10)=142469423360\) ويتأكد من أن خط الحساب المعياري يعطي الباقي نفسه modulo \(M\).
لأولي واحد \(p\)، ولْيكن \(J=\min(n,3p-1)\). بناء جدول المعاملات الثنائية حتى الصف \(J\) يحتاج إلى \(O(J^2)\) زمنًا و\(O(J^2)\) ذاكرة. أمّا التحضير المسبق للقيم \(i^n\bmod p^5\) لكل \(0\le i\le J\) فيحتاج إلى \(O(J\log n)\) زمنًا.
ويحتاج المجموع الرئيسي أيضًا إلى \(O(J^2)\) زمنًا، لأن صيغة الفروق المنتهية للحد ذي الفهرس \(j\) تجمع على جميع \(i=0,\dots,j\). ومن ثم فإن كلفة قناة أولية واحدة هي
$$O(J^2+J\log n)$$
زمنًا و\(O(J^2)\) ذاكرة. وبما أن الأعداد الأولية الفعلية ثابتة وأن \(J<3p\) دائمًا، فإن الكلفة الكلية على \(83\) و\(89\) و\(97\) تعد ثابتة عمليًا عند الإدخال المستهدف \(n=10^{18}\).