For Problem 522, the central observation is that the target quantity can be evaluated directly from a finite formula instead of simulating the underlying blackout process. The C++, Python, and Java implementations compute the value for \(n=12344321\) modulo
$$M=135707531.$$
The practical task is therefore to evaluate one leading term and one indexed sum efficiently in modular arithmetic.
The implementations use the identity
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
The mathematics of the solution is about reorganizing this expression so that every summand can be produced quickly and safely modulo \(M\).
Write
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
Then
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
This split is useful because the first part is a single modular power, while the second part is a uniform family of terms indexed by \(m\). It also makes the small edge cases transparent: if \(n<4\), the interval \(2\le m\le n-2\) is empty, so only \(Z(n)\) remains.
The coefficient is genuinely integral, because
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
So the formula introduces no fractional ambiguity before the reduction modulo \(M\).
For the target range, \(n<M\), and the modulus \(M\) is prime. Hence every integer \(1,2,\dots,n\) has a multiplicative inverse modulo \(M\). Define
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
Then each summand becomes
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}.$$
After this rewrite, the entire computation is reduced to modular multiplications and modular exponentiation. No explicit division is needed during the main loop.
The inverse table is built with the standard recurrence
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
for \(2\le i\le n\). Once the \(u_i\) values are known, the inverse factorials follow from a forward product:
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
A separate forward pass computes \(P=n!\bmod M\). After these linear precomputations, the coefficient part \(P\,v_m\,u_{n-m}\) of every term is available in \(O(1)\) time.
The remaining factor in every indexed term is
$$(m-1)^m\pmod{M}.$$
The implementations evaluate it with binary exponentiation. Repeated squaring reduces one power evaluation from linear time in \(m\) to logarithmic time in \(m\), so each term needs only a constant number of modular multiplications plus one \(O(\log m)\) exponentiation.
This is why the sum is feasible even for a very large target \(n\): the expensive part is the sequence of fast power calls, not the factorial coefficient.
For \(n=8\), the leading term is
$$Z(8)=8\cdot 7\cdot 6^7=15676416.$$
The summation runs over \(m=2,3,4,5,6\). The corresponding coefficients and contributions are
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
Adding everything gives
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736.$$
In this example the total is still below \(M\), so the modular answer equals the ordinary integer answer. This matches the checkpoint used by the implementation.
The C++, Python, and Java implementations all follow the same arithmetic plan. They first precompute modular inverses up to \(n\), then compute \(n!\bmod M\), and then build a prefix table for inverse factorials. After that they evaluate the leading term \(n(n-1)(n-2)^{n-1}\) once.
Next they iterate through \(m=2,\dots,n-2\). For each \(m\), the factorial coefficient is assembled from the precomputed tables, the power \((m-1)^m\) is obtained by binary exponentiation, and the contribution is added modulo \(M\). The C++ implementation additionally splits the \(m\)-interval into chunks and combines partial sums from multiple workers; the Python and Java implementations use the same formula sequentially.
Precomputing inverses, the factorial value, and the inverse factorial table takes \(O(n)\) time and \(O(n)\) memory. The main sum has \(n-3\) terms, and each term requires one modular exponentiation of cost \(O(\log m)\). Therefore the total time complexity is \(O(n\log n)\), with \(O(n)\) memory usage. In the multithreaded C++ version, the arithmetic workload is the same, but the wall-clock time is reduced by distributing the summation interval across several workers.
Bei Problem 522 ist die entscheidende Beobachtung, dass sich die gesuchte Größe direkt durch eine endliche Formel auswerten lässt, statt den zugrunde liegenden Blackout-Prozess zu simulieren. Die Implementierungen in C++, Python und Java berechnen den Wert für \(n=12344321\) modulo
$$M=135707531.$$
Die praktische Aufgabe besteht daher darin, einen führenden Term und eine indizierte Summe effizient in modularer Arithmetik zu berechnen.
Die Implementierungen verwenden die Identität
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
Mathematisch geht es nun darum, diesen Ausdruck so umzuformen, dass jeder Summand schnell und sicher modulo \(M\) ausgewertet werden kann.
Setze
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
Dann gilt
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
Diese Aufspaltung ist nützlich, weil der erste Teil nur aus einer einzigen modularen Potenz besteht, während der zweite Teil eine einheitliche Familie von Summanden mit Index \(m\) bildet. Außerdem werden die kleinen Randfälle sofort klar: Für \(n<4\) ist das Intervall \(2\le m\le n-2\) leer, also bleibt nur \(Z(n)\).
Der Koeffizient ist tatsächlich ganzzahlig, denn
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
Die Formel erzeugt also vor der Reduktion modulo \(M\) keine Mehrdeutigkeit durch Brüche.
Im Zielbereich gilt \(n<M\), und der Modulus \(M\) ist prim. Deshalb besitzt jede Zahl \(1,2,\dots,n\) ein multiplikatives Inverses modulo \(M\). Definiere
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
Damit wird jeder Summand zu
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}.$$
Nach dieser Umformung besteht die gesamte Rechnung nur noch aus modularen Multiplikationen und modularer Exponentiation. Explizite Division tritt in der Hauptschleife nicht mehr auf.
Die Tabelle der Inversen wird mit der Standardrekursion aufgebaut:
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
für \(2\le i\le n\). Sobald die Werte \(u_i\) bekannt sind, folgen die inversen Fakultäten durch ein Vorwärtsprodukt:
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
Ein weiterer Vorwärtsdurchlauf liefert \(P=n!\bmod M\). Nach diesen linearen Vorberechnungen steht der Koeffiziententeil \(P\,v_m\,u_{n-m}\) jedes Summanden in \(O(1)\) Zeit zur Verfügung.
Der verbleibende Faktor in jedem Summanden ist
$$(m-1)^m\pmod{M}.$$
Die Implementierungen berechnen ihn per binärer Exponentiation. Wiederholtes Quadrieren reduziert eine Potenzberechnung von linearer Zeit in \(m\) auf logarithmische Zeit in \(m\), sodass pro Summand nur eine konstante Zahl modularer Multiplikationen plus eine \(O(\log m)\)-Potenzierung anfällt.
Darum bleibt die Summe selbst für sehr großes \(n\) beherrschbar: Der teure Teil sind die schnellen Potenzaufrufe, nicht der Fakultätskoeffizient.
Für \(n=8\) ist der führende Term
$$Z(8)=8\cdot 7\cdot 6^7=15676416.$$
Die Summe läuft über \(m=2,3,4,5,6\). Die zugehörigen Koeffizienten und Beiträge sind
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
Die Summe aller Teile ergibt
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736.$$
In diesem kleinen Beispiel liegt das Ergebnis noch unter \(M\), daher stimmt die modulare Antwort mit dem gewöhnlichen Ganzzahlergebnis überein. Genau dieser Wert wird von der Implementierung als Kontrollpunkt verwendet.
Die Implementierungen in C++, Python und Java folgen demselben arithmetischen Plan. Zuerst werden alle modularen Inversen bis \(n\) vorab berechnet, danach \(n!\bmod M\), und anschließend wird eine Präfixtabelle für inverse Fakultäten aufgebaut. Danach wird der führende Term \(n(n-1)(n-2)^{n-1}\) einmal ausgewertet.
Anschließend läuft eine Schleife über \(m=2,\dots,n-2\). Für jedes \(m\) wird der Fakultätskoeffizient aus den vorberechneten Tabellen zusammengesetzt, die Potenz \((m-1)^m\) per binärer Exponentiation bestimmt und der Beitrag modulo \(M\) addiert. Die C++-Implementierung zerlegt das Intervall zusätzlich in Blöcke und fasst partielle Summen mehrerer Worker zusammen; die Python- und Java-Implementierungen werten dieselbe Formel sequentiell aus.
Das Vorberechnen der Inversen, des Fakultätswertes und der Tabelle der inversen Fakultäten benötigt \(O(n)\) Zeit und \(O(n)\) Speicher. Die Hauptsumme enthält \(n-3\) Summanden, und jeder Summand verlangt genau eine modulare Exponentiation mit Kosten \(O(\log m)\). Damit beträgt die gesamte Zeitkomplexität \(O(n\log n)\) bei \(O(n)\) Speicher. In der mehrfädigen C++-Variante bleibt die arithmetische Gesamtarbeit gleich, aber die reale Laufzeit sinkt durch die Verteilung des Summationsintervalls auf mehrere Worker.
Problem 522 için temel gözlem, istenen büyüklüğün alttaki blackout sürecini simüle etmeden doğrudan sonlu bir formülle hesaplanabilmesidir. C++, Python ve Java uygulamaları \(n=12344321\) değeri için sonucu
$$M=135707531$$
modunda üretir. Dolayısıyla pratik görev, bir önder terimi ve indeksli bir toplamı modüler aritmetikte verimli biçimde değerlendirmektir.
Uygulamaların kullandığı özdeşlik şudur:
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
Çözümün matematiksel kısmı, bu ifadeyi her terim hızlı ve güvenli biçimde \(M\) modunda hesaplanacak şekilde yeniden düzenlemektir.
Şöyle yazalım:
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
O zaman
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
Bu ayrım faydalıdır; çünkü ilk parça tek bir modüler üs alma işlemidir, ikinci parça ise \(m\) ile indekslenen tek tip bir terim ailesidir. Ayrıca küçük kenar durumları da hemen görünür: \(n<4\) ise \(2\le m\le n-2\) aralığı boştur ve geriye yalnızca \(Z(n)\) kalır.
Katsayı gerçekten tam sayıdır; çünkü
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
Yani mod \(M\)'ye geçmeden önce formülde kesirsel bir belirsizlik yoktur.
Hedef aralıkta \(n<M\) ve modül \(M\) asaldır. Bu yüzden \(1,2,\dots,n\) sayılarının her biri \(M\) modunda çarpımsal tersi olan bir değere sahiptir. Şunları tanımlayalım:
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
Böylece her terim
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}$$
şeklini alır. Bu dönüşümden sonra bütün hesap modüler çarpımlar ve modüler üs almadan ibarettir; ana döngüde açık bölme işlemi kalmaz.
Ters tablosu standart yineleme ile kurulur:
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
burada \(2\le i\le n\). \(u_i\) değerleri bilindikten sonra ters faktöriyeller ileri yönde çarpılarak elde edilir:
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
Ayrı bir ileri geçiş de \(P=n!\bmod M\) değerini hesaplar. Bu doğrusal önhesaplardan sonra her terimin katsayı kısmı \(P\,v_m\,u_{n-m}\) için \(O(1)\) zaman yeterlidir.
Her indeksli terimde kalan çarpan
$$(m-1)^m\pmod{M}$$
ifadesidir. Uygulamalar bunu ikili üs alma ile hesaplar. Tekrarlı karesini alma, bir kuvvet hesabını \(m\)'e doğrusal zamandan \(m\)'de logaritmik zamana düşürür; böylece her terim sabit sayıda modüler çarpım ve bir adet \(O(\log m)\) üs alma gerektirir.
Büyük \(n\) için yöntemin çalışabilir olmasının nedeni budur: pahalı kısım faktöriyel katsayısı değil, hızlı üs alma çağrılarının dizisidir.
\(n=8\) için önder terim
$$Z(8)=8\cdot 7\cdot 6^7=15676416$$
olur. Toplam \(m=2,3,4,5,6\) üzerinde alınır. Buna karşılık gelen katsayılar ve katkılar şunlardır:
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
Hepsi toplanınca
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736$$
elde edilir. Bu küçük örnekte toplam hâlâ \(M\)'den küçük olduğu için modüler sonuç ile normal tamsayı sonucu aynıdır. Bu değer, uygulamanın kullandığı kontrol noktasıyla da tam uyuşur.
C++, Python ve Java uygulamaları aynı aritmetik planı izler. Önce \(n\)'e kadar modüler tersler önhesaplanır, sonra \(n!\bmod M\) bulunur ve ardından ters faktöriyeller için bir önek tablosu kurulur. Daha sonra \(n(n-1)(n-2)^{n-1}\) önder terimi bir kez hesaplanır.
Ardından \(m=2,\dots,n-2\) için döngü çalışır. Her \(m\) değerinde faktöriyel katsayısı önceden hazırlanmış tablolardan kurulur, \((m-1)^m\) ikili üs alma ile hesaplanır ve katkı \(M\) modunda toplama eklenir. C++ uygulaması ayrıca \(m\) aralığını parçalara bölüp çoklu işçilerden gelen kısmi toplamları birleştirir; Python ve Java uygulamaları ise aynı formülü ardışık olarak değerlendirir.
Terslerin, faktöriyel değerinin ve ters faktöriyel tablosunun hazırlanması \(O(n)\) zaman ve \(O(n)\) bellek gerektirir. Ana toplam \(n-3\) terim içerir ve her terimde maliyeti \(O(\log m)\) olan bir modüler üs alma vardır. Bu nedenle toplam zaman karmaşıklığı \(O(n\log n)\), bellek kullanımı ise \(O(n)\) olur. Çok iş parçacıklı C++ sürümünde aritmetik iş yükü değişmez, fakat toplam aralık birden çok işçiye dağıtıldığı için gerçek çalışma süresi azalır.
En el Problema 522, la observación decisiva es que la cantidad buscada puede evaluarse directamente mediante una fórmula finita, sin simular el proceso original de blackout. Las implementaciones en C++, Python y Java calculan el valor para \(n=12344321\) módulo
$$M=135707531.$$
Por tanto, la tarea práctica consiste en evaluar con eficiencia un término principal y una suma indexada dentro de la aritmética modular.
Las implementaciones usan la identidad
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
La parte matemática de la solución consiste en reorganizar esta expresión para que cada sumando pueda generarse rápida y limpiamente módulo \(M\).
Escribimos
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
Entonces
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
Esta separación es útil porque la primera parte es solo una potencia modular, mientras que la segunda es una familia uniforme de términos indexados por \(m\). También aclara enseguida los casos pequeños: si \(n<4\), el intervalo \(2\le m\le n-2\) está vacío y solo queda \(Z(n)\).
Además, el coeficiente es realmente entero, ya que
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
Así, antes de reducir módulo \(M\), la fórmula no introduce ninguna ambigüedad fraccionaria.
En el rango objetivo se cumple \(n<M\), y el módulo \(M\) es primo. Por eso cada entero \(1,2,\dots,n\) posee inverso multiplicativo módulo \(M\). Definimos
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
Entonces cada sumando toma la forma
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}.$$
Tras esta reescritura, todo el cálculo queda reducido a multiplicaciones modulares y exponenciación modular. En el bucle principal ya no aparece ninguna división explícita.
La tabla de inversos se construye con la recurrencia estándar
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
para \(2\le i\le n\). Una vez conocidos los \(u_i\), los inversos factoriales se obtienen mediante un producto prefijo:
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
Otro recorrido hacia adelante calcula \(P=n!\bmod M\). Tras estas precomputaciones lineales, la parte coeficiente \(P\,v_m\,u_{n-m}\) de cada término queda disponible en \(O(1)\) tiempo.
El factor restante en cada término indexado es
$$(m-1)^m\pmod{M}.$$
Las implementaciones lo evalúan con exponenciación binaria. El método de cuadrados repetidos reduce una potencia de tiempo lineal en \(m\) a tiempo logarítmico en \(m\), de modo que cada sumando requiere solo un número constante de multiplicaciones modulares más una exponenciación \(O(\log m)\).
Por eso la suma sigue siendo viable incluso para un \(n\) muy grande: la parte costosa es la sucesión de potencias rápidas, no el coeficiente factorial.
Para \(n=8\), el término principal es
$$Z(8)=8\cdot 7\cdot 6^7=15676416.$$
La suma recorre \(m=2,3,4,5,6\). Los coeficientes y contribuciones correspondientes son
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
Al sumar todo se obtiene
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736.$$
En este ejemplo el total sigue siendo menor que \(M\), así que el resultado modular coincide con el entero ordinario. Ese valor coincide exactamente con el punto de comprobación utilizado por la implementación.
Las implementaciones en C++, Python y Java siguen el mismo plan aritmético. Primero precalculan los inversos modulares hasta \(n\), luego calculan \(n!\bmod M\), y después construyen una tabla prefija de inversos factoriales. A continuación evalúan una sola vez el término principal \(n(n-1)(n-2)^{n-1}\).
Después recorren \(m=2,\dots,n-2\). Para cada \(m\), el coeficiente factorial se arma a partir de las tablas precalculadas, la potencia \((m-1)^m\) se obtiene por exponenciación binaria y la contribución se suma módulo \(M\). La implementación en C++ además divide el intervalo de \(m\) en bloques y combina sumas parciales de varios trabajadores; las implementaciones en Python y Java evalúan la misma fórmula de forma secuencial.
Precalcular los inversos, el valor factorial y la tabla de inversos factoriales cuesta \(O(n)\) tiempo y \(O(n)\) memoria. La suma principal contiene \(n-3\) términos, y cada término requiere una exponenciación modular de costo \(O(\log m)\). En consecuencia, la complejidad temporal total es \(O(n\log n)\), con uso de memoria \(O(n)\). En la versión multihilo de C++, la carga aritmética total es la misma, pero el tiempo de reloj disminuye al repartir el intervalo de sumación entre varios trabajadores.
对于第 522 题，最关键的观察是：目标数量并不需要去模拟原始的 blackout 过程，而是可以直接用一个有限公式来计算。C++、Python 和 Java 实现都要求在
$$M=135707531$$
这个模数下求出 \(n=12344321\) 时的值。因此，真正需要解决的是如何把一个主项和一个带索引的求和高效地放到模运算里完成。
实现所依赖的恒等式是
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
因此，数学上的重点不在于重新模拟原问题，而在于把这个表达式改写成适合快速模运算的形式，使得每个求和项都能稳定、快速地算出来。
记
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
则有
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
这样拆开以后，第一部分只是一次模幂，而第二部分是一族结构完全一致、只由 \(m\) 变化的项。这种写法还立即说明了边界情况：如果 \(n<4\)，那么区间 \(2\le m\le n-2\) 为空，整个答案只剩下 \(Z(n)\)。
另外，分式系数本身其实是整数，因为
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
也就是说，在取模之前，这个公式并没有真正引入“分数”带来的歧义。
在目标范围内有 \(n<M\)，而且模数 \(M\) 是素数，所以 \(1,2,\dots,n\) 中的每个整数在模 \(M\) 下都有乘法逆元。定义
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
那么每一项都可以写成
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}.$$
这样处理之后，整个问题就只剩下模乘和模幂。主循环里不再做显式除法，而是统一改成与预处理好的逆元相乘。
逆元表使用标准递推式构造：
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
其中 \(2\le i\le n\)。当所有 \(u_i\) 已知以后，逆阶乘就可以通过前缀乘积得到：
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
与此同时，再做一次从前到后的乘法就能得到 \(P=n!\bmod M\)。完成这些线性预处理之后，每个求和项中的系数部分 \(P\,v_m\,u_{n-m}\) 都可以在 \(O(1)\) 时间内取出。
每个带索引的求和项还剩下一个幂因子
$$(m-1)^m\pmod{M}.$$
实现使用二进制快速幂来计算它。重复平方法把一次幂运算从关于 \(m\) 的线性时间降到关于 \(m\) 的对数时间，因此每个求和项只需要常数次模乘，再加一次 \(O(\log m)\) 的幂运算。
这也是整个算法之所以能支撑很大的 \(n\) 的原因：真正昂贵的是一系列快速幂调用，而不是阶乘系数本身。
当 \(n=8\) 时，主项为
$$Z(8)=8\cdot 7\cdot 6^7=15676416.$$
此时求和范围是 \(m=2,3,4,5,6\)。对应的系数与贡献分别为
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
把这些全部加起来得到
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736.$$
在这个小例子里，总和仍然小于 \(M\)，所以模结果与普通整数结果一致。这个数值与实现中的校验点完全相符。
C++、Python 和 Java 实现遵循同一套算术流程。它们先预处理 \(1\) 到 \(n\) 的模逆元，再计算 \(n!\bmod M\)，然后构造逆阶乘的前缀表。之后，主项 \(n(n-1)(n-2)^{n-1}\) 只需要单独计算一次。
接下来程序遍历 \(m=2,\dots,n-2\)。对每个 \(m\)，先用预处理表拼出阶乘系数，再用二进制快速幂算出 \((m-1)^m\)，最后把这一项累加到模 \(M\) 的答案里。C++ 实现还会把 \(m\) 的区间切成多个块，分别计算局部和，再把这些部分结果合并；Python 和 Java 实现则按同样的公式顺序计算。
预处理逆元、阶乘值和逆阶乘表需要 \(O(n)\) 时间与 \(O(n)\) 空间。主求和一共有 \(n-3\) 项，而每一项都需要一次代价为 \(O(\log m)\) 的模幂运算，所以总时间复杂度是 \(O(n\log n)\)，空间复杂度是 \(O(n)\)。在多线程的 C++ 版本中，总算术工作量并没有改变，但由于求和区间被分配给多个工作单元，实际墙钟时间会下降。
Для задачи 522 ключевое наблюдение состоит в том, что искомую величину можно вычислить напрямую по конечной формуле, не моделируя исходный blackout-процесс. Реализации на C++, Python и Java вычисляют значение при \(n=12344321\) по модулю
$$M=135707531.$$
Поэтому практическая задача сводится к эффективному вычислению одного главного слагаемого и одной индексированной суммы в модульной арифметике.
Реализации используют тождество
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
Математическая часть решения заключается в том, чтобы перестроить это выражение так, чтобы каждый член суммы можно было быстро и надежно вычислять по модулю \(M\).
Обозначим
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
Тогда
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
Такое разбиение удобно, потому что первая часть представляет собой одну модульную степень, а вторая часть состоит из однотипных членов, зависящих только от индекса \(m\). Одновременно становятся видны малые граничные случаи: если \(n<4\), то промежуток \(2\le m\le n-2\) пуст, и остается только \(Z(n)\).
Коэффициент действительно является целым числом, поскольку
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
Значит, до перехода к модулю \(M\) никакой дробной неоднозначности здесь нет.
В целевом диапазоне выполняется \(n<M\), а модуль \(M\) является простым. Следовательно, каждое число \(1,2,\dots,n\) имеет мультипликативный обратный элемент по модулю \(M\). Введем обозначения
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
Тогда каждый член суммы принимает вид
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}.$$
После этого преобразования все вычисление сводится к модульным умножениям и модульному возведению в степень. Явного деления в основном цикле уже не остается.
Таблица обратных строится по стандартной рекуррентной формуле
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
для \(2\le i\le n\). После того как все \(u_i\) известны, обратные факториалы находятся префиксным произведением:
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
Еще один линейный проход дает \(P=n!\bmod M\). После этих подготовительных вычислений коэффициентная часть \(P\,v_m\,u_{n-m}\) любого члена доступна за \(O(1)\) времени.
Оставшийся множитель в каждом индексированном члене равен
$$(m-1)^m\pmod{M}.$$
Реализации считают его бинарным возведением в степень. Метод повторного возведения в квадрат уменьшает стоимость одной степени с линейной по \(m\) до логарифмической по \(m\), поэтому на каждый член требуется лишь постоянное число модульных умножений и одна экспонентация стоимости \(O(\log m)\).
Именно поэтому метод остается практичным даже для очень большого \(n\): дорогостоящей частью оказываются быстрые степени, а не факториальный коэффициент.
При \(n=8\) главный член равен
$$Z(8)=8\cdot 7\cdot 6^7=15676416.$$
Сумма идет по \(m=2,3,4,5,6\). Соответствующие коэффициенты и вклады таковы:
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
Складывая все части, получаем
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736.$$
В этом примере итог еще меньше \(M\), поэтому ответ по модулю совпадает с обычным целым значением. Это полностью совпадает с контрольной точкой, используемой в реализации.
Реализации на C++, Python и Java придерживаются одного и того же арифметического плана. Сначала они предвычисляют все модульные обратные до \(n\), затем находят \(n!\bmod M\), а после этого строят префиксную таблицу обратных факториалов. Далее один раз вычисляется главный член \(n(n-1)(n-2)^{n-1}\).
Затем выполняется проход по \(m=2,\dots,n-2\). Для каждого \(m\) факториальный коэффициент собирается из предвычисленных таблиц, степень \((m-1)^m\) находится бинарным возведением в степень, и вклад добавляется по модулю \(M\). Реализация на C++ дополнительно делит интервал значений \(m\) на блоки и затем объединяет частичные суммы нескольких рабочих потоков; реализации на Python и Java вычисляют ту же формулу последовательно.
Предвычисление обратных, значения факториала и таблицы обратных факториалов требует \(O(n)\) времени и \(O(n)\) памяти. Основная сумма содержит \(n-3\) членов, и для каждого члена нужна одна модульная степень стоимости \(O(\log m)\). Следовательно, общая временная сложность равна \(O(n\log n)\), а потребление памяти равно \(O(n)\). В многопоточной версии на C++ суммарная арифметическая работа не меняется, но реальное время выполнения уменьшается за счет распределения интервала суммирования между несколькими рабочими потоками.
في المسألة 522 تكون الملاحظة الحاسمة هي أن القيمة المطلوبة لا تحتاج إلى محاكاة عملية blackout الأصلية، بل يمكن حسابها مباشرة من صيغة منتهية. وتقوم تطبيقات C++ وPython وJava بحساب القيمة عند \(n=12344321\) بترديد
$$M=135707531.$$
لذلك فالمهمة العملية هي تقييم حد رئيسي واحد ومجموع مفهرس واحد بكفاءة داخل الحسابات المعيارية.
تعتمد التطبيقات على الهوية التالية:
$$F(n)\equiv n(n-1)(n-2)^{n-1}+\sum_{m=2}^{n-2}\frac{n!}{m!(n-m)}(m-1)^m \pmod{M}.$$
والجزء الرياضي من الحل يتمثل في إعادة تنظيم هذه الصيغة بحيث يمكن إنتاج كل حد من حدود المجموع بسرعة وبصورة مستقرة بترديد \(M\).
لنكتب
$$Z(n)=n(n-1)(n-2)^{n-1},\qquad T_m(n)=\frac{n!}{m!(n-m)}(m-1)^m.$$
وعندئذٍ
$$F(n)\equiv Z(n)+\sum_{m=2}^{n-2}T_m(n)\pmod{M}.$$
هذا الفصل مفيد لأن الجزء الأول ليس إلا قوة معيارية واحدة، بينما الجزء الثاني يتكون من عائلة منتظمة من الحدود المفهرسة بالمتغير \(m\). كما أنه يكشف الحالات الصغيرة مباشرة: إذا كان \(n<4\) فإن المجال \(2\le m\le n-2\) يكون فارغًا، فلا يبقى إلا \(Z(n)\).
كما أن المعامل عدد صحيح فعلًا لأن
$$\frac{n!}{m!(n-m)}=\binom{n}{m}(n-m-1)!.$$
إذن لا توجد أي ضبابية كسرية في الصيغة قبل أخذ الباقي بترديد \(M\).
ضمن المجال المستهدف لدينا \(n<M\)، كما أن العدد \(M\) أولي. لذلك فإن كل عدد من \(1,2,\dots,n\) يملك معكوسًا ضربيًا بترديد \(M\). لنعرّف
$$u_i\equiv i^{-1}\pmod{M},\qquad v_m\equiv (m!)^{-1}\pmod{M},\qquad P\equiv n!\pmod{M}.$$
وبهذا يصبح كل حد
$$T_m(n)\equiv P\,v_m\,u_{n-m}(m-1)^m\pmod{M}.$$
بعد هذه الصياغة تصبح العملية كلها عبارة عن ضربات معيارية ورفع معياري للأس. ولا يعود هناك أي قسمة صريحة داخل الحلقة الرئيسية.
يُبنى جدول المعكوسات بالصيغة التراجعية القياسية
$$u_1=1,\qquad u_i\equiv M-\left\lfloor\frac{M}{i}\right\rfloor u_{M\bmod i}\pmod{M}$$
وذلك لكل \(2\le i\le n\). وبعد معرفة القيم \(u_i\)، نحصل على معكوسات المضروب بواسطة حاصل ضرب بادئي:
$$v_0=1,\qquad v_m\equiv v_{m-1}u_m\pmod{M}.$$
كما أن مرورًا خطيًا آخر يعطي \(P=n!\bmod M\). وبعد إنهاء هذه التهيئة الخطية يصبح الجزء المعاملي \(P\,v_m\,u_{n-m}\) متاحًا لكل حد في \(O(1)\) زمنًا.
العامل المتبقي في كل حد مفهرس هو
$$(m-1)^m\pmod{M}.$$
وتحسبه التطبيقات باستخدام الرفع الثنائي للأس. فالتربيع المتكرر يخفض كلفة حساب قوة واحدة من زمن خطي في \(m\) إلى زمن لوغاريتمي في \(m\)، ولذلك يحتاج كل حد إلى عدد ثابت من الضربات المعيارية إضافة إلى عملية أس واحدة من رتبة \(O(\log m)\).
ولهذا يبقى الأسلوب عمليًا حتى عندما تكون قيمة \(n\) كبيرة جدًا: الجزء المكلف هو سلسلة نداءات القوى السريعة، لا معامل المضروب نفسه.
عند \(n=8\) يكون الحد الرئيسي
$$Z(8)=8\cdot 7\cdot 6^7=15676416.$$
ويمتد المجموع على \(m=2,3,4,5,6\). أما المعاملات والمساهمات المقابلة فهي
$$\frac{8!}{2!(8-2)}=3360,\qquad 3360\cdot 1^2=3360,$$
$$\frac{8!}{3!(8-3)}=1344,\qquad 1344\cdot 2^3=10752,$$
$$\frac{8!}{4!(8-4)}=420,\qquad 420\cdot 3^4=34020,$$
$$\frac{8!}{5!(8-5)}=112,\qquad 112\cdot 4^5=114688,$$
$$\frac{8!}{6!(8-6)}=28,\qquad 28\cdot 5^6=437500.$$
وبجمع جميع الأجزاء نحصل على
$$F(8)=15676416+3360+10752+34020+114688+437500=16276736.$$
وفي هذا المثال يبقى المجموع أصغر من \(M\)، لذلك يتطابق الجواب المعياري مع الجواب الصحيح كعدد صحيح عادي. وهذا يطابق تمامًا نقطة التحقق المستخدمة في التنفيذ.
تتبع تطبيقات C++ وPython وJava الخطة الحسابية نفسها. فهي تبدأ بالحساب المسبق للمعكوسات المعيارية حتى \(n\)، ثم تحسب \(n!\bmod M\)، ثم تبني جدولًا بادئيًا لمعكوسات المضروب. وبعد ذلك تحسب الحد الرئيسي \(n(n-1)(n-2)^{n-1}\) مرة واحدة.
بعدها تدور حلقة على \(m=2,\dots,n-2\). ولكل قيمة من \(m\)، يُركَّب معامل المضروب من الجداول المحسوبة مسبقًا، وتُحسب القوة \((m-1)^m\) بالرفع الثنائي للأس، ثم تُضاف المساهمة بترديد \(M\). كما أن تنفيذ C++ يقسم مجال \(m\) إلى مقاطع ويجمع المجاميع الجزئية من عدة عمّال، بينما تنفذ نسختا Python وJava الصيغة نفسها بشكل متسلسل.
الحساب المسبق للمعكوسات وقيمة المضروب وجدول معكوسات المضروب يحتاج إلى \(O(n)\) زمنًا و\(O(n)\) ذاكرة. ويحتوي المجموع الرئيسي على \(n-3\) حدود، ويتطلب كل حد عملية رفع معياري للأس بكلفة \(O(\log m)\). لذلك يكون التعقيد الزمني الكلي \(O(n\log n)\)، مع استهلاك ذاكرة مقداره \(O(n)\). وفي نسخة C++ متعددة الخيوط تبقى كمية العمل الحسابي الكلية نفسها، لكن زمن التنفيذ الفعلي ينخفض لأن مجال الجمع يُوزَّع على عدة عمّال.