Let \(m=100\) and \(n=1+2+\cdots+m=5050\). The permutation in the problem is obtained by starting with a block permutation whose disjoint cycles have lengths \(1,2,\dots,100\), and then relabeling the points by a bijection induced by multiplication by \(10^9+7\) modulo \(5050\). The task is to sum the 1-indexed lexicographic ranks of the first \(100!\) powers of that permutation and report the result modulo \(10^9+7\).
A direct simulation would require handling \(100!\) different powers of a permutation on 5050 symbols, which is completely infeasible. The key observation is that lexicographic rank can be written as a weighted inversion count, and powers of a permutation behave periodically on each pair of cycles.
Write the final permutation as \(\rho\), in one-line notation \((\rho(1),\rho(2),\dots,\rho(n))\). The entire solution comes from combining cycle structure, Lehmer-code weights, and a counting argument on pairs of cycles.
The base permutation is a disjoint union of consecutive cycles of lengths \(1,2,\dots,100\). Conjugating by a relabeling permutation changes the labels written inside the cycles, but it does not change any cycle length. Therefore \(\rho\) still has exactly one cycle of each length from 1 through 100.
This immediately implies that the order of \(\rho\) divides \(100!\), because every cycle length divides \(100!\). So when we sum over the first \(100!\) powers, every cycle has completed an integer number of full turns, and every pair of cycles has completed an integer number of joint periods.
For any permutation \(\alpha\) on \(\{1,\dots,n\}\), its 1-indexed lexicographic rank is
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
where
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
This is exactly the factorial-number-system or Lehmer-code expansion. Summing over the first \(100!\) powers of \(\rho\) gives
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
with
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
So the whole problem reduces to one question: for each pair of positions \(i\lt j\), how often do their images appear in reversed numerical order as the exponent runs?
Suppose \(i\) belongs to a cycle
$$C=(c_0,c_1,\dots,c_{s-1}),$$
and \(j\) belongs to a cycle
$$D=(d_0,d_1,\dots,d_{t-1}).$$
If \(i\) starts at position \(u\) in \(C\) and \(j\) starts at position \(v\) in \(D\), then after \(k\) applications of \(\rho\) we have
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}.$$
Now define
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}.$$
The ordered pair of cycle positions repeats every \(L\) steps. Since \(L\mid 100!\), it is enough to count favorable exponents in one \(L\)-step period and then multiply by \(100!/L\).
The relative phase between the two cycles matters only modulo \(g\). Set
$$\delta\equiv v-u \pmod g.$$
Partition each cycle according to position modulo \(g\):
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
During one full \(L\)-step period, the pair \((\rho^k(i),\rho^k(j))\) visits exactly the pairs of positions whose residues differ by \(\delta\). Each admissible position pair occurs once. Therefore the number of favorable exponents in one period is
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}.$$
Hence
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
The comparison problem is now finite and static: sort each residue class once, and for every phase \(\delta\) count how many elements of the second class are smaller than each element of the first.
Substituting the cycle-pair count into the weighted inversion formula yields
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
Here \(C(i)\) and \(C(j)\) are the cycles containing \(i\) and \(j\), and \(\delta(i,j)\) is the phase difference of their positions modulo the relevant gcd. This is exactly the quantity accumulated by the implementations.
Take two sample cycles
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
Then \(s=4\), \(t=6\), so
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
Split them by position parity:
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}.$$
After sorting,
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
If the starting phase difference is \(\delta=1\), then
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
So there are exactly 4 favorable exponents in each 12-step joint period. Across the first \(100!\) powers this becomes
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}.$$
This miniature example is the same mechanism used for every pair of indices in the full problem.
The C++, Python, and Java implementations build the relabeled permutation, decompose it into cycles, and record for every value both its cycle index and its position inside that cycle. They also precompute the factorial weights \((n-i)!\) used by the lexicographic-rank formula, together with \(100! \bmod (10^9+7)\).
For each ordered pair of cycles, the implementation computes \(g=\gcd(s,t)\), \(L=\operatorname{lcm}(s,t)\), and the phase tables \(Q_\delta(C,D)\) for \(\delta=0,1,\dots,g-1\). Because the modulus is prime and \(L<10^9+7\), the factor \(100!/L\) is represented modulo \(10^9+7\) as \(100!\cdot L^{-1}\).
After that preprocessing, the final accumulation is straightforward: for each \(i<j\), look up the two cycles, recover the correct phase \(\delta\), read the precomputed table entry, multiply by \((n-i)!\) and by the modular version of \(100!/L\), and add the result to the running sum. The C++ and Java implementations parallelize this last double loop across several threads; the Python implementation performs the same arithmetic serially.
The permutation size is fixed at \(n=5050\), so the dominant cost is the sweep over all \(\binom{5050}{2}\) index pairs in the final accumulation. In asymptotic terms, if one writes \(n=1+2+\cdots+m=\Theta(m^2)\), then the main phase is \(O(n^2)=O(m^4)\).
The cycle-pair preprocessing is smaller: there are only 100 cycles, and each pair of cycles needs a table of size \(\gcd(s,t)\) plus sorted residue classes. Memory usage is \(O(n)\) for the permutation metadata and factorial weights, plus the cycle-pair tables, which are much smaller than the final pair sweep. In practice the algorithm is fast because it replaces gigantic exponentiation over \(100!\) powers by a single precompute-and-count pass.
Setze \(m=100\) und \(n=1+2+\cdots+m=5050\). Die gesuchte Permutation entsteht, indem man zuerst eine Blockpermutation mit disjunkten Zyklen der Längen \(1,2,\dots,100\) nimmt und anschließend die Elemente durch eine von der Multiplikation mit \(10^9+7\) modulo \(5050\) induzierte Bijektion umbenennt. Gesucht ist die Summe der 1-indizierten lexikographischen Ränge der ersten \(100!\) Potenzen dieser Permutation modulo \(10^9+7\).
Direkte Simulation ist völlig ausgeschlossen: Man kann weder \(100!\) Potenzen explizit erzeugen noch für jede davon eine Permutation auf 5050 Symbolen vollständig auswerten. Die Lösung nutzt stattdessen die Zyklusstruktur, die Lehmer-Code-Darstellung des lexikographischen Rangs und die Periodizität von Potenzen auf Zykluspaaren.
Schreibe die endgültige Permutation als \(\rho\) in einzeiliger Notation \((\rho(1),\rho(2),\dots,\rho(n))\). Die gesamte Herleitung verbindet Zykluszerlegung, faktoriell gewichtete Inversionszahlen und eine statische Zählung auf Paaren von Zyklen.
Die Ausgangspermutation ist eine disjunkte Vereinigung aufeinanderfolgender Zyklen mit Längen \(1,2,\dots,100\). Eine Konjugation durch eine Umbenennung ändert zwar die Beschriftungen innerhalb der Zyklen, aber keine Zykluslänge. Deshalb besitzt \(\rho\) weiterhin genau einen Zyklus jeder Länge von 1 bis 100.
Daraus folgt sofort, dass die Ordnung von \(\rho\) ein Teiler von \(100!\) ist, denn jede Zykluslänge teilt \(100!\). Wenn wir also über die ersten \(100!\) Potenzen summieren, durchläuft jeder Zyklus eine ganzzahlige Anzahl vollständiger Umläufe, und jedes Zykluspaar durchläuft eine ganzzahlige Anzahl gemeinsamer Perioden.
Für eine beliebige Permutation \(\alpha\) auf \(\{1,\dots,n\}\) gilt für den 1-indizierten lexikographischen Rang
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
wobei
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
Das ist genau die Darstellung im Fakultätenzahlensystem, also der Lehmer-Code. Summiert man über die ersten \(100!\) Potenzen von \(\rho\), erhält man
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
mit
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
Damit ist das globale Problem auf eine präzise Frage reduziert: Wie oft erscheint für ein festes Paar \(i\lt j\) unter den Potenzen die Bildfolge in umgekehrter numerischer Reihenfolge?
Angenommen, \(i\) liegt im Zyklus
$$C=(c_0,c_1,\dots,c_{s-1}),$$
und \(j\) liegt im Zyklus
$$D=(d_0,d_1,\dots,d_{t-1}).$$
Befindet sich \(i\) an Startposition \(u\) in \(C\) und \(j\) an Startposition \(v\) in \(D\), dann gilt nach \(k\) Anwendungen von \(\rho\)
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}.$$
Definiere nun
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}.$$
Das geordnete Paar von Zykluspositionen wiederholt sich alle \(L\) Schritte. Da \(L\mid 100!\), genügt es, die günstigen Exponenten in einer einzigen \(L\)-Periode zu zählen und anschließend mit \(100!/L\) zu multiplizieren.
Die relative Phase der beiden Zyklen ist nur modulo \(g\) relevant. Setze
$$\delta\equiv v-u \pmod g.$$
Teile jeden Zyklus nach Positionen modulo \(g\) auf:
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
Während einer vollständigen \(L\)-Periode besucht das Paar \((\rho^k(i),\rho^k(j))\) genau diejenigen Positionspaare, deren Restklassen sich um \(\delta\) unterscheiden. Jedes zulässige Positionspaar tritt genau einmal auf. Also ist die Anzahl günstiger Exponenten in einer Periode
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}.$$
Damit folgt
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
Das dynamische Problem wird dadurch zu einer endlichen, statischen Vergleichsaufgabe: Sortiere jede Restklasse einmal und zähle dann für jede Phase \(\delta\), wie viele Elemente der zweiten Klasse kleiner als die Elemente der ersten Klasse sind.
Setzt man die Zykluszählung in die gewichtete Inversionsformel ein, so erhält man
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
Hier bezeichnen \(C(i)\) und \(C(j)\) die Zyklen, die \(i\) bzw. \(j\) enthalten, und \(\delta(i,j)\) ist die Phasendifferenz ihrer Positionen modulo des passenden ggT. Genau diese Größe wird in den Implementierungen akkumuliert.
Betrachte die Beispielzyklen
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
Dann sind \(s=4\), \(t=6\), also
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
Nach Positionsparität zerlegt:
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}.$$
Sortiert ergibt das
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
Für die Startphasendifferenz \(\delta=1\) gilt
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
Es gibt also genau 4 günstige Exponenten in jeder gemeinsamen 12er-Periode. Über die ersten \(100!\) Potenzen ergibt das
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}.$$
Genau dieses Skalierungsprinzip wird für jedes Indexpaar im Gesamtproblem verwendet.
Die C++-, Python- und Java-Implementierungen konstruieren zunächst die relabelte Permutation, zerlegen sie in Zyklen und speichern für jeden Wert sowohl die Zyklusnummer als auch die Position innerhalb dieses Zyklus. Zusätzlich werden die Fakultätsgewichte \((n-i)!\) aus der Lehmer-Code-Formel sowie \(100! \bmod (10^9+7)\) vorab berechnet.
Für jedes geordnete Zykluspaar berechnet die Implementierung \(g=\gcd(s,t)\), \(L=\operatorname{lcm}(s,t)\) und die Phasentabellen \(Q_\delta(C,D)\) für \(\delta=0,1,\dots,g-1\). Da der Modul eine Primzahl ist und \(L<10^9+7\) gilt, wird der Faktor \(100!/L\) modulo \(10^9+7\) als \(100!\cdot L^{-1}\) dargestellt.
Nach dieser Vorverarbeitung ist die Endsumme direkt: Für jedes \(i<j\) werden die beiden Zyklen gefunden, die korrekte Phase \(\delta\) rekonstruiert, der vorberechnete Tabellenwert gelesen und mit \((n-i)!\) sowie der modularen Version von \(100!/L\) multipliziert. Die C++- und Java-Versionen parallelisieren die abschließende Doppelschleife über mehrere Threads; die Python-Version führt dieselbe Rechnung seriell aus.
Die Permutationsgröße ist fest \(n=5050\), daher dominiert der Durchlauf über alle \(\binom{5050}{2}\) Indexpaaren in der Endakkumulation. Asymptotisch gilt bei \(n=1+2+\cdots+m=\Theta(m^2)\): Die Hauptphase kostet \(O(n^2)=O(m^4)\).
Die Vorberechnung über Zykluspaare ist kleiner: Es gibt nur 100 Zyklen, und jedes Paar benötigt eine Tabelle der Größe \(\gcd(s,t)\) sowie sortierte Restklassen. Der Speicherbedarf ist \(O(n)\) für Permutationsmetadaten und Fakultätsgewichte plus die deutlich kleineren Tabellen für Zykluspaare. Praktisch ist das Verfahren schnell, weil es die gigantische Iteration über \(100!\) Potenzen durch einen einmaligen Vorberechnen-und-Zählen-Schritt ersetzt.
\(m=100\) ve \(n=1+2+\cdots+m=5050\) olsun. Sorudaki permütasyon, önce uzunlukları \(1,2,\dots,100\) olan ayrık çevrimlerden oluşan bir blok permütasyonu kurup sonra elemanları \(5050\) modunda \(10^9+7\) ile çarpmadan doğan bir bijeksiyonla yeniden etiketleyerek elde edilir. İstenen şey, bu permütasyonun ilk \(100!\) kuvvetinin 1-indeksli leksikografik sıralarını toplayıp sonucu \(10^9+7\) modunda vermektir.
Doğrudan simülasyon tamamen imkansızdır; ne \(100!\) farklı kuvvet açıkça üretilebilir ne de bunların her biri için 5050 elemanlı bir permütasyon baştan sona işlenebilir. Çözüm, bunun yerine çevrim yapısını, Lehmer kodunu ve bir çevrim çifti üzerindeki periyodik davranışı kullanır.
Son permütasyonu \(\rho\) ile gösterelim; tek satırlı yazımı \((\rho(1),\rho(2),\dots,\rho(n))\) olsun. Tüm çözüm, çevrim ayrışımı ile faktöriyel ağırlıklı terslik sayımını birleştiren tek bir çerçeve içinde kuruluyor.
Başlangıçtaki permütasyon, uzunlukları \(1,2,\dots,100\) olan ardışık çevrimlerin ayrık birleşimidir. Bir yeniden etiketleme ile yapılan eşleniklik, çevrimlerin içindeki değerleri değiştirir ama çevrim uzunluklarını değiştirmez. Bu yüzden \(\rho\) hâlâ 1'den 100'e kadar her uzunluktan tam bir çevrim içerir.
Buradan \(\rho\)'nun mertebesinin \(100!\)'i böldüğü hemen çıkar; çünkü her çevrim uzunluğu \(100!\)'i böler. Dolayısıyla ilk \(100!\) kuvvet üzerinde toplama yaptığımızda her çevrim tam sayıda tur atmış olur ve her çevrim çifti ortak periyodunu tam sayıda tekrar eder.
\(\{1,\dots,n\}\) üzerindeki herhangi bir \(\alpha\) permütasyonu için 1-indeksli leksikografik sıra
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
şeklindedir; burada
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
Bu, faktöriyel sayı sistemi ya da Lehmer kodu formülüdür. Bunu \(\rho\)'nun ilk \(100!\) kuvveti üzerinde toplarsak
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
elde edilir; burada
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
Yani asıl problem şuna dönüşür: sabit bir \(i<j\) çifti için, üs değiştikçe görüntüler kaç kez ters sayısal sıraya düşer?
Diyelim ki \(i\),
$$C=(c_0,c_1,\dots,c_{s-1})$$
çevriminde, \(j\) ise
$$D=(d_0,d_1,\dots,d_{t-1})$$
çevriminde olsun. \(i\), \(C\) içinde \(u\) konumundan; \(j\) de \(D\) içinde \(v\) konumundan başlıyorsa, \(\rho\)'nun \(k\) kez uygulanmasından sonra
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}$$
olur. Şimdi
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}$$
tanımlarını yapalım. Konum çiftinin düzeni her \(L\) adımda bir tekrar eder. \(L\mid 100!\) olduğundan, uygun üsleri bir tek \(L\) adımlık periyotta sayıp sonra \(100!/L\) ile çarpmak yeterlidir.
İki çevrim arasındaki göreli faz yalnızca \(g\) modunda önemlidir. O halde
$$\delta\equiv v-u \pmod g$$
olsun. Her çevrimi, konumların \(g\) modundaki artık sınıflarına göre parçalayalım:
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
Bir tam \(L\)-adımlık ortak periyot boyunca \((\rho^k(i),\rho^k(j))\) çifti, artık farkı \(\delta\) olan tam olarak bütün konum çiftlerini birer kez ziyaret eder. Bu yüzden bir periyottaki uygun üs sayısı
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}$$
olur. Sonuç olarak
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
Böylece hareketli bir kuvvet problemi, tek seferlik sıralama ve karşılaştırma yapılan sonlu bir tablo problemine dönüşür.
Çevrim çifti sayımını ağırlıklı terslik formülüne yerleştirince
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
elde edilir. Burada \(C(i)\) ve \(C(j)\), sırasıyla \(i\) ve \(j\)'yi içeren çevrimleri; \(\delta(i,j)\) ise bu iki konumun uygun EBOB modundaki faz farkını gösterir. Uygulamalar tam olarak bu toplamı hesaplar.
Şu örnek çevrimleri alalım:
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
Burada \(s=4\), \(t=6\) olduğundan
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
Konum paritesine göre ayırırsak
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}$$
elde edilir. Sıralandıktan sonra
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
Başlangıç faz farkı \(\delta=1\) ise
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
Demek ki ortak 12 adımlık periyotta tam 4 uygun üs vardır. İlk \(100!\) kuvvette bu desen \(100!/12\) kez tekrarlandığı için
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}$$
olur. Tam programda yapılan şey, bu hesabı bütün indeks çiftlerine yaymaktır.
C++, Python ve Java uygulamaları önce yeniden etiketlenmiş permütasyonu kurar, onu çevrimlere ayırır ve her değer için hem ait olduğu çevrimi hem de çevrim içindeki konumunu kaydeder. Ayrıca leksikografik sıra formülünde kullanılan \((n-i)!\) ağırlıkları ile \(100! \bmod (10^9+7)\) önceden hesaplanır.
Sonra her sıralı çevrim çifti için \(g=\gcd(s,t)\), \(L=\operatorname{lcm}(s,t)\) ve \(\delta=0,1,\dots,g-1\) fazlarının her biri için \(Q_\delta(C,D)\) tablosu hazırlanır. Modül asal olduğu ve \(L<10^9+7\) olduğu için \(100!/L\) katsayısı modüler olarak \(100!\cdot L^{-1}\) biçiminde temsil edilir.
Bu ön işlem bittikten sonra son toplama basittir: her \(i<j\) için iki çevrim bulunur, doğru faz farkı \(\delta\) elde edilir, hazır tablodan ilgili değer okunur, \((n-i)!\) ve \(100!/L\)'nin modüler karşılığıyla çarpılır ve sonuca eklenir. C++ ve Java sürümleri bu son çift döngüsünü birkaç iş parçacığına bölerek hızlandırır; Python sürümü aynı matematiği tek iş parçacığında uygular.
Permütasyon boyutu sabit olarak \(n=5050\) olduğundan baskın maliyet, son aşamadaki \(\binom{5050}{2}\) indeks çifti üzerinden geçmektir. Asimptotik olarak \(n=1+2+\cdots+m=\Theta(m^2)\) yazılırsa ana fazın maliyeti \(O(n^2)=O(m^4)\) olur.
Çevrim çifti ön hesaplaması daha küçüktür: yalnızca 100 çevrim vardır ve her çift için \(\gcd(s,t)\) boyutunda bir tablo ile sıralanmış artık sınıfları gerekir. Bellek kullanımı, permütasyon metaverisi ve faktöriyel ağırlıklar için \(O(n)\), buna ek olarak da çok daha küçük çevrim-çifti tablolarıdır. Bu yöntem, \(100!\) kuvveti tek tek dolaşmak yerine tek bir ön hesaplama ve sayım adımına geçtiği için pratiktir.
Sea \(m=100\) y \(n=1+2+\cdots+m=5050\). La permutación del problema se construye tomando primero una permutación por bloques cuyos ciclos disjuntos tienen longitudes \(1,2,\dots,100\), y luego reetiquetando los elementos mediante una biyección inducida por multiplicar por \(10^9+7\) módulo \(5050\). Hay que sumar los rangos lexicográficos, indexados desde 1, de las primeras \(100!\) potencias de esa permutación y dar el resultado módulo \(10^9+7\).
Simularlo de forma directa es imposible: no se pueden generar explícitamente \(100!\) potencias de una permutación sobre 5050 símbolos. La solución usa en cambio la estructura de ciclos, la fórmula del código de Lehmer para el rango lexicográfico y la periodicidad del comportamiento de una potencia sobre cada par de ciclos.
Denotemos por \(\rho\) la permutación final, escrita en notación de una línea como \((\rho(1),\rho(2),\dots,\rho(n))\). Toda la derivación combina la descomposición en ciclos con un conteo de inversiones ponderadas y una reducción estática a pares de ciclos.
La permutación base es una unión disjunta de ciclos consecutivos de longitudes \(1,2,\dots,100\). Conjugar por una permutación de reetiquetado cambia los valores escritos dentro de cada ciclo, pero no cambia ninguna longitud de ciclo. Por lo tanto, \(\rho\) sigue teniendo exactamente un ciclo de cada longitud entre 1 y 100.
Esto implica de inmediato que el orden de \(\rho\) divide a \(100!\), porque cada longitud de ciclo divide a \(100!\). Así, al sumar sobre las primeras \(100!\) potencias, cada ciclo completa un número entero de vueltas y cada par de ciclos completa un número entero de periodos conjuntos.
Para cualquier permutación \(\alpha\) sobre \(\{1,\dots,n\}\), su rango lexicográfico indexado desde 1 es
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
donde
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
Esta es exactamente la expansión del código de Lehmer. Al sumar sobre las primeras \(100!\) potencias de \(\rho\) obtenemos
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
con
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
Así, el problema global se convierte en contar, para cada par fijo \(i<j\), cuántas veces sus imágenes aparecen en orden numérico invertido cuando el exponente recorre el intervalo completo.
Supongamos que \(i\) pertenece al ciclo
$$C=(c_0,c_1,\dots,c_{s-1}),$$
y que \(j\) pertenece al ciclo
$$D=(d_0,d_1,\dots,d_{t-1}).$$
Si la posición inicial de \(i\) dentro de \(C\) es \(u\) y la de \(j\) dentro de \(D\) es \(v\), entonces después de aplicar \(\rho\) \(k\) veces se cumple
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}.$$
Definimos ahora
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}.$$
El par ordenado de posiciones se repite cada \(L\) pasos. Como \(L\mid 100!\), basta contar los exponentes favorables en un solo periodo de longitud \(L\) y luego multiplicar por \(100!/L\).
La fase relativa entre los dos ciclos solo importa módulo \(g\). Definimos
$$\delta\equiv v-u \pmod g.$$
Particionamos cada ciclo por la posición módulo \(g\):
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
Durante un periodo conjunto completo de longitud \(L\), el par \((\rho^k(i),\rho^k(j))\) recorre exactamente los pares de posiciones cuyas clases de residuos difieren en \(\delta\). Cada par admisible aparece una sola vez. Por tanto, el número de exponentes favorables en un periodo es
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}.$$
En consecuencia,
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
El problema dinámico se convierte así en un problema finito de conteo: ordenar una vez cada clase de residuos y luego medir, para cada fase \(\delta\), cuántos valores de la segunda clase son menores que los de la primera.
Sustituyendo el conteo del par de ciclos en la fórmula de inversiones ponderadas, obtenemos
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
Aquí \(C(i)\) y \(C(j)\) representan los ciclos que contienen a \(i\) y \(j\), mientras que \(\delta(i,j)\) es la diferencia de fase de sus posiciones módulo el mcd correspondiente. Esa es exactamente la cantidad que acumulan las implementaciones.
Tomemos los ciclos de ejemplo
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
Entonces \(s=4\), \(t=6\), y por tanto
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
Separando por paridad de la posición:
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}.$$
Tras ordenar:
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
Si la diferencia de fase inicial es \(\delta=1\), entonces
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
Eso significa que en cada periodo conjunto de 12 pasos hay exactamente 4 exponentes favorables. En las primeras \(100!\) potencias, el patrón se repite \(100!/12\) veces, así que
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}.$$
Este ejemplo pequeño reproduce exactamente el mecanismo que se usa en todo el cálculo real.
Las implementaciones en C++, Python y Java construyen la permutación reetiquetada, la descomponen en ciclos y guardan, para cada valor, tanto el identificador del ciclo como su posición dentro de dicho ciclo. También precomputan los pesos factoriales \((n-i)!\) que aparecen en la fórmula del rango lexicográfico, junto con \(100! \bmod (10^9+7)\).
Para cada par ordenado de ciclos, la implementación calcula \(g=\gcd(s,t)\), \(L=\operatorname{lcm}(s,t)\) y la tabla de fases \(Q_\delta(C,D)\) para \(\delta=0,1,\dots,g-1\). Como el módulo es primo y \(L<10^9+7\), el factor \(100!/L\) se representa módulo \(10^9+7\) como \(100!\cdot L^{-1}\).
Después de esa fase previa, la acumulación final es directa: para cada \(i<j\), se localizan los dos ciclos, se recupera la fase correcta \(\delta\), se lee la entrada ya calculada de la tabla, se multiplica por \((n-i)!\) y por la versión modular de \(100!/L\), y se añade al total. Las versiones en C++ y Java paralelizan este último doble bucle; la versión en Python hace la misma aritmética en serie.
El tamaño de la permutación es fijo, \(n=5050\), así que el costo dominante es el recorrido de todos los \(\binom{5050}{2}\) pares de índices en la acumulación final. En términos asintóticos, si se escribe \(n=1+2+\cdots+m=\Theta(m^2)\), entonces la fase principal cuesta \(O(n^2)=O(m^4)\).
La precalculación por pares de ciclos es menor: solo hay 100 ciclos, y cada par necesita una tabla de tamaño \(\gcd(s,t)\) y algunas clases de residuos ordenadas. El uso de memoria es \(O(n)\) para los metadatos de la permutación y los pesos factoriales, más las tablas de pares de ciclos, que son mucho más pequeñas que el barrido final. En la práctica, el método es eficiente porque sustituye una iteración imposible sobre \(100!\) potencias por una sola pasada de precomputación y conteo.
设 \(m=100\)，并令 \(n=1+2+\cdots+m=5050\)。题目中的置换先从一个按区块拼接的基础置换开始，这个基础置换恰好由长度为 \(1,2,\dots,100\) 的互不相交循环组成；然后再通过一个由“模 \(5050\) 乘以 \(10^9+7\)”诱导出的双射重新标号。要求的是这个置换前 \(100!\) 个幂的 1 起始字典序排名之和，并把结果对 \(10^9+7\) 取模。
如果直接暴力做，就意味着要面对 \(100!\) 个不同的幂次，而且每个幂次都是 5050 个元素上的一个置换，这显然不可能。实现真正利用的是三件事：循环分解、字典序排名的 Lehmer 码公式，以及置换幂在每一对循环上的周期性。
把最终得到的置换记为 \(\rho\)，其单行表示为 \((\rho(1),\rho(2),\dots,\rho(n))\)。整个推导就是把“对所有幂求字典序排名之和”改写成“对所有下标对做一次静态计数”。
基础置换由连续区间上的若干独立循环组成，循环长度依次为 \(1,2,\dots,100\)。随后做的只是一次重新标号，也就是群论中的共轭。共轭会改变循环里写着哪些数字，但不会改变循环长度。因此最终置换 \(\rho\) 仍然恰好拥有长度 1 到 100 各一个循环。
这一点立刻带来第一个关键结论：\(\rho\) 的阶一定整除 \(100!\)，因为每个循环长度都整除 \(100!\)。所以当我们把幂次从 1 加到 \(100!\) 时，每个循环都完整地转过了整数圈，每一对循环也完整地走过了若干个联合周期。
对于 \(\{1,\dots,n\}\) 上任意一个置换 \(\alpha\)，它的 1 起始字典序排名满足
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
其中
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
这正是 Lehmer 码，也可以看成阶乘进位制展开。把它对 \(\rho\) 的前 \(100!\) 个幂求和，得到
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
其中
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
这样一来，原题就被压缩成一个更具体的问题：对每个固定的 \(i<j\)，当幂次变化时，\(\rho^k(i)\) 和 \(\rho^k(j)\) 有多少次会出现“后者数值更小”的情况。
设 \(i\) 位于循环
$$C=(c_0,c_1,\dots,c_{s-1}),$$
而 \(j\) 位于循环
$$D=(d_0,d_1,\dots,d_{t-1}).$$
如果 \(i\) 在 \(C\) 中的起始位置是 \(u\)，\(j\) 在 \(D\) 中的起始位置是 \(v\)，那么施加 \(k\) 次置换之后，
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}.$$
定义
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}.$$
这两个位置组成的有序对每隔 \(L\) 步就会完全重复一次。由于 \(L\mid 100!\)，所以只要统计一个长度为 \(L\) 的完整周期里有多少个“有利”指数，再乘上 \(100!/L\)，就得到了全部 \(100!\) 个幂中的贡献次数。
两个循环之间真正起作用的不是完整位置差，而是它模 \(g\) 的值。记
$$\delta\equiv v-u \pmod g.$$
接着按位置对 \(g\) 取模来拆分两个循环：
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
在一个完整的联合周期中，\((\rho^k(i),\rho^k(j))\) 恰好会遍历所有满足“两个位置的剩余类差为 \(\delta\)”的配对，而且每种合法配对只出现一次。因此，一个周期里满足 \(\rho^k(j)<\rho^k(i)\) 的指数个数正好是
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}.$$
于是
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
这一步很关键，因为原来随 \(k\) 变化的动态问题被彻底变成了一个静态比较问题：把每个剩余类内部排好序，然后数一数第二个集合里有多少元素小于第一个集合里的元素。
把循环对的计数代回带权逆序数公式，就得到
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
这里 \(C(i)\) 和 \(C(j)\) 分别表示包含 \(i\) 和 \(j\) 的循环，\(\delta(i,j)\) 是它们在相应 \(\gcd\) 模数下的位置相位差。实现程序累加的正是这一个公式，没有任何多余的暴力幂运算。
考虑下面这两个示例循环：
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
此时 \(s=4\)、\(t=6\)，因此
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
按位置奇偶拆分后得到
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}.$$
把它们分别排序后就是
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
如果初始相位差是 \(\delta=1\)，那么
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
也就是说，在每个长度为 12 的联合周期里，恰好有 4 个指数满足“来自 \(D\) 的值小于来自 \(C\) 的值”。扩展到前 \(100!\) 个幂，这个模式重复了 \(100!/12\) 次，因此
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}.$$
真实题目里做的事情与此完全一致，只是把这套计算同时应用到所有下标对上。
C++、Python 和 Java 三个实现都会先构造重新标号后的置换，再做循环分解，并为每个值记录它属于哪个循环以及在循环中的位置。同时还会预先计算字典序排名公式中需要的权重 \((n-i)!\)，以及 \(100! \bmod (10^9+7)\)。
对于每一对有序循环，实现会计算 \(g=\gcd(s,t)\)、\(L=\operatorname{lcm}(s,t)\)，并为 \(\delta=0,1,\dots,g-1\) 的所有相位准备好 \(Q_\delta(C,D)\) 表。由于模数是素数，且这里的 \(L<10^9+7\)，所以 \(100!/L\) 可以在模意义下写成 \(100!\cdot L^{-1}\)。
有了这些预处理以后，最后的累加阶段就只是查表：对每个 \(i<j\)，找到两个循环，恢复正确的相位差 \(\delta\)，取出对应的表项，再乘上 \((n-i)!\) 与 \(100!/L\) 的模表示并加入答案。C++ 与 Java 版本把最后这个双层循环分配到多个线程上，Python 版本则按相同的数学逻辑串行完成。
置换规模固定为 \(n=5050\)，因此主导成本是最后那一步遍历所有 \(\binom{5050}{2}\) 个下标对。若把 \(n\) 写成 \(n=1+2+\cdots+m=\Theta(m^2)\)，则主阶段的渐近复杂度是 \(O(n^2)=O(m^4)\)。
循环对预处理要小得多：总共只有 100 个循环，每对循环只需要一个大小为 \(\gcd(s,t)\) 的表以及若干排好序的剩余类。内存方面，置换元数据和阶乘权重占 \(O(n)\)，再加上远小于主遍历规模的循环对表。它之所以高效，是因为它把“不可能枚举的 \(100!\) 个幂”压缩成了“一次预处理加一次计数”。
Положим \(m=100\) и \(n=1+2+\cdots+m=5050\). Перестановка в задаче строится так: сначала берется блочная перестановка, состоящая из непересекающихся циклов длины \(1,2,\dots,100\), а затем элементы переименовываются с помощью биекции, индуцированной умножением на \(10^9+7\) по модулю \(5050\). Требуется сложить 1-индексированные лексикографические ранги первых \(100!\) степеней этой перестановки и вернуть результат по модулю \(10^9+7\).
Прямое моделирование здесь невозможно: нельзя явно построить \(100!\) степеней перестановки на 5050 элементах. Поэтому решение опирается на структуру циклов, формулу Лемера для лексикографического ранга и периодичность поведения степеней на каждой паре циклов.
Обозначим итоговую перестановку через \(\rho\), в однострочной записи \((\rho(1),\rho(2),\dots,\rho(n))\). Вся идея состоит в том, чтобы переписать сумму рангов по степеням как сумму статических вкладов от пар индексов.
Исходная перестановка является дизъюнктным объединением последовательных циклов длины \(1,2,\dots,100\). Сопряжение перестановкой-переименованием меняет сами подписи внутри циклов, но не меняет длины циклов. Следовательно, \(\rho\) по-прежнему содержит ровно один цикл каждой длины от 1 до 100.
Отсюда сразу следует, что порядок \(\rho\) делит \(100!\), потому что каждая длина цикла делит \(100!\). Значит, при суммировании по первым \(100!\) степеням каждый цикл делает целое число оборотов, а каждая пара циклов проходит целое число общих периодов.
Для любой перестановки \(\alpha\) на \(\{1,\dots,n\}\) ее 1-индексированный лексикографический ранг равен
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
где
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
Это и есть стандартная запись через код Лемера. Если просуммировать по первым \(100!\) степеням \(\rho\), получим
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
где
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
Итак, глобальная задача сводится к локальному вопросу: для фиксированной пары \(i<j\) сколько раз значения \(\rho^k(i)\) и \(\rho^k(j)\) оказываются в обратном числовом порядке.
Пусть \(i\) принадлежит циклу
$$C=(c_0,c_1,\dots,c_{s-1}),$$
а \(j\) принадлежит циклу
$$D=(d_0,d_1,\dots,d_{t-1}).$$
Если стартовая позиция \(i\) внутри \(C\) равна \(u\), а стартовая позиция \(j\) внутри \(D\) равна \(v\), то после \(k\) применений \(\rho\)
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}.$$
Теперь введем
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}.$$
Упорядоченная пара позиций повторяется через каждые \(L\) шагов. Поскольку \(L\mid 100!\), достаточно посчитать благоприятные показатели в одном полном периоде длины \(L\), а затем умножить на \(100!/L\).
Относительная фаза двух циклов важна только по модулю \(g\). Обозначим
$$\delta\equiv v-u \pmod g.$$
Разобьем каждый цикл по позициям modulo \(g\):
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
За один полный совместный период длины \(L\) пара \((\rho^k(i),\rho^k(j))\) пробегает ровно те пары позиций, у которых разность классов вычетов равна \(\delta\). Каждая допустимая пара позиций встречается ровно один раз. Поэтому число благоприятных показателей в одном периоде равно
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}.$$
Следовательно,
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
Тем самым задача о степенях перестановки превращается в конечную статическую задачу сравнения: нужно один раз отсортировать каждый класс вычетов и затем для каждой фазы \(\delta\) посчитать, сколько элементов второго класса меньше элементов первого.
Подставляя подсчет для пары циклов в формулу взвешенных инверсий, получаем
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
Здесь \(C(i)\) и \(C(j)\) обозначают циклы, содержащие \(i\) и \(j\), а \(\delta(i,j)\) есть сдвиг фаз их позиций по модулю соответствующего \(\gcd\). Именно эту величину суммируют все реализации.
Возьмем примерные циклы
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
Тогда \(s=4\), \(t=6\), и потому
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
Разбиение по четности позиции дает
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}.$$
После сортировки получаем
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
Если начальная разность фаз \(\delta=1\), то
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
Значит, в каждом совместном периоде длины 12 есть ровно 4 благоприятных показателя. На первых \(100!\) степенях этот рисунок повторяется \(100!/12\) раз, поэтому
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}.$$
Ровно такой же механизм применяется в реальном решении ко всем парам индексов.
Реализации на C++, Python и Java сначала строят переименованную перестановку, затем раскладывают ее на циклы и для каждого значения сохраняют номер цикла и позицию внутри цикла. Одновременно предварительно вычисляются факториальные веса \((n-i)!\), входящие в формулу лексикографического ранга, а также \(100! \bmod (10^9+7)\).
Для каждой упорядоченной пары циклов вычисляются \(g=\gcd(s,t)\), \(L=\operatorname{lcm}(s,t)\) и таблицы фаз \(Q_\delta(C,D)\) для \(\delta=0,1,\dots,g-1\). Поскольку модуль прост и \(L<10^9+7\), множитель \(100!/L\) представляется по модулю \(10^9+7\) как \(100!\cdot L^{-1}\).
После этой подготовки итоговое накопление становится прямым: для каждого \(i<j\) программа определяет два цикла, восстанавливает нужную фазу \(\delta\), берет заранее посчитанное значение из таблицы, умножает его на \((n-i)!\) и на модульную версию \(100!/L\), а затем добавляет в ответ. Версии на C++ и Java распараллеливают этот последний двойной цикл; версия на Python выполняет ту же математику последовательно.
Размер перестановки фиксирован: \(n=5050\). Поэтому доминирующая стоимость связана с проходом по всем \(\binom{5050}{2}\) парам индексов на заключительном этапе. Если записать \(n=1+2+\cdots+m=\Theta(m^2)\), то основная фаза имеет сложность \(O(n^2)=O(m^4)\).
Предварительная обработка пар циклов меньше по объему: циклов всего 100, а для каждой пары нужен массив размера \(\gcd(s,t)\) и несколько отсортированных классов вычетов. Память составляет \(O(n)\) для метаданных перестановки и факториальных весов плюс заметно меньшие таблицы пар циклов. На практике метод эффективен именно потому, что заменяет недостижимый перебор \(100!\) степеней одной фазой предвычисления и одной фазой подсчета.
لنضع \(m=100\) و\(n=1+2+\cdots+m=5050\). التبديل المطلوب في المسألة يُبنى أولًا من تبديل كتلي مكوَّن من دورات منفصلة أطوالها \(1,2,\dots,100\)، ثم تُعاد تسمية العناصر بواسطة تقابل ناتج عن الضرب في \(10^9+7\) بترديد \(5050\). المطلوب هو جمع الرتب المعجمية ذات الفهرسة من 1 لأول \(100!\) قوة من هذا التبديل، ثم أخذ الناتج بترديد \(10^9+7\).
المحاكاة المباشرة مستحيلة عمليًا، لأن ذلك يعني التعامل مع \(100!\) قوة مختلفة لتبديل على 5050 عنصرًا. الحل الحقيقي يستفيد من ثلاثة عناصر رياضية: بنية الدورات، وصيغة شيفرة Lehmer للرتبة المعجمية، والدورية التي تظهر عند تتبع قوة التبديل على كل زوج من الدورات.
لنرمز إلى التبديل النهائي بالرمز \(\rho\)، ولنكتب تمثيله في سطر واحد على الصورة \((\rho(1),\rho(2),\dots,\rho(n))\). الفكرة كلها هي تحويل مجموع الرتب على جميع القوى إلى مجموع ثابت على أزواج الفهارس.
التبديل الأساسي هو اتحاد منفصل لدورات متتالية أطوالها \(1,2,\dots,100\). وعملية الاقتران بإعادة التسمية تغيّر القيم المكتوبة داخل كل دورة، لكنها لا تغيّر أطوال الدورات نفسها. لذلك يبقى لدى \(\rho\) بالضبط دورة واحدة من كل طول بين 1 و100.
ومن هنا نحصل مباشرة على أن رتبة \(\rho\) تقسم \(100!\)، لأن كل طول دورة يقسم \(100!\). وهذا يعني أنه عند الجمع على أول \(100!\) قوة، فإن كل دورة تكمل عددًا صحيحًا من اللفات، وكل زوج من الدورات يمر بعدد صحيح من الفترات المشتركة.
لكل تبديل \(\alpha\) على المجموعة \(\{1,\dots,n\}\)، فإن رتبته المعجمية ذات الفهرسة من 1 تساوي
$$\operatorname{rank}(\alpha)=1+\sum_{i=1}^{n} c_i(\alpha)\,(n-i)!,$$
حيث
$$c_i(\alpha)=\#\{j \gt i:\alpha(j)\lt \alpha(i)\}.$$
وهذه هي بالضبط صيغة شيفرة Lehmer أو الكتابة بنظام المضروب. وإذا جمعنا هذه الصيغة على أول \(100!\) قوة من \(\rho\) نحصل على
$$S=\sum_{k=1}^{100!}\operatorname{rank}(\rho^k)=100!+\sum_{1\le i\lt j\le n}(n-i)!\,N_{i,j},$$
حيث
$$N_{i,j}=\#\{1\le k\le 100!:\rho^k(j)\lt \rho^k(i)\}.$$
إذن المسألة كلها تختزل إلى سؤال واحد واضح: لكل زوج ثابت \(i<j\)، كم مرة تظهر الصورتان \(\rho^k(i)\) و\(\rho^k(j)\) بترتيب عددي معكوس عندما يتغير الأس \(k\)؟
لنفترض أن \(i\) ينتمي إلى الدورة
$$C=(c_0,c_1,\dots,c_{s-1}),$$
وأن \(j\) ينتمي إلى الدورة
$$D=(d_0,d_1,\dots,d_{t-1}).$$
إذا كانت مواضع البداية هي \(u\) داخل \(C\) و\(v\) داخل \(D\)، فعند تطبيق \(\rho\) عدد \(k\) من المرات نحصل على
$$\rho^k(i)=c_{u+k \bmod s},\qquad \rho^k(j)=d_{v+k \bmod t}.$$
والآن نعرّف
$$g=\gcd(s,t),\qquad L=\operatorname{lcm}(s,t)=\frac{st}{g}.$$
زوج المواضع هذا يعيد نفسه كل \(L\) خطوة. وبما أن \(L\mid 100!\)، فيكفي أن نعدّ الأسس الملائمة داخل فترة مشتركة واحدة طولها \(L\)، ثم نضرب في \(100!/L\).
الذي يهم في فرق الطور بين الدورتين ليس الفرق الكامل، بل قيمته بترديد \(g\). لذا نضع
$$\delta\equiv v-u \pmod g.$$
ثم نقسم كل دورة وفقًا لمواضعها بترديد \(g\):
$$C_r=\{c_a:a\equiv r \pmod g\},\qquad D_r=\{d_b:b\equiv r \pmod g\}.$$
خلال فترة مشتركة كاملة طولها \(L\)، يمر الزوج \((\rho^k(i),\rho^k(j))\) بجميع أزواج المواضع التي يساوي فيها فرق فئتي البواقي \(\delta\)، وكل زوج مسموح يظهر مرة واحدة فقط. لذلك فإن عدد الأسس الملائمة في فترة واحدة هو
$$Q_\delta(C,D)=\sum_{r=0}^{g-1}\#\{(x,y)\in C_r\times D_{r+\delta}: y\lt x\}.$$
ومن ثم
$$N_{i,j}=Q_\delta(C,D)\cdot\frac{100!}{L}.$$
وبهذا تتحول المسألة من تتبع ديناميكي للقوى إلى مسألة مقارنة ثابتة ومحدودة: نرتب كل فئة من فئات البواقي مرة واحدة، ثم نعدّ لكل طور \(\delta\) عدد عناصر المجموعة الثانية الأصغر من عناصر المجموعة الأولى.
بإرجاع عدّ أزواج الدورات إلى صيغة الانعكاسات الموزونة نحصل على
$$\boxed{S=100!+\sum_{1\le i\lt j\le n}(n-i)!\,Q_{\delta(i,j)}(C(i),C(j))\frac{100!}{\operatorname{lcm}(|C(i)|,|C(j)|)} \pmod{10^9+7}.}$$
هنا \(C(i)\) و\(C(j)\) هما الدورتان اللتان تحتويان \(i\) و\(j\)، و\(\delta(i,j)\) هو فرق الطور بين موضعيهما بترديد القاسم المشترك المناسب. هذه هي الصيغة التي تجمعها التطبيقات كما هي.
لنأخذ الدورتين المثاليتين
$$C=(9,1,8,2),\qquad D=(6,3,7,4,5,10).$$
عندئذٍ \(s=4\) و\(t=6\)، وبالتالي
$$g=\gcd(4,6)=2,\qquad L=\operatorname{lcm}(4,6)=12.$$
وبتقسيمهما بحسب parity الموضع نحصل على
$$C_0=\{9,8\},\ C_1=\{1,2\},\qquad D_0=\{6,7,5\},\ D_1=\{3,4,10\}.$$
وبعد الترتيب يصبح لدينا
$$C_0=\{8,9\},\ C_1=\{1,2\},\qquad D_0=\{5,6,7\},\ D_1=\{3,4,10\}.$$
إذا كان فرق الطور الابتدائي هو \(\delta=1\)، فإن
$$Q_1(C,D)=\#\{(x,y)\in C_0\times D_1:y\lt x\}+\#\{(x,y)\in C_1\times D_0:y\lt x\}=4+0=4.$$
أي إن كل فترة مشتركة طولها 12 تحتوي على 4 أسس تحقق الشرط. وعلى أول \(100!\) قوة يتكرر هذا النمط \(100!/12\) مرة، ولذلك
$$N=4\cdot\frac{100!}{12}=\frac{100!}{3}.$$
وهو بالضبط النوع نفسه من الحساب الذي يجريه البرنامج لجميع أزواج الفهارس في المسألة الأصلية.
تبني تطبيقات C++ وPython وJava التبديل بعد إعادة التسمية، ثم تفككه إلى دورات، وتسجل لكل قيمة رقم الدورة وموضعها داخل تلك الدورة. كما تحسب مسبقًا الأوزان \((n-i)!\) التي تظهر في صيغة الرتبة المعجمية، وكذلك \(100! \bmod (10^9+7)\).
وبالنسبة لكل زوج مرتب من الدورات، تحسب الشيفرة \(g=\gcd(s,t)\) و\(L=\operatorname{lcm}(s,t)\) وجدول الأطوار \(Q_\delta(C,D)\) لكل \(\delta=0,1,\dots,g-1\). ولأن المودولو عدد أولي، ولأن \(L<10^9+7\)، فإن العامل \(100!/L\) يُمثَّل معياريًا على صورة \(100!\cdot L^{-1}\).
بعد هذه المرحلة التمهيدية تصبح الخطوة الأخيرة مجرد عملية جمع مع الرجوع إلى الجداول: لكل \(i<j\) تُحدَّد الدورتان، ثم يُستخرج فرق الطور الصحيح \(\delta\)، وتُقرأ القيمة الموافقة من الجدول، ثم تُضرب في \((n-i)!\) وفي النسخة المعيارية من \(100!/L\) وتُضاف إلى الجواب. إصدارا C++ وJava يوزعان هذه الحلقة المزدوجة الأخيرة على عدة خيوط، بينما ينفذ إصدار Python الحساب نفسه بشكل تسلسلي.
حجم التبديل ثابت هنا ويساوي \(n=5050\)، ولهذا فإن التكلفة المهيمنة هي المرور على جميع أزواج الفهارس وعددها \(\binom{5050}{2}\) في مرحلة التجميع النهائية. وإذا كتبنا \(n=1+2+\cdots+m=\Theta(m^2)\)، فإن الطور الرئيسي يملك تعقيدًا \(O(n^2)=O(m^4)\).
أما المعالجة المسبقة لأزواج الدورات فهي أصغر بكثير: هناك 100 دورة فقط، وكل زوج يحتاج إلى جدول حجمه \(\gcd(s,t)\) وبعض فئات البواقي المرتبة. استخدام الذاكرة هو \(O(n)\) لبيانات التبديل والأوزان العاملية، إضافة إلى جداول أزواج الدورات الأصغر كثيرًا من المرور النهائي. عمليًا، تكمن قوة الطريقة في أنها تستبدل تعدادًا مستحيلًا على \(100!\) قوة بمرحلة تهيئة واحدة ثم مرحلة عدّ واحدة.