Concatenate the decimal expansions of all primes below \(N\). The implementations only branch on nonzero digits, so let \(d_1,\dots,d_L\in\{1,\dots,9\}\) be that resulting stream in left-to-right order. At each position \(i\), we choose one positive divisor of \(d_i\), obtaining a generated sequence \(a_1,\dots,a_L\) with \(a_i\in D(d_i)\).
For one generated sequence, its inversion count is
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}.$$
The goal is to sum this inversion count over all divisor choices and return the total modulo
$$M=10^9+7.$$
Directly enumerating every generated sequence is impossible, because each new digit multiplies the number of branches by its divisor count. The key observation is that we do not need the sequences themselves; we only need aggregate information that is sufficient to update the global inversion total when one more digit is appended.
For each nonzero digit \(d\), define
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|.$$
These sets are fixed once and for all:
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
So every processed digit contributes only a tiny local choice set, even though the number of full sequences grows multiplicatively.
After processing the first \(i\) digits, let
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
be the number of generated prefixes. Let \(I_i\) be the sum of inversion counts over all those prefixes. For each value \(t\in\{1,\dots,9\}\), define
$$A_i(t)=\sum_{\text{all generated prefixes }a_1,\dots,a_i}\#\{k\le i:a_k=t\}.$$
This is the total number of occurrences of \(t\) across all prefixes, not merely the number of prefixes ending in \(t\). That distinction matters: when a new value is appended, it can form inversions with any earlier larger value, regardless of position.
Suppose the next processed digit is \(d_i\), with divisor set \(D(d_i)\). Every old prefix branches into \(\tau(d_i)\) continuations, so every old inversion is copied that many times:
$$\text{old contribution}=\tau(d_i)\,I_{i-1}.$$
New inversions are exactly the pairs whose right endpoint is the newly appended value. If we append \(v\in D(d_i)\), then the number of new inversions contributed over all old prefixes equals the number of earlier entries larger than \(v\):
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
Summing over all allowed appended values yields
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v).$$
For a fixed value \(t\in\{1,\dots,9\}\), every old occurrence of \(t\) is duplicated in each of the \(\tau(d_i)\) branches, contributing \(\tau(d_i)A_{i-1}(t)\).
There is also a fresh last-position contribution. If \(t\in D(d_i)\), then each old prefix creates exactly one new branch ending with \(t\), so we gain \(T_{i-1}\) additional occurrences of \(t\). Hence
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}.$$
The branch count obeys the equally simple recurrence
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0.$$
Together, these formulas completely describe the evolution of the total inversion sum.
The chosen values always lie in \(\{1,\dots,9\}\), and every divisor set has size at most \(4\). Therefore the quantities \(G_{i-1}(v)\) can be obtained from a descending suffix sum over only nine counters \(A_{i-1}(1),\dots,A_{i-1}(9)\).
The implementations skip digit \(0\), so only digits \(1\) through \(9\) enter the dynamic program. This means the combinatorial explosion of \(\prod \tau(d_i)\) is absorbed into modular arithmetic on a constant-size state rather than explicit branching.
The primes below \(20\) are
$$2,3,5,7,11,13,17,19,$$
so the processed nonzero digit stream is
$$2,3,5,7,1,1,1,3,1,7,1,9.$$
The first four digits have divisor sets \(\{1,2\}\), \(\{1,3\}\), \(\{1,5\}\), and \(\{1,7\}\). After these four steps there are
$$T_4=2^4=16$$
generated prefixes, and the inversion totals are
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24.$$
At that point the total occurrence counts are
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8,$$
with all other \(A_4(t)\) equal to \(0\). Each following digit \(1\) has only one allowed value, so the cross term is always
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32,$$
which gives
$$I_5=56,\qquad I_6=88,\qquad I_7=120.$$
The next digit is \(3\), so the old total doubles and the new cross term is \(48\), yielding
$$I_8=2\cdot 120+48=288.$$
The next digit \(1\) gives \(I_9=368\), the next digit \(7\) gives
$$I_{10}=2\cdot 368+80=816,$$
and the next digit \(1\) gives \(I_{11}=1008\). Before the final digit \(9\), the suffix totals are
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0.$$
Since \(D(9)=\{1,3,9\}\), the last cross term is \(192+96+0=288\), so
$$I_{12}=3\cdot 1008+288=3312.$$
This matches the checkpoint used by the implementations.
The C++, Python, and Java implementations all use the same mathematical state. They precompute the divisor choices for digits \(1\) through \(9\), then generate all primes below \(N\) with an odd-only sieve while handling prime \(2\) explicitly. Each prime is decomposed into decimal digits from most significant to least significant so the dynamic program sees the correct left-to-right stream.
For each nonzero digit, the implementation first builds the descending sums \(\sum_{t>v}A(t)\), then updates the global inversion total with the recurrence for \(I_i\), then updates the occurrence totals with the recurrence for \(A_i(t)\), and finally multiplies the sequence count by \(\tau(d_i)\). All arithmetic is reduced modulo \(10^9+7\).
The C++ and Java implementations perform this dynamic program directly. The Python implementation is a thin wrapper that makes sure the compiled solver is available, runs it, and returns the same numeric answer.
Let \(L\) be the number of processed nonzero digits appearing in the decimal expansions of primes below \(N\). In the given implementations, prime generation costs \(O(N\log\log N)\) time and \(O(N)\) memory. The digit dynamic program performs constant work per processed digit, because the alphabet has size \(9\) and every divisor set has size at most \(4\). Therefore the DP contributes \(O(L)\) time and \(O(1)\) extra memory.
Overall, the method runs in
$$O(N\log\log N+L)$$
time and uses \(O(N)\) memory, while avoiding explicit construction of the exponentially many generated sequences.
Man verknüpft die Dezimaldarstellungen aller Primzahlen unter \(N\). Die Implementierungen verzweigen nur bei von Null verschiedenen Ziffern; sei also \(d_1,\dots,d_L\in\{1,\dots,9\}\) der so entstehende Strom in natürlicher Reihenfolge. An jeder Position \(i\) wählt man einen positiven Teiler von \(d_i\), also \(a_i\in D(d_i)\), und erhält damit eine erzeugte Folge \(a_1,\dots,a_L\).
Für eine solche Folge ist die Inversionszahl definiert als
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}.$$
Gesucht ist die Summe dieser Inversionszahlen über alle möglichen Teilerwahlen, modulo
$$M=10^9+7.$$
Alle erzeugten Folgen explizit aufzuschreiben ist unmöglich, denn jede neue Ziffer multipliziert die Zahl der Zweige mit ihrer Teileranzahl. Entscheidend ist daher, nur solche Aggregatgrößen zu speichern, die zum Aktualisieren der globalen Inversionssumme beim Anhängen einer weiteren Ziffer ausreichen.
Für jede von Null verschiedene Ziffer \(d\) definieren wir
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|.$$
Diese Mengen sind fest:
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
Jede verarbeitete Ziffer bringt also nur eine winzige lokale Auswahl mit, obwohl die Gesamtzahl vollständiger Folgen multiplikativ wächst.
Nach den ersten \(i\) Ziffern sei
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
die Zahl der erzeugten Präfixe. Weiter sei \(I_i\) die Summe ihrer Inversionszahlen. Für jeden Wert \(t\in\{1,\dots,9\}\) definieren wir außerdem
$$A_i(t)=\sum_{\text{alle erzeugten Präfixe }a_1,\dots,a_i}\#\{k\le i:a_k=t\}.$$
Das ist die Gesamtzahl der Vorkommen von \(t\) über alle Präfixe und alle Positionen hinweg, nicht nur die Zahl der Präfixe, die auf \(t\) enden. Genau diese Information wird benötigt, weil ein neu angehängter Wert mit jedem früheren größeren Eintrag eine neue Inversion bilden kann.
Sei \(d_i\) die nächste Ziffer mit Teilermenge \(D(d_i)\). Jedes alte Präfix verzweigt in \(\tau(d_i)\) Fortsetzungen, also wird jede alte Inversion genauso oft kopiert:
$$\text{alter Beitrag}=\tau(d_i)\,I_{i-1}.$$
Neue Inversionen entstehen genau durch Paare, deren rechter Endpunkt der neu angehängte Wert ist. Hängen wir \(v\in D(d_i)\) an, so ist die Zahl der neuen Inversionen über alle alten Präfixe hinweg gleich der Zahl früherer Einträge, die größer als \(v\) sind:
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
Aufsummiert über alle erlaubten neuen Werte folgt
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v).$$
Für ein festes \(t\in\{1,\dots,9\}\) wird jedes alte Vorkommen von \(t\) in jedem der \(\tau(d_i)\) Zweige dupliziert. Das ergibt \(\tau(d_i)A_{i-1}(t)\).
Dazu kommt der neue letzte Eintrag. Falls \(t\in D(d_i)\), erzeugt jedes alte Präfix genau einen neuen Zweig, der mit \(t\) endet; also kommen \(T_{i-1}\) neue Vorkommen hinzu. Damit gilt
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}.$$
Für die Anzahl der Zweige gilt ebenso schlicht
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0.$$
Zusammen beschreiben diese Formeln die gesamte Entwicklung der Inversionssumme.
Die gewählten Werte liegen immer in \(\{1,\dots,9\}\), und jede Teilermenge hat höchstens \(4\) Elemente. Deshalb lassen sich die Größen \(G_{i-1}(v)\) durch eine absteigende Suffixsumme über nur neun Zähler \(A_{i-1}(1),\dots,A_{i-1}(9)\) berechnen.
Die Implementierungen überspringen die Ziffer \(0\), sodass nur \(1\) bis \(9\) in das dynamische Programm eingehen. Die kombinatorische Explosion von \(\prod \tau(d_i)\) wird dadurch in Modulo-Arithmetik auf einem Zustand konstanter Größe absorbiert, statt die Zweige explizit zu erzeugen.
Die Primzahlen unter \(20\) sind
$$2,3,5,7,11,13,17,19,$$
also ist der verarbeitete Strom der von Null verschiedenen Ziffern
$$2,3,5,7,1,1,1,3,1,7,1,9.$$
Die ersten vier Ziffern haben die Teilermengen \(\{1,2\}\), \(\{1,3\}\), \(\{1,5\}\) und \(\{1,7\}\). Nach diesen vier Schritten gibt es
$$T_4=2^4=16$$
erzeugte Präfixe, und die Inversionssummen lauten
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24.$$
Zu diesem Zeitpunkt sind die Häufigkeiten
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8,$$
während alle übrigen \(A_4(t)\) gleich \(0\) sind. Jede folgende Ziffer \(1\) hat nur einen erlaubten Wert, also ist der Kreuzterm stets
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32,$$
und damit
$$I_5=56,\qquad I_6=88,\qquad I_7=120.$$
Die nächste Ziffer ist \(3\); daher verdoppelt sich die alte Summe und der neue Kreuzterm ist \(48\). Also
$$I_8=2\cdot 120+48=288.$$
Die nächste Ziffer \(1\) liefert \(I_9=368\), die nächste Ziffer \(7\) liefert
$$I_{10}=2\cdot 368+80=816,$$
und die nächste Ziffer \(1\) liefert \(I_{11}=1008\). Vor der letzten Ziffer \(9\) sind die Suffixsummen
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0.$$
Da \(D(9)=\{1,3,9\}\) gilt, ist der letzte Kreuzterm \(192+96+0=288\), also
$$I_{12}=3\cdot 1008+288=3312.$$
Das ist genau der Kontrollwert aus den Implementierungen.
Die C++, Python- und Java-Implementierungen verwenden alle denselben mathematischen Zustand. Zunächst werden die Teileroptionen für die Ziffern \(1\) bis \(9\) vorbereitet. Danach werden alle Primzahlen unter \(N\) mit einem Sieb über ungerade Zahlen erzeugt, wobei die Primzahl \(2\) explizit behandelt wird. Jede Primzahl wird von der höchstwertigen zur niedrigstwertigen Dezimalziffer zerlegt, damit das dynamische Programm den korrekten links-nach-rechts-Strom sieht.
Für jede von Null verschiedene Ziffer bildet die Implementierung zuerst die absteigenden Summen \(\sum_{t>v}A(t)\), aktualisiert damit die globale Inversionssumme, ersetzt anschließend die Häufigkeitssummen gemäß der Rekursion für \(A_i(t)\) und multipliziert zuletzt die Zahl der erzeugten Folgen mit \(\tau(d_i)\). Sämtliche Arithmetik wird modulo \(10^9+7\) ausgeführt.
Die C++- und Java-Implementierungen führen dieses dynamische Programm direkt aus. Die Python-Implementierung ist ein dünner Aufrufer, der sicherstellt, dass der kompilierte Löser verfügbar ist, ihn startet und denselben numerischen Wert zurückgibt.
Sei \(L\) die Anzahl der verarbeiteten von Null verschiedenen Ziffern in den Dezimaldarstellungen der Primzahlen unter \(N\). In den vorliegenden Implementierungen kostet die Primzahlerzeugung \(O(N\log\log N)\) Zeit und \(O(N)\) Speicher. Das Ziffern-DP benötigt pro verarbeiteter Ziffer nur konstante Arbeit, weil das Alphabet Größe \(9\) hat und jede Teilermenge höchstens \(4\) Elemente enthält. Daher trägt das DP \(O(L)\) Zeit und \(O(1)\) zusätzlichen Speicher bei.
Insgesamt läuft das Verfahren also in
$$O(N\log\log N+L)$$
Zeit und verwendet \(O(N)\) Speicher, ohne die exponentiell vielen erzeugten Folgen jemals explizit zu konstruieren.
\(N\)'den küçük tüm asal sayıların ondalık yazımları art arda okunur. Uygulamalar yalnızca sıfır olmayan rakamlarda dallandığı için, soldan sağa elde edilen akışı \(d_1,\dots,d_L\in\{1,\dots,9\}\) olarak yazalım. Her konum \(i\) için \(d_i\)'nin pozitif bölenlerinden biri seçilir; böylece \(a_i\in D(d_i)\) olacak şekilde bir üretilmiş dizi \(a_1,\dots,a_L\) oluşur.
Bir üretilmiş dizinin inversion sayısı
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}$$
olarak tanımlanır. Amaç, tüm bölen seçimleri üzerindeki toplam inversion sayısını bulmak ve sonucu
$$M=10^9+7$$
modunda vermektir.
Tüm üretilmiş dizileri tek tek yazmak imkansızdır; çünkü her yeni rakam dal sayısını kendi bölen sayısı kadar çarpar. Kritik fikir, dizilerin kendisini değil, yeni bir rakam eklendiğinde toplam inversion değerini güncellemeye yetecek özet bilgileri tutmaktır.
Her sıfır olmayan rakam \(d\) için
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|$$
tanımını yapalım. Bu kümeler sabittir:
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
Yani her işlenen rakam yalnızca çok küçük bir yerel seçim kümesi getirir; asıl büyüme, tam dizilerin sayısının çarpımsal biçimde artmasından gelir.
İlk \(i\) rakam işlendiğinde
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
üretilen ön-ek sayısı olsun. \(I_i\), bu ön-eklerin inversion sayılarının toplamı olsun. Ayrıca her \(t\in\{1,\dots,9\}\) için
$$A_i(t)=\sum_{\text{tüm üretilmiş ön-ekler }a_1,\dots,a_i}\#\{k\le i:a_k=t\}$$
tanımını yapalım. Bu büyüklük, yalnızca son elemanı \(t\) olan dizileri değil; tüm ön-eklerdeki ve tüm konumlardaki toplam \(t\) sayısını tutar. Bu fark önemlidir, çünkü sona eklenen yeni bir değer, daha önceki herhangi bir büyük değerle inversion oluşturabilir.
Sıradaki işlenen rakam \(d_i\) olsun. Her eski ön-ek \(\tau(d_i)\) farklı dala ayrıldığı için eski inversion'ların her biri aynı sayıda kopyalanır:
$$\text{eski katkı}=\tau(d_i)\,I_{i-1}.$$
Yeni inversion'lar tam olarak sağ ucu yeni eklenen değer olan çiftlerdir. Eğer sona \(v\in D(d_i)\) eklenirse, tüm eski ön-ekler boyunca oluşan yeni inversion sayısı, \(v\)'den büyük eski değerlerin toplam sayısına eşittir:
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
İzin verilen tüm yeni değerler üzerinden toplarsak
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v)$$
elde edilir.
Sabit bir \(t\in\{1,\dots,9\}\) için, eski tüm \(t\) görünümleri \(\tau(d_i)\) dalın her birinde kopyalandığından \(\tau(d_i)A_{i-1}(t)\) katkısı gelir.
Buna ek olarak yeni son konum katkısı vardır. Eğer \(t\in D(d_i)\) ise, her eski ön-ek tam bir tane \(t\) ile biten yeni dal üretir; yani \(T_{i-1}\) yeni görünüm eklenir. Dolayısıyla
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}$$
olur. Dal sayısı da
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0$$
rekürsiyonunu izler. Bu formüller birlikte toplam inversion değerinin tüm evrimini belirler.
Seçilen değerler her zaman \(\{1,\dots,9\}\) aralığındadır ve her bölen kümesinin boyutu en fazla \(4\)'tür. Bu yüzden \(G_{i-1}(v)\) değerleri yalnızca dokuz sayaç \(A_{i-1}(1),\dots,A_{i-1}(9)\) üzerinden inen bir suffix toplamıyla elde edilir.
Uygulamalar \(0\) rakamını atladığı için dinamik programa yalnızca \(1\) ile \(9\) arasındaki rakamlar girer. Böylece \(\prod \tau(d_i)\) büyümesinden gelen kombinatoryal patlama, dalları açıkça üretmek yerine sabit boyutlu bir durumda modüler aritmetik ile yönetilir.
\(20\)'den küçük asallar
$$2,3,5,7,11,13,17,19$$
olduğundan, işlenen sıfır olmayan rakam akışı
$$2,3,5,7,1,1,1,3,1,7,1,9$$
şeklindedir. İlk dört rakamın bölen kümeleri sırasıyla \(\{1,2\}\), \(\{1,3\}\), \(\{1,5\}\) ve \(\{1,7\}\)'dir. Bu dört adımdan sonra
$$T_4=2^4=16$$
adet ön-ek vardır ve inversion toplamları
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24$$
olur. Bu anda görülme sayıları
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8$$
ve diğer tüm \(A_4(t)\) değerleri \(0\)'dır. Sonraki her \(1\) rakamının yalnızca tek seçeneği olduğu için çapraz terim sürekli
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32$$
olur; bu da
$$I_5=56,\qquad I_6=88,\qquad I_7=120$$
sonuçlarını verir. Sıradaki rakam \(3\) olduğu için eski toplam ikiyle çarpılır ve yeni çapraz terim \(48\) olur:
$$I_8=2\cdot 120+48=288.$$
Sonraki \(1\) rakamı \(I_9=368\) verir; sonraki \(7\) rakamı
$$I_{10}=2\cdot 368+80=816,$$
sonraki \(1\) rakamı ise \(I_{11}=1008\) verir. Son rakam \(9\)'dan hemen önce suffix toplamları
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0$$
şeklindedir. \(D(9)=\{1,3,9\}\) olduğundan son çapraz terim \(192+96+0=288\) olur ve
$$I_{12}=3\cdot 1008+288=3312$$
elde edilir. Bu değer, uygulamalardaki kontrol noktasıyla aynıdır.
C++, Python ve Java uygulamalarının hepsi aynı matematiksel durumu kullanır. Önce \(1\) ile \(9\) arasındaki rakamlar için bölen seçenekleri hazırlanır. Ardından \(N\)'den küçük asallar, \(2\) açıkça ele alınarak tek sayılar üzerinde çalışan bir sieve ile üretilir. Her asal, en anlamlı basamaktan en düşük basamağa doğru rakamlarına ayrılır; böylece dinamik program doğru soldan sağa akışı görür.
Her sıfır olmayan rakam için uygulama önce \(\sum_{t>v}A(t)\) türündeki azalan toplamları kurar, sonra inversion toplamını \(I_i\) rekürsiyonu ile günceller, ardından görülme sayıları dizisini \(A_i(t)\) rekürsiyonuna göre yeniler ve son olarak üretilen dizi sayısını \(\tau(d_i)\) ile çarpar. Tüm aritmetik \(10^9+7\) modunda yapılır.
C++ ve Java uygulamaları bu dinamik programı doğrudan yürütür. Python uygulaması ise derlenmiş çözücünün hazır olmasını sağlayan, onu çalıştıran ve aynı sayısal sonucu döndüren ince bir sarmalayıcıdır.
\(L\), \(N\)'den küçük asalların ondalık yazımlarında işlenen sıfır olmayan rakam sayısı olsun. Verilen uygulamalarda asal üretimi \(O(N\log\log N)\) zaman ve \(O(N)\) bellek gerektirir. Rakam dinamik programı, alfabe boyutu \(9\) ve her bölen kümesi en fazla \(4\) elemanlı olduğu için işlenen rakam başına sabit iş yapar. Bu nedenle DP kısmı \(O(L)\) zaman ve \(O(1)\) ek bellek kullanır.
Toplam karmaşıklık
$$O(N\log\log N+L)$$
zamandır; bellek kullanımı \(O(N)\)'dir. Üstel sayıda üretilmiş diziyi açıkça oluşturmadan sonuca ulaşılır.
Se concatenan las expansiones decimales de todos los primos menores que \(N\). Las implementaciones solo ramifican en los dígitos no nulos, así que escribimos \(d_1,\dots,d_L\in\{1,\dots,9\}\) para ese flujo resultante en orden de izquierda a derecha. En cada posición \(i\) se elige un divisor positivo de \(d_i\), lo que produce una secuencia generada \(a_1,\dots,a_L\) con \(a_i\in D(d_i)\).
Para una secuencia generada, su número de inversiones es
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}.$$
Hay que sumar este valor sobre todas las elecciones posibles de divisores y devolver el total módulo
$$M=10^9+7.$$
Enumerar todas las secuencias generadas es inviable, porque cada nuevo dígito multiplica el número de ramas por su cantidad de divisores. La idea clave es conservar solo estadísticas agregadas que basten para actualizar la suma global de inversiones al añadir un dígito más.
Para cada dígito no nulo \(d\), definimos
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|.$$
Estos conjuntos son fijos:
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
Así, cada dígito aporta solo un conjunto local diminuto, aunque el número total de secuencias completas crezca multiplicativamente.
Después de procesar los primeros \(i\) dígitos, sea
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
el número de prefijos generados. Sea \(I_i\) la suma de los números de inversiones de todos esos prefijos. Para cada valor \(t\in\{1,\dots,9\}\), definimos además
$$A_i(t)=\sum_{\text{todos los prefijos generados }a_1,\dots,a_i}\#\{k\le i:a_k=t\}.$$
Esto cuenta cuántas veces aparece \(t\) en total a través de todos los prefijos y todas las posiciones, no solo cuántos prefijos terminan en \(t\). Esa es exactamente la información que hace falta, porque un valor nuevo al final puede formar una inversión con cualquier valor anterior mayor.
Supongamos que el siguiente dígito procesado es \(d_i\), con conjunto de divisores \(D(d_i)\). Cada prefijo antiguo se bifurca en \(\tau(d_i)\) continuaciones, de modo que cada inversión antigua se copia ese mismo número de veces:
$$\text{contribución antigua}=\tau(d_i)\,I_{i-1}.$$
Las inversiones nuevas son exactamente las parejas cuyo extremo derecho es el valor recién añadido. Si añadimos \(v\in D(d_i)\), el número total de inversiones nuevas sobre todos los prefijos antiguos es el número de entradas anteriores mayores que \(v\):
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
Sumando sobre todos los valores permitidos, obtenemos
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v).$$
Para un valor fijo \(t\in\{1,\dots,9\}\), cada aparición antigua de \(t\) se duplica en cada una de las \(\tau(d_i)\) ramas, lo que aporta \(\tau(d_i)A_{i-1}(t)\).
Además existe la contribución de la última posición. Si \(t\in D(d_i)\), cada prefijo antiguo crea exactamente una nueva rama que termina en \(t\), así que se añaden \(T_{i-1}\) apariciones nuevas. Por tanto,
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}.$$
El número de ramas sigue también una recurrencia sencilla:
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0.$$
Estas fórmulas bastan para describir toda la evolución de la suma total de inversiones.
Los valores elegidos siempre pertenecen a \(\{1,\dots,9\}\), y cada conjunto de divisores tiene tamaño a lo sumo \(4\). Por eso, las cantidades \(G_{i-1}(v)\) se calculan con una simple suma sufija descendente sobre solo nueve contadores \(A_{i-1}(1),\dots,A_{i-1}(9)\).
Las implementaciones omiten el dígito \(0\), de modo que el programa dinámico solo procesa dígitos del \(1\) al \(9\). Así, la explosión combinatoria de \(\prod \tau(d_i)\) se absorbe en aritmética modular sobre un estado de tamaño constante, sin generar explícitamente todas las ramas.
Los primos menores que \(20\) son
$$2,3,5,7,11,13,17,19,$$
de modo que el flujo procesado de dígitos no nulos es
$$2,3,5,7,1,1,1,3,1,7,1,9.$$
Los primeros cuatro dígitos tienen conjuntos de divisores \(\{1,2\}\), \(\{1,3\}\), \(\{1,5\}\) y \(\{1,7\}\). Tras esos cuatro pasos hay
$$T_4=2^4=16$$
prefijos generados, y las sumas de inversiones son
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24.$$
En ese momento, las cuentas de apariciones son
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8,$$
y todos los demás \(A_4(t)\) valen \(0\). Cada dígito \(1\) posterior tiene un único valor permitido, así que el término cruzado siempre es
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32,$$
lo que produce
$$I_5=56,\qquad I_6=88,\qquad I_7=120.$$
El siguiente dígito es \(3\), de modo que la suma antigua se duplica y el nuevo término cruzado es \(48\):
$$I_8=2\cdot 120+48=288.$$
El siguiente dígito \(1\) da \(I_9=368\), el siguiente dígito \(7\) da
$$I_{10}=2\cdot 368+80=816,$$
y el siguiente dígito \(1\) da \(I_{11}=1008\). Justo antes del último dígito \(9\), las sumas sufijas son
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0.$$
Como \(D(9)=\{1,3,9\}\), el último término cruzado es \(192+96+0=288\), así que
$$I_{12}=3\cdot 1008+288=3312.$$
Este valor coincide con el punto de comprobación usado por las implementaciones.
Las implementaciones en C++, Python y Java usan el mismo estado matemático. Primero precalculan las opciones de divisores para los dígitos \(1\) a \(9\). Después generan todos los primos menores que \(N\) con una criba sobre números impares y tratando explícitamente el primo \(2\). Cada primo se descompone en sus dígitos decimales desde el más significativo hasta el menos significativo para que el programa dinámico vea el flujo correcto de izquierda a derecha.
Para cada dígito no nulo, la implementación construye primero las sumas descendentes \(\sum_{t>v}A(t)\), luego actualiza la suma global de inversiones con la recurrencia de \(I_i\), después reemplaza las cuentas de apariciones con la recurrencia de \(A_i(t)\) y finalmente multiplica el número de secuencias por \(\tau(d_i)\). Toda la aritmética se reduce módulo \(10^9+7\).
Las implementaciones en C++ y Java ejecutan este programa dinámico de forma directa. La implementación en Python es un envoltorio ligero que garantiza que el solucionador compilado esté disponible, lo ejecuta y devuelve el mismo resultado numérico.
Sea \(L\) el número de dígitos no nulos procesados en las expansiones decimales de los primos menores que \(N\). En las implementaciones dadas, la generación de primos cuesta \(O(N\log\log N)\) tiempo y \(O(N)\) memoria. El programa dinámico sobre dígitos realiza trabajo constante por dígito procesado, porque el alfabeto tiene tamaño \(9\) y cada conjunto de divisores tiene tamaño como máximo \(4\). Por tanto, la parte de DP aporta \(O(L)\) tiempo y \(O(1)\) memoria adicional.
En conjunto, el método funciona en
$$O(N\log\log N+L)$$
tiempo y usa \(O(N)\) memoria, sin construir nunca de forma explícita las exponencialmente muchas secuencias generadas.
把所有小于 \(N\) 的素数写成十进制后按顺序拼接起来。实现中只对非零数字进行分支，所以记从左到右得到的非零数字流为 \(d_1,\dots,d_L\in\{1,\dots,9\}\)。在第 \(i\) 个位置，我们从 \(d_i\) 的正因子中选一个值，于是得到一条生成序列 \(a_1,\dots,a_L\)，其中 \(a_i\in D(d_i)\)。
对任意一条生成序列，它的逆序对数定义为
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}.$$
题目要求把 所有 因子选择方案对应的逆序对数全部加起来，并对
$$M=10^9+7$$
取模。
如果真的把每一条生成序列都列出来，规模会立刻失控，因为每遇到一个新数字，分支总数就会乘上这个数字的因子个数。关键观察是：我们不需要保存所有序列本身，只需要保存那些足以在“再追加一个数字”时更新全局逆序对总和的聚合量。
对每个非零数字 \(d\)，定义
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|.$$
这些集合是固定不变的：
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
因此，每个数字本身带来的局部选择规模非常小；真正困难的地方在于完整序列条数会随着这些局部选择数连乘增长。
处理完前 \(i\) 个数字之后，记
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
为当前生成前缀的总数。记 \(I_i\) 为这些前缀的逆序对总和。对每个 \(t\in\{1,\dots,9\}\)，再定义
$$A_i(t)=\sum_{\text{所有生成前缀 }a_1,\dots,a_i}\#\{k\le i:a_k=t\}.$$
\(A_i(t)\) 统计的是值 \(t\) 在 所有 前缀、所有 位置上的总出现次数，而不是“以 \(t\) 结尾的前缀有多少条”。这点非常关键，因为新追加的一个值会和前面任意位置上更大的值形成逆序对。
设当前要处理的下一个数字是 \(d_i\)，它的因子集合为 \(D(d_i)\)。每条旧前缀都会分裂成 \(\tau(d_i)\) 条新分支，因此所有旧逆序对都会被完整复制 \(\tau(d_i)\) 次：
$$\text{旧贡献}=\tau(d_i)\,I_{i-1}.$$
新增逆序对只可能来自“右端点就是新追加值”的那些配对。如果追加的是某个 \(v\in D(d_i)\)，那么跨越所有旧前缀时，新产生的逆序对数恰好等于“之前所有位置里，大于 \(v\) 的值出现了多少次”，也就是
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
对所有允许的追加值求和，就得到
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v).$$
固定一个值 \(t\in\{1,\dots,9\}\)。原来所有值为 \(t\) 的出现，在 \(\tau(d_i)\) 条分支中都会被复制，所以带来 \(\tau(d_i)A_{i-1}(t)\)。
除此之外，还有新末尾位置的贡献。如果 \(t\in D(d_i)\)，那么每条旧前缀都会恰好生成一条“最后一个值是 \(t\)”的新分支，因此会新增 \(T_{i-1}\) 次 \(t\) 的出现。于是
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}.$$
分支总数本身也满足
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0.$$
这组递推已经完整刻画了总逆序对值如何随着数字流推进而变化。
可选值始终落在 \(\{1,\dots,9\}\) 内，而每个因子集合最多只有 \(4\) 个元素。因此，\(G_{i-1}(v)\) 只需对九个计数器 \(A_{i-1}(1),\dots,A_{i-1}(9)\) 做一次从大到小的后缀求和就能得到。
实现还会跳过数字 \(0\)，所以动态规划真正处理的只有 \(1\) 到 \(9\) 这九种情况。这样一来，\(\prod \tau(d_i)\) 带来的指数级分支膨胀就被压缩进一个常数大小的模运算状态里，而不需要显式展开任何分支树。
小于 \(20\) 的素数是
$$2,3,5,7,11,13,17,19,$$
因此处理到的非零数字流为
$$2,3,5,7,1,1,1,3,1,7,1,9.$$
前四个数字的因子集合分别是 \(\{1,2\}\)、\(\{1,3\}\)、\(\{1,5\}\)、\(\{1,7\}\)。处理完这四步以后，生成前缀总数为
$$T_4=2^4=16,$$
而逆序对总和依次为
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24.$$
此时的出现次数总和是
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8,$$
其余 \(A_4(t)\) 都为 \(0\)。后面连续出现的每个数字 \(1\) 都只有唯一选择，因此它们的新增交叉项始终是
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32,$$
于是得到
$$I_5=56,\qquad I_6=88,\qquad I_7=120.$$
下一个数字是 \(3\)，所以旧总和翻倍，再加上新的交叉项 \(48\)，得到
$$I_8=2\cdot 120+48=288.$$
接着下一个数字 \(1\) 给出 \(I_9=368\)，再下一个数字 \(7\) 给出
$$I_{10}=2\cdot 368+80=816,$$
再下一个数字 \(1\) 给出 \(I_{11}=1008\)。在最后一个数字 \(9\) 到来之前，后缀和为
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0.$$
由于 \(D(9)=\{1,3,9\}\)，最后一步的交叉项就是 \(192+96+0=288\)，所以
$$I_{12}=3\cdot 1008+288=3312.$$
这个结果与实现中的校验值完全一致。
C++、Python 和 Java 实现都使用同一套数学状态。它们先预处理数字 \(1\) 到 \(9\) 的因子选项，然后用只筛奇数的方法生成所有小于 \(N\) 的素数，并单独处理素数 \(2\)。每个素数再从最高位到最低位拆成十进制数字，让动态规划看到正确的从左到右数字流。
对每个非零数字，实现都会先构造 \(\sum_{t>v}A(t)\) 这样的降序后缀和，然后用 \(I_i\) 的递推更新全局逆序对总和，再按 \(A_i(t)\) 的递推替换出现次数数组，最后把生成序列总数乘上 \(\tau(d_i)\)。所有运算都在模 \(10^9+7\) 下进行。
C++ 和 Java 实现直接执行这套动态规划。Python 实现则是一个很薄的包装层：它确保编译后的求解器可用，运行该求解器，并返回同一个数值答案。
设 \(L\) 为所有小于 \(N\) 的素数十进制展开中，被实际处理的非零数字个数。在给定实现里，素数筛的复杂度是 \(O(N\log\log N)\) 时间和 \(O(N)\) 空间。数字动态规划对每个已处理数字只做常数工作，因为字母表大小固定为 \(9\)，且每个因子集合大小最多为 \(4\)。因此 DP 部分的复杂度是 \(O(L)\) 时间和 \(O(1)\) 额外空间。
总复杂度为
$$O(N\log\log N+L)$$
时间、\(O(N)\) 空间，而且整个过程中从不显式构造指数数量的生成序列。
Берутся десятичные записи всех простых чисел меньше \(N\) и сцепляются в один поток. Реализации ветвят процесс только по ненулевым цифрам, поэтому обозначим через \(d_1,\dots,d_L\in\{1,\dots,9\}\) полученный поток в порядке слева направо. В позиции \(i\) выбирается один положительный делитель числа \(d_i\), и так возникает порожденная последовательность \(a_1,\dots,a_L\), где \(a_i\in D(d_i)\).
Для одной такой последовательности число инверсий равно
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}.$$
Нужно просуммировать это значение по всем допустимым выборам делителей и вернуть ответ по модулю
$$M=10^9+7.$$
Невозможно перечислить все порожденные последовательности напрямую: каждая новая цифра умножает число ветвей на количество своих делителей. Поэтому нужно хранить только такие агрегированные величины, которых достаточно, чтобы обновить глобальную сумму инверсий после добавления еще одной цифры.
Для каждой ненулевой цифры \(d\) определим
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|.$$
Эти множества фиксированы:
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
Значит, каждая цифра сама по себе добавляет лишь очень маленький локальный набор вариантов, хотя общее число полных последовательностей растет мультипликативно.
После обработки первых \(i\) цифр положим
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
равным числу сгенерированных префиксов. Пусть \(I_i\) обозначает сумму чисел инверсий по всем этим префиксам. Для каждого \(t\in\{1,\dots,9\}\) введем еще
$$A_i(t)=\sum_{\text{все сгенерированные префиксы }a_1,\dots,a_i}\#\{k\le i:a_k=t\}.$$
Эта величина считает общее число появлений значения \(t\) во всех префиксах и во всех позициях, а не только число префиксов, заканчивающихся на \(t\). Именно это нужно для инверсий: новый добавленный элемент образует инверсии с любыми более крупными значениями, встретившимися раньше.
Пусть следующая обрабатываемая цифра равна \(d_i\), а ее множество делителей есть \(D(d_i)\). Каждый старый префикс порождает \(\tau(d_i)\) продолжений, поэтому каждая старая инверсия просто копируется столько раз:
$$\text{старый вклад}=\tau(d_i)\,I_{i-1}.$$
Новые инверсии возникают только у пар, чья правая граница есть вновь добавленное значение. Если дописать \(v\in D(d_i)\), то число новых инверсий по всем старым префиксам равно числу более крупных прежних значений:
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
Суммируя по всем допустимым \(v\), получаем
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v).$$
Зафиксируем \(t\in\{1,\dots,9\}\). Каждое старое появление \(t\) копируется в каждой из \(\tau(d_i)\) ветвей, что дает вклад \(\tau(d_i)A_{i-1}(t)\).
Есть и вклад новой последней позиции. Если \(t\in D(d_i)\), то каждый старый префикс создает ровно одну новую ветвь, заканчивающуюся на \(t\), значит прибавляется \(T_{i-1}\) новых появлений. Следовательно,
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}.$$
Число ветвей подчиняется столь же простой формуле:
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0.$$
Эти рекурсии полностью описывают эволюцию общей суммы инверсий.
Выбираемые значения всегда лежат в \(\{1,\dots,9\}\), а каждое множество делителей имеет размер не больше \(4\). Поэтому величины \(G_{i-1}(v)\) находятся обычной нисходящей суффиксной суммой по всего девяти счетчикам \(A_{i-1}(1),\dots,A_{i-1}(9)\).
Реализации пропускают цифру \(0\), так что в динамическую программу попадают только цифры от \(1\) до \(9\). Благодаря этому комбинаторный взрыв \(\prod \tau(d_i)\) сводится к модульной арифметике над состоянием постоянного размера, а не к явному построению всех ветвей.
Простые числа меньше \(20\) таковы:
$$2,3,5,7,11,13,17,19,$$
поэтому поток обрабатываемых ненулевых цифр равен
$$2,3,5,7,1,1,1,3,1,7,1,9.$$
Первые четыре цифры имеют множества делителей \(\{1,2\}\), \(\{1,3\}\), \(\{1,5\}\) и \(\{1,7\}\). После этих четырех шагов число сгенерированных префиксов равно
$$T_4=2^4=16,$$
а суммы инверсий равны
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24.$$
В этот момент суммарные появления имеют вид
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8,$$
а все остальные \(A_4(t)\) равны \(0\). Каждая следующая цифра \(1\) имеет единственный допустимый выбор, поэтому перекрестный вклад каждый раз равен
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32,$$
и отсюда
$$I_5=56,\qquad I_6=88,\qquad I_7=120.$$
Следующая цифра равна \(3\), значит старая сумма удваивается, а новый перекрестный вклад равен \(48\):
$$I_8=2\cdot 120+48=288.$$
Далее следующая цифра \(1\) дает \(I_9=368\), следующая цифра \(7\) дает
$$I_{10}=2\cdot 368+80=816,$$
а следующая цифра \(1\) дает \(I_{11}=1008\). Перед последней цифрой \(9\) суффиксные суммы равны
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0.$$
Так как \(D(9)=\{1,3,9\}\), последний перекрестный вклад равен \(192+96+0=288\), и потому
$$I_{12}=3\cdot 1008+288=3312.$$
Это в точности совпадает с контрольным значением в реализациях.
Реализации на C++, Python и Java используют одно и то же математическое состояние. Сначала они заранее строят наборы делителей для цифр от \(1\) до \(9\). Затем все простые меньше \(N\) генерируются решетом по нечетным числам, причем простое число \(2\) обрабатывается отдельно. Каждое простое раскладывается на десятичные цифры от старшего разряда к младшему, чтобы динамическая программа получала правильный поток слева направо.
Для каждой ненулевой цифры реализация сначала строит нисходящие суммы вида \(\sum_{t>v}A(t)\), затем обновляет глобальную сумму инверсий по рекурсии для \(I_i\), после этого заменяет массив суммарных появлений по рекурсии для \(A_i(t)\) и в конце умножает число последовательностей на \(\tau(d_i)\). Все вычисления ведутся по модулю \(10^9+7\).
Реализации на C++ и Java выполняют это динамическое программирование напрямую. Реализация на Python является тонкой оберткой: она гарантирует наличие скомпилированного решателя, запускает его и возвращает тот же численный ответ.
Пусть \(L\) обозначает число обрабатываемых ненулевых цифр в десятичных представлениях простых чисел меньше \(N\). В данных реализациях построение простых стоит \(O(N\log\log N)\) времени и \(O(N)\) памяти. Динамическая программа по цифрам выполняет постоянный объем работы на каждую обработанную цифру, поскольку алфавит имеет размер \(9\), а каждое множество делителей имеет размер не более \(4\). Поэтому вклад DP равен \(O(L)\) по времени и \(O(1)\) по дополнительной памяти.
Итоговая сложность метода равна
$$O(N\log\log N+L)$$
по времени и \(O(N)\) по памяти. При этом экспоненциально большое семейство порожденных последовательностей никогда не строится явно.
نأخذ التمثيل العشري لجميع الأعداد الأولية الأصغر من \(N\) ونوصله في تيار واحد. التنفيذات لا تُنشئ تفرعًا إلا عند الأرقام غير الصفرية، لذا نرمز للتيار الناتج من اليسار إلى اليمين بـ \(d_1,\dots,d_L\in\{1,\dots,9\}\). في الموضع \(i\) نختار قاسمًا موجبًا واحدًا للرقم \(d_i\)، فنحصل على سلسلة مولدة \(a_1,\dots,a_L\) بحيث \(a_i\in D(d_i)\).
عدد الانقلابات في سلسلة مولدة واحدة هو
$$\operatorname{inv}(a_1,\dots,a_L)=\#\{(i,j):1\le i<j\le L,\ a_i>a_j\}.$$
والمطلوب هو جمع هذا العدد على جميع اختيارات القواسم الممكنة، ثم إرجاع الناتج بترديد
$$M=10^9+7.$$
من المستحيل أن نولّد كل السلاسل صراحةً، لأن كل رقم جديد يضرب عدد الفروع في عدد قواسمه. الفكرة الأساسية هي الاكتفاء بمجموعة صغيرة من المقادير المجمعة التي تكفي لتحديث مجموع الانقلابات العالمي عند إلحاق رقم جديد.
لكل رقم غير صفري \(d\) نعرّف
$$D(d)=\{x\in\{1,\dots,9\}: x\mid d\},\qquad \tau(d)=|D(d)|.$$
وهذه المجموعات ثابتة:
$$\begin{aligned} D(1)&=\{1\}, & D(2)&=\{1,2\}, & D(3)&=\{1,3\},\\ D(4)&=\{1,2,4\}, & D(5)&=\{1,5\}, & D(6)&=\{1,2,3,6\},\\ D(7)&=\{1,7\}, & D(8)&=\{1,2,4,8\}, & D(9)&=\{1,3,9\}. \end{aligned}$$
إذن كل رقم يضيف مجموعة خيارات صغيرة جدًا محليًا، بينما يأتي التعقيد من أن عدد السلاسل الكاملة ينمو بشكل ضربي.
بعد معالجة أول \(i\) أرقام، ليكن
$$T_i=\prod_{k=1}^{i}\tau(d_k)$$
هو عدد البوادئ المولدة. ولتكن \(I_i\) مجموع أعداد الانقلابات عبر هذه البوادئ كلها. ولكل قيمة \(t\in\{1,\dots,9\}\) نعرّف كذلك
ولنرمز إلى مجموعة جميع البوادئ المولدة بعد \(i\) خطوات بالرمز \(\mathcal{P}_i\). عندئذ
$$A_i(t)=\sum_{(a_1,\dots,a_i)\in \mathcal{P}_i}\#\{k\le i:a_k=t\}.$$
هذا المقدار لا يحصي عدد البوادئ التي تنتهي بالقيمة \(t\) فقط، بل يحصي مجموع مرات ظهور \(t\) في كل البوادئ وكل المواضع. وهذا هو المطلوب فعليًا، لأن القيمة الجديدة في النهاية قد تُكوّن انقلابًا مع أي قيمة سابقة أكبر منها، مهما كان موضعها.
إذا كان الرقم التالي هو \(d_i\) وله مجموعة قواسم \(D(d_i)\)، فإن كل بادئة قديمة تتفرع إلى \(\tau(d_i)\) امتدادات. لذلك تُنسخ كل الانقلابات القديمة هذا العدد من المرات:
$$\tau(d_i)\,I_{i-1}.$$
أما الانقلابات الجديدة فهي بالضبط الأزواج التي يكون طرفها الأيمن هو القيمة المضافة حديثًا. فإذا ألحقنا قيمة \(v\in D(d_i)\)، فإن عدد الانقلابات الجديدة عبر جميع البوادئ القديمة يساوي عدد القيم السابقة الأكبر من \(v\):
$$G_{i-1}(v)=\sum_{t=v+1}^{9}A_{i-1}(t).$$
وبالجمع على جميع القيم المسموح بها نحصل على
$$I_i=\tau(d_i)\,I_{i-1}+\sum_{v\in D(d_i)}G_{i-1}(v).$$
ثبّت قيمة \(t\in\{1,\dots,9\}\). كل ظهور قديم لـ \(t\) يُنسخ في كل واحد من الفروع \(\tau(d_i)\)، فتكون مساهمته \(\tau(d_i)A_{i-1}(t)\).
وهناك أيضًا مساهمة الموضع الأخير الجديد. إذا كان \(t\in D(d_i)\)، فإن كل بادئة قديمة تُنتج فرعًا واحدًا بالضبط ينتهي بالقيمة \(t\)، وبالتالي نكسب \(T_{i-1}\) ظهورات جديدة من \(t\). إذن
$$A_i(t)=\tau(d_i)\,A_{i-1}(t)+\mathbf{1}_{t\in D(d_i)}\,T_{i-1}.$$
كما أن عدد الفروع نفسه يحقق العلاقة
$$T_i=\tau(d_i)\,T_{i-1},\qquad T_0=1,\qquad I_0=0,\qquad A_0(t)=0.$$
وهذه العلاقات مجتمعة تصف كامل تطور مجموع الانقلابات المطلوب.
القيم المختارة تقع دائمًا في \(\{1,\dots,9\}\)، وكل مجموعة قواسم لا يزيد حجمها على \(4\). لذلك يمكن استخراج الكميات \(G_{i-1}(v)\) بحساب مجاميع لاحقة تنازلية على تسعة عدّادات فقط هي \(A_{i-1}(1),\dots,A_{i-1}(9)\).
كما أن التنفيذات تتجاوز الرقم \(0\)، ولذلك لا يدخل في البرمجة الديناميكية إلا الأرقام من \(1\) إلى \(9\). وهكذا يتم امتصاص الانفجار التركيبي في \(\prod \tau(d_i)\) داخل حسابات معيارية على حالة ذات حجم ثابت بدلًا من توليد كل الفروع صراحةً.
الأعداد الأولية الأصغر من \(20\) هي
$$2,3,5,7,11,13,17,19,$$
ومن ثم فإن تيار الأرقام غير الصفرية المعالَج هو
$$2,3,5,7,1,1,1,3,1,7,1,9.$$
الأرقام الأربعة الأولى لها مجموعات القواسم \(\{1,2\}\) و\(\{1,3\}\) و\(\{1,5\}\) و\(\{1,7\}\). بعد هذه الخطوات الأربع يصبح لدينا
$$T_4=2^4=16$$
بادئة مولدة، بينما تكون مجاميع الانقلابات
$$I_1=0,\qquad I_2=1,\qquad I_3=6,\qquad I_4=24.$$
وفي تلك اللحظة تكون مجاميع الظهور
$$A_4(1)=32,\qquad A_4(2)=A_4(3)=A_4(5)=A_4(7)=8,$$
وجميع القيم الأخرى \(A_4(t)\) تساوي \(0\). كل رقم لاحق من النوع \(1\) يملك خيارًا وحيدًا، ولذلك يكون الحد المتقاطع دائمًا
$$A_4(2)+A_4(3)+A_4(5)+A_4(7)=32,$$
ومن ثم نحصل على
$$I_5=56,\qquad I_6=88,\qquad I_7=120.$$
الرقم التالي هو \(3\)، لذا يتضاعف المجموع القديم ويضاف إليه حد متقاطع جديد مقداره \(48\)، فنحصل على
$$I_8=2\cdot 120+48=288.$$
ثم يعطي الرقم \(1\) التالي القيمة \(I_9=368\)، ويعطي الرقم \(7\) التالي
$$I_{10}=2\cdot 368+80=816,$$
ثم يعطي الرقم \(1\) التالي \(I_{11}=1008\). وقبل الرقم الأخير \(9\) تكون المجاميع اللاحقة
$$\sum_{t>1}A_{11}(t)=192,\qquad \sum_{t>3}A_{11}(t)=96,\qquad \sum_{t>9}A_{11}(t)=0.$$
وبما أن \(D(9)=\{1,3,9\}\)، فإن الحد المتقاطع الأخير يساوي \(192+96+0=288\)، وبالتالي
$$I_{12}=3\cdot 1008+288=3312.$$
وهذا يطابق نقطة التحقق المستخدمة في التنفيذات.
تنفيذات C++ وPython وJava تستخدم الحالة الرياضية نفسها. فهي تسبق أولًا حساب خيارات القواسم للأرقام من \(1\) إلى \(9\)، ثم تولّد جميع الأعداد الأولية الأصغر من \(N\) باستخدام غربال يعمل على الأعداد الفردية مع معالجة العدد الأولي \(2\) صراحةً. بعد ذلك يُفك كل عدد أولي إلى أرقامه العشرية من الخانة الأعلى إلى الأدنى حتى ترى البرمجة الديناميكية التيار الصحيح من اليسار إلى اليمين.
عند كل رقم غير صفري، تبني الشيفرة أولًا المجاميع التنازلية من الصورة \(\sum_{t>v}A(t)\)، ثم تحدّث مجموع الانقلابات العالمي باستخدام علاقة \(I_i\)، ثم تستبدل مجاميع الظهور وفق علاقة \(A_i(t)\)، وأخيرًا تضرب عدد السلاسل في \(\tau(d_i)\). جميع العمليات تُختزل بترديد \(10^9+7\).
تنفيذَا C++ وJava ينفذان هذه البرمجة الديناميكية مباشرةً. أما تنفيذ Python فهو غلاف خفيف يضمن توفر الحل المترجَم، ثم يشغله ويعيد القيمة العددية نفسها.
ليكن \(L\) هو عدد الأرقام غير الصفرية التي تُعالَج فعليًا في التمثيلات العشرية للأعداد الأولية الأصغر من \(N\). في التنفيذات المعطاة، يكلف توليد الأعداد الأولية \(O(N\log\log N)\) زمنًا و\(O(N)\) ذاكرة. أما البرمجة الديناميكية على الأرقام فتكلف عملًا ثابتًا لكل رقم معالَج، لأن حجم الأبجدية \(9\) فقط، وكل مجموعة قواسم لا يزيد حجمها على \(4\). لذلك تسهم هذه المرحلة بـ \(O(L)\) زمنًا و\(O(1)\) ذاكرة إضافية.
وعليه فالتعقيد الكلي هو
$$O(N\log\log N+L)$$
زمنًا و\(O(N)\) ذاكرة، من غير أن نُنشئ صراحةً العائلة الأسية الضخمة من السلاسل المولدة.