Let \(p_1,p_2,\dots\) be the primes and \(c_1,c_2,\dots\) be the composite numbers. Define the digital-root sequences
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n)),$$
where
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
The task is to form the shortest decimal digit string that contains both \(P_n\) and \(C_n\) as subsequences. If several shortest strings exist, we take the lexicographically smallest one; because every digit lies in \(\{1,\dots,9\}\), this is also the numerically smallest shortest superinteger. The required output is that enormous integer modulo \(10^9+7\), and the implementations target \(n=10000\).
Write
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
We must compute the lexicographically least shortest common supersequence of these two digit sequences.
The first stage is purely arithmetic. We scan the integers from \(2\) upward, separate primes from composites, and replace each accepted value by its digital root. Because
$$\operatorname{dr}(x)\in\{1,2,\dots,9\},$$
both sequences consist only of ordinary decimal digits and contain no zeros. This matters later, because equal-length digit strings are ordered lexicographically exactly as their decimal integers are ordered.
A shortest common supersequence (SCS) of \(A\) and \(B\) is a shortest string that contains both sequences in order, not necessarily contiguously. Every valid answer must preserve the internal order of \(A\) and the internal order of \(B\). If \(a_i=b_j\), one output digit can serve both sequences simultaneously; if they differ, the next output digit must come from either \(A\) or \(B\).
So the problem is not about decimal arithmetic first. It is a sequence-merging problem whose final merged digit string is interpreted as an integer only at the end.
Let \(L(i,j)\) be the length of the shortest common supersequence of the suffixes
$$a_i a_{i+1}\dots a_n\qquad\text{and}\qquad b_j b_{j+1}\dots b_n,$$
with the convention that \(L(n+1,n+1)=0\). The boundary cases are immediate:
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1.$$
For interior states we have
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j. \end{cases}$$
The recurrence is standard: matching digits are consumed together, while different digits force a choice of which sequence contributes the next output digit.
The length table tells us which moves keep the answer shortest. Reconstruction then follows these rules:
1. If one sequence is exhausted, append the rest of the other sequence.
2. If \(a_i=b_j\), output that digit once and advance in both sequences.
3. If \(a_i\ne b_j\), compare \(L(i+1,j)\) and \(L(i,j+1)\).
If one option gives a smaller remaining length, that branch is forced. If both options preserve the optimal length, then both produce shortest supersequences, so the first digit decides lexicographic order immediately. Therefore we output \(\min(a_i,b_j)\). By induction on the remaining suffix length, this greedy tie-break yields the lexicographically smallest shortest supersequence.
If the final digit string is \(d_1d_2\dots d_t\), its value modulo \(10^9+7\) can be accumulated online by
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}.$$
This avoids constructing a huge big integer. The algorithm only needs the next chosen digit, so reconstruction and modular evaluation can happen in the same pass.
The first ten prime digital roots are
$$P_{10}=(2,3,5,7,2,4,8,1,5,2),$$
and the first ten composite digital roots are
$$C_{10}=(4,6,8,9,1,3,5,6,7,9).$$
The common subsequence \((4,8,1,5)\) already shows that the answer can be shorter than length \(20\), and the dynamic-programming table proves that the true optimum length is \(16\). After lexicographic tie-breaking, the shortest supersequence becomes
$$2357246891352679.$$
This is the checkpoint used by the implementations for \(f(10)\). They also verify that \(f(100)\equiv 771661825 \pmod{10^9+7}\).
The C++, Python, and Java implementations follow the same pipeline. First they sieve enough integers to collect the first \(n\) primes and the first \(n\) composites, converting each accepted number to its digital root immediately. Next they fill an \((n+1)\times(n+1)\) dynamic-programming table from bottom right to top left so that every state already knows the optimal remaining length of its suffixes.
After that, the implementation reconstructs one digit at a time. Equal digits are merged, unequal digits consult the two neighboring table entries, and ties are broken by the smaller next digit. At the same moment, the answer is updated modulo \(10^9+7\). For small checkpoint cases the full digit string can also be materialized, but that is not needed for the final \(n=10000\) computation.
Let \(M\) be the largest integer that must be sieved in order to collect \(n\) primes and \(n\) composites. Building primality information up to \(M\) costs \(O(M\log\log M)\) time and \(O(M)\) memory. Since the prime side is the sparse one, \(M\) is on the order of the \(n\)-th prime, so \(M=\Theta(n\log n)\).
The SCS stage dominates: filling the length table takes \(O(n^2)\) time and \(O(n^2)\) memory. Reconstruction adds only \(O(t)\) time, where \(t\le 2n\). For the target \(n=10000\), the quadratic dynamic programming is the main cost.
Seien \(p_1,p_2,\dots\) die Primzahlen und \(c_1,c_2,\dots\) die zusammengesetzten Zahlen. Definiere die Folgen der digitalen Wurzeln durch
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n)),$$
wobei
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
Gesucht ist die kürzeste Dezimalziffernfolge, die sowohl \(P_n\) als auch \(C_n\) als Teilfolgen enthält. Gibt es mehrere gleich kurze Kandidaten, wählen wir den lexikographisch kleinsten; da alle Ziffern in \(\{1,\dots,9\}\) liegen, ist das zugleich der numerisch kleinste kürzeste Superinteger. Ausgegeben wird der Wert modulo \(10^9+7\), und die Implementierungen zielen auf \(n=10000\).
Schreibe
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
Damit reduziert sich die Aufgabe auf die lexikographisch kleinste kürzeste gemeinsame Oberfolge dieser beiden Ziffernfolgen.
Zuerst werden die natürlichen Zahlen ab \(2\) durchlaufen, in Primzahlen und zusammengesetzte Zahlen getrennt und anschließend sofort durch ihre digitale Wurzel ersetzt. Wegen
$$\operatorname{dr}(x)\in\{1,2,\dots,9\}$$
entstehen Folgen aus normalen Dezimalziffern ohne Nullen. Genau deshalb stimmt bei gleich langen Kandidaten die lexikographische Ordnung mit der numerischen Ordnung der zugehörigen Dezimalzahlen überein.
Eine kürzeste gemeinsame Oberfolge (SCS) von \(A\) und \(B\) ist die kürzeste Folge, in der beide Ursprungsfolgen in derselben Reihenfolge als Teilfolgen auftauchen. Jede gültige Antwort muss also die innere Reihenfolge von \(A\) und die innere Reihenfolge von \(B\) bewahren. Falls \(a_i=b_j\) gilt, kann eine einzige ausgegebene Ziffer beide Folgen gleichzeitig bedienen; sonst muss die nächste Ziffer entweder aus \(A\) oder aus \(B\) kommen.
Das Problem ist deshalb zunächst ein optimales Verschmelzen zweier Folgen. Die Interpretation als ganze Zahl passiert erst danach.
Sei \(L(i,j)\) die Länge der kürzesten gemeinsamen Oberfolge der Suffixe
$$a_i a_{i+1}\dots a_n\qquad\text{und}\qquad b_j b_{j+1}\dots b_n,$$
mit \(L(n+1,n+1)=0\). Die Randfälle lauten
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1.$$
Für innere Zustände gilt die Rekursion
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j. \end{cases}$$
Stimmen die Ziffern überein, werden sie gemeinsam verbraucht. Sonst entscheidet man sich für den Zweig mit der kleineren verbleibenden SCS-Länge.
Die Längentabelle sagt uns, welche Übergänge die Antwort kurz halten. Beim Wiederaufbau gelten daher:
1. Ist eine Folge bereits erschöpft, wird der Rest der anderen angehängt.
2. Gilt \(a_i=b_j\), wird diese Ziffer genau einmal ausgegeben und in beiden Folgen weitergegangen.
3. Gilt \(a_i\ne b_j\), vergleicht man \(L(i+1,j)\) und \(L(i,j+1)\).
Erzwingt eine Seite eine kleinere Restlänge, ist die Wahl eindeutig. Bei Gleichstand bleiben beide Wege optimal; dann entscheidet sofort die erste ausgegebene Ziffer über die lexikographische Ordnung. Also wählt man \(\min(a_i,b_j)\). Per Induktion über die verbleibende Suffixlänge liefert dieses gierige Tie-Breaking die lexikographisch kleinste kürzeste Oberfolge.
Hat die endgültige Ziffernfolge die Form \(d_1d_2\dots d_t\), so genügt die laufende Modulo-Auswertung
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}.$$
Damit braucht man keinen Big-Integer für den Endwert. Wiederaufbau und Modulo-Berechnung können in einem einzigen Durchlauf kombiniert werden.
Die ersten zehn digitalen Wurzeln der Primzahlen sind
$$P_{10}=(2,3,5,7,2,4,8,1,5,2),$$
und für die ersten zehn zusammengesetzten Zahlen erhält man
$$C_{10}=(4,6,8,9,1,3,5,6,7,9).$$
Die gemeinsame Teilfolge \((4,8,1,5)\) zeigt bereits, dass eine Länge kleiner als \(20\) möglich ist, und die dynamische Programmierung beweist, dass das Optimum genau \(16\) beträgt. Nach lexikographischem Tie-Breaking ergibt sich die kürzeste Oberfolge
$$2357246891352679.$$
Das ist genau der Prüfwert für \(f(10)\). Zusätzlich wird kontrolliert, dass \(f(100)\equiv 771661825 \pmod{10^9+7}\) gilt.
Die C++-, Python- und Java-Implementierungen folgen demselben Ablauf. Zuerst wird bis zu einer hinreichenden Schranke gesiebt, um die ersten \(n\) Primzahlen und die ersten \(n\) zusammengesetzten Zahlen zu sammeln; jede akzeptierte Zahl wird sofort in ihre digitale Wurzel umgewandelt. Danach wird eine \((n+1)\times(n+1)\)-Tabelle der dynamischen Programmierung von rechts unten nach links oben gefüllt, sodass jeder Zustand die optimale Restlänge seiner beiden Suffixe kennt.
Anschließend wird die Antwort zifferweise rekonstruiert. Gleiche Ziffern werden zusammengelegt, unterschiedliche Ziffern vergleichen die beiden Nachbarzustände der Tabelle, und bei Gleichstand gewinnt die kleinere nächste Ziffer. Gleichzeitig wird der numerische Wert modulo \(10^9+7\) fortgeschrieben. Für kleine Kontrollfälle kann die komplette Ziffernfolge zusätzlich materialisiert werden; für \(n=10000\) ist das jedoch nicht erforderlich.
Sei \(M\) die größte Zahl, bis zu der gesiebt werden muss, um \(n\) Primzahlen und \(n\) zusammengesetzte Zahlen zu erhalten. Das Sieb benötigt \(O(M\log\log M)\) Zeit und \(O(M)\) Speicher. Da Primzahlen die dünnere Folge bilden, liegt \(M\) in der Größenordnung der \(n\)-ten Primzahl, also bei \(M=\Theta(n\log n)\).
Dominant ist jedoch die SCS-Tabelle: Ihr Aufbau kostet \(O(n^2)\) Zeit und \(O(n^2)\) Speicher. Der Wiederaufbau benötigt nur noch \(O(t)\) Zeit mit \(t\le 2n\). Für das Ziel \(n=10000\) ist die quadratische dynamische Programmierung der wesentliche Aufwand.
\(p_1,p_2,\dots\) asal sayılar ve \(c_1,c_2,\dots\) bileşik sayılar olsun. Dijital kök dizilerini
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n))$$
şeklinde tanımlayalım; burada
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
Aranan şey, hem \(P_n\) hem de \(C_n\) dizilerini alt dizi olarak içeren en kısa ondalık basamak dizisidir. Aynı en kısa uzunluğa sahip birden fazla aday varsa sözlükçe en küçüğü seçilir; tüm basamaklar \(\{1,\dots,9\}\) kümesinde olduğundan bu aynı zamanda sayısal olarak da en küçük en kısa superinteger olur. Sonuç \(10^9+7\) modunda istenir ve uygulamalar \(n=10000\) için çözüm üretir.
Şöyle yazalım:
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
Böylece görev, bu iki basamak dizisinin sözlükçe en küçük en kısa ortak üst dizisini bulmaya dönüşür.
İlk aşama tamamen aritmetiktir. \(2\)'den başlayarak tamsayılar taranır, asallar ve bileşikler ayrılır, sonra her kabul edilen sayı dijital köküne çevrilir. Çünkü
$$\operatorname{dr}(x)\in\{1,2,\dots,9\},$$
elde edilen iki dizi yalnızca sıradan ondalık basamaklardan oluşur ve hiç \(0\) içermez. Bu ayrıntı önemlidir: uzunluğu eşit iki aday için sözlük sırası ile sayısal sıra tamamen aynıdır.
En kısa ortak üst dizi (SCS), \(A\) ve \(B\)'yi sıralarını bozmadan alt dizi olarak içeren en kısa dizidir. Her geçerli cevap, \(A\)'nın kendi iç sırasını ve \(B\)'nin kendi iç sırasını korumak zorundadır. Eğer \(a_i=b_j\) ise tek bir çıktı basamağı iki diziyi aynı anda ilerletebilir; farklıysalar sıradaki basamak ya \(A\)'dan ya da \(B\)'den gelmelidir.
Dolayısıyla sorun önce büyük tam sayı üretmek değil, iki diziyi en iyi biçimde birleştirmektir. Sayısal yorum son aşamada gelir.
\(L(i,j)\),
$$a_i a_{i+1}\dots a_n\qquad\text{ve}\qquad b_j b_{j+1}\dots b_n$$
son eklerinin en kısa ortak üst dizi uzunluğu olsun. \(L(n+1,n+1)=0\) kabulüyle sınır koşulları
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1$$
şeklindedir. İç durumlarda ise
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j \end{cases}$$
bağıntısı kullanılır. Basamaklar eşitse birlikte tüketilir, değilse daha kısa kalan yolu veren dal seçilir.
Uzunluk tablosu hangi geçişlerin cevabı minimal tuttuğunu söyler. Yeniden kurulumda şu kurallar uygulanır:
1. Dizilerden biri biterse diğerinin kalanı eklenir.
2. \(a_i=b_j\) ise bu basamak bir kez yazılır ve iki dizide de ilerlenir.
3. \(a_i\ne b_j\) ise \(L(i+1,j)\) ile \(L(i,j+1)\) karşılaştırılır.
Bir seçenek daha kısa kalan uzunluk veriyorsa seçim zorunludur. İki seçenek de optimal uzunluğu koruyorsa, sözlük sırasını daha ilk basamak belirler; bu yüzden \(\min(a_i,b_j)\) seçilir. Kalan son ek uzunluğu üzerinde indüksiyonla bu açgözlü eşitlik bozma kuralının sözlükçe en küçük en kısa üst diziyi verdiği görülür.
Son basamak dizisi \(d_1d_2\dots d_t\) ise değer
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}$$
ile soldan sağa biriktirilebilir. Böylece dev bir tam sayı nesnesi oluşturmaya gerek kalmaz; yeniden kurma ve mod hesabı aynı geçişte yapılır.
İlk on asalın dijital kökleri
$$P_{10}=(2,3,5,7,2,4,8,1,5,2)$$
ve ilk on bileşiğin dijital kökleri
$$C_{10}=(4,6,8,9,1,3,5,6,7,9)$$
olur. Ortak alt dizi \((4,8,1,5)\), cevabın \(20\)'den kısa olabileceğini gösterir; dinamik programlama ise gerçek optimum uzunluğun \(16\) olduğunu kanıtlar. Sözlükçe en küçük bağ bozma uygulandığında en kısa üst dizi
$$2357246891352679$$
şeklinde elde edilir. Bu, \(f(10)\) için kullanılan kontrol değeridir. Ayrıca \(f(100)\equiv 771661825 \pmod{10^9+7}\) eşitliği de doğrulanır.
C++, Python ve Java uygulamaları aynı iskeleti izler. Önce, ilk \(n\) asal ve ilk \(n\) bileşiği toplamaya yetecek bir üst sınıra kadar süzgeç kurulup sayılar anında dijital köke dönüştürülür. Sonra \((n+1)\times(n+1)\) boyutlu dinamik programlama tablosu sağ alttan sol üste doğru doldurulur; böylece her hücre kendi iki son ekinin optimal kalan uzunluğunu bilir.
Bundan sonra cevap basamak basamak yeniden kurulur. Eşit basamaklar tek kopya halinde birleştirilir, farklı basamaklar için tablodaki iki komşu duruma bakılır ve eşitlikte küçük olan basamak seçilir. Aynı anda sonuç \(10^9+7\) modunda güncellenir. Küçük kontrol örneklerinde tam basamak dizisi de üretilebilir, fakat nihai \(n=10000\) hesabı için buna gerek yoktur.
\(M\), \(n\) asal ve \(n\) bileşik toplamaya yetecek en büyük süzgeç sınırı olsun. Bu sınıra kadar asal bilgisi üretmek \(O(M\log\log M)\) zaman ve \(O(M)\) bellek ister. Seyrek olan taraf asallar olduğundan, \(M\) büyüklük olarak \(n\)'inci asala denktir; dolayısıyla \(M=\Theta(n\log n)\).
Ana maliyet ise SCS tablosudur: tabloyu doldurmak \(O(n^2)\) zaman ve \(O(n^2)\) bellek gerektirir. Yeniden kurulum yalnızca \(O(t)\) zaman ekler; burada \(t\le 2n\). Hedef \(n=10000\) için baskın maliyet kuadratik dinamik programlamadır.
Sean \(p_1,p_2,\dots\) los números primos y \(c_1,c_2,\dots\) los números compuestos. Definimos las secuencias de raíces digitales
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n)),$$
donde
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
Hay que construir la cadena decimal más corta que contenga a \(P_n\) y a \(C_n\) como subsecuencias. Si existen varias con la misma longitud mínima, se elige la menor en orden lexicográfico; como todos los dígitos pertenecen a \(\{1,\dots,9\}\), eso coincide también con el entero numéricamente más pequeño entre las supersecuencias mínimas. La salida pedida es ese entero gigantesco módulo \(10^9+7\), y las implementaciones resuelven el caso \(n=10000\).
Escribimos
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
Entonces el problema consiste en hallar la supersecuencia común más corta y, entre todas ellas, la lexicográficamente menor.
La primera etapa es aritmética. Se recorren los enteros desde \(2\), se separan primos y compuestos, y cada valor aceptado se reemplaza por su raíz digital. Como
$$\operatorname{dr}(x)\in\{1,2,\dots,9\},$$
ambas secuencias solo contienen dígitos decimales ordinarios y nunca contienen ceros. Ese detalle es importante porque, cuando dos candidatos tienen la misma longitud, el orden lexicográfico coincide exactamente con el orden numérico de los enteros decimales representados.
Una supersecuencia común más corta (SCS) de \(A\) y \(B\) es la secuencia más corta que contiene a ambas preservando su orden interno. Toda respuesta válida debe respetar el orden relativo de \(A\) y también el de \(B\). Si \(a_i=b_j\), un solo dígito de salida puede servir para las dos secuencias a la vez; si son distintos, el siguiente dígito debe venir de \(A\) o de \(B\).
Así, el núcleo del problema no es la aritmética de enteros grandes, sino la fusión óptima de dos secuencias de símbolos.
Sea \(L(i,j)\) la longitud de la supersecuencia común más corta de los sufijos
$$a_i a_{i+1}\dots a_n\qquad\text{y}\qquad b_j b_{j+1}\dots b_n,$$
con \(L(n+1,n+1)=0\). Los casos de borde son
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1.$$
Para los estados interiores se cumple
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j. \end{cases}$$
Cuando los dígitos coinciden se consumen juntos; cuando difieren, se elige la continuación que deja la menor longitud restante.
La tabla de longitudes indica qué movimientos mantienen la longitud óptima. Por eso la reconstrucción sigue estas reglas:
1. Si una secuencia ya terminó, se añade el resto de la otra.
2. Si \(a_i=b_j\), ese dígito se escribe una sola vez y se avanza en ambas.
3. Si \(a_i\ne b_j\), se comparan \(L(i+1,j)\) y \(L(i,j+1)\).
Si una de las dos opciones deja una longitud restante menor, esa rama es obligatoria. Si ambas conservan la longitud mínima, entonces las dos producen SCS óptimas y el primer dígito decide de inmediato el orden lexicográfico; por tanto se toma \(\min(a_i,b_j)\). Por inducción sobre la longitud del sufijo restante, este desempate voraz produce la menor cadena lexicográfica entre todas las óptimas.
Si la cadena final es \(d_1d_2\dots d_t\), su valor módulo \(10^9+7\) se obtiene en línea mediante
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}.$$
Así no hace falta construir un entero gigante. Basta con conocer el siguiente dígito elegido durante la reconstrucción.
Las primeras diez raíces digitales de los primos son
$$P_{10}=(2,3,5,7,2,4,8,1,5,2),$$
y para los diez primeros compuestos obtenemos
$$C_{10}=(4,6,8,9,1,3,5,6,7,9).$$
La subsecuencia común \((4,8,1,5)\) ya muestra que la respuesta puede ser más corta que \(20\), y la tabla de programación dinámica demuestra que la longitud óptima exacta es \(16\). Tras aplicar el desempate lexicográfico, la supersecuencia mínima es
$$2357246891352679.$$
Ese es el valor de comprobación para \(f(10)\). Además, se verifica que \(f(100)\equiv 771661825 \pmod{10^9+7}\).
Las implementaciones en C++, Python y Java siguen la misma idea. Primero cribán suficientes enteros para reunir los primeros \(n\) primos y los primeros \(n\) compuestos, transformando cada número aceptado en su raíz digital en cuanto aparece. Después rellenan una tabla de programación dinámica de tamaño \((n+1)\times(n+1)\) desde la esquina inferior derecha hacia la superior izquierda, de modo que cada estado conoce la longitud óptima restante de sus dos sufijos.
Luego la solución reconstruye la respuesta dígito a dígito. Los dígitos iguales se fusionan, los distintos consultan las dos celdas vecinas de la tabla y, en caso de empate, se toma el menor de los dos próximos dígitos. Al mismo tiempo, el valor numérico se actualiza módulo \(10^9+7\). Para casos pequeños de verificación se puede materializar la cadena completa, pero para el cálculo final con \(n=10000\) no es necesario.
Sea \(M\) el mayor entero que debe cribarse para obtener \(n\) primos y \(n\) compuestos. Construir la información de primalidad hasta \(M\) cuesta \(O(M\log\log M)\) tiempo y \(O(M)\) memoria. Como la parte escasa es la de los primos, \(M\) tiene el mismo orden que el \(n\)-ésimo primo, es decir, \(M=\Theta(n\log n)\).
Sin embargo, domina la etapa SCS: rellenar la tabla requiere \(O(n^2)\) tiempo y \(O(n^2)\) memoria. La reconstrucción añade solo \(O(t)\) tiempo, con \(t\le 2n\). Para el objetivo \(n=10000\), la programación dinámica cuadrática es el coste principal.
设 \(p_1,p_2,\dots\) 为按从小到大排列的素数，\(c_1,c_2,\dots\) 为按从小到大排列的合数。定义两条数字根序列
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n)),$$
其中
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
题目要求构造一个最短的十进制数字串，使得 \(P_n\) 和 \(C_n\) 都能按顺序作为它的子序列出现。如果最短答案不止一个，就取字典序最小的那个。由于这里出现的数字都在 \(\{1,\dots,9\}\) 中，不会出现前导零，所以“字典序最小”也就等价于“数值最小”的最短超级整数。最终只需要输出这个巨大整数对 \(10^9+7\) 取模后的结果，实际求解目标是 \(n=10000\)。
记
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
于是问题可以精确地表述为：求 \(A\) 与 \(B\) 的最短公共超序列，并在所有最短公共超序列中取字典序最小者。
第一部分是数论预处理。从 \(2\) 开始依次扫描整数，用筛法区分素数与合数，并把每个被接纳的数立刻替换成数字根。因为
$$\operatorname{dr}(x)\in\{1,2,\dots,9\},$$
所以两条序列都只包含普通十进制数字，而且绝不会出现 \(0\)。这一点非常关键：当两个候选答案长度相同时，按字典序比较它们，得到的次序就与按十进制整数大小比较完全一致。
所谓最短公共超序列，就是一条最短的数字串，它同时包含 \(A\) 和 \(B\) 作为子序列。这里“子序列”只要求相对顺序不变，不要求连续。因此，任何合法答案都必须保留 \(A\) 内部的先后顺序，也必须保留 \(B\) 内部的先后顺序。若某一步出现 \(a_i=b_j\)，那么这一位可以在输出中只写一次，同时满足两边；若 \(a_i\ne b_j\)，那么下一位就必须在“先取 \(A\)”和“先取 \(B\)”之间做选择。
也就是说，问题的核心不是大整数运算，而是如何在保持两边顺序的前提下，用最少的位数把两条数字流合并起来。
定义 \(L(i,j)\) 为下面两个后缀的最短公共超序列长度：
$$a_i a_{i+1}\dots a_n\qquad\text{和}\qquad b_j b_{j+1}\dots b_n.$$
约定 \(L(n+1,n+1)=0\)。边界情形很直接：
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1.$$
内部状态满足递推式
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j. \end{cases}$$
含义非常清楚。如果当前两位相同，那么这位只能合并输出一次，随后两个下标一起前进；如果当前两位不同，那么无论怎样都要先输出一位，所以总长度多出 \(1\)，再加上两个可能后继中较短的那一个。
长度表只告诉我们“最短长度是多少”，还要进一步决定“具体输出哪一个最短答案”。重建时遵循以下规则：
1. 如果某一条序列已经用完，就把另一条序列剩余的所有数字直接接到答案末尾。
2. 如果 \(a_i=b_j\)，就把这个数字输出一次，并同时移动两个下标。
3. 如果 \(a_i\ne b_j\)，就比较 \(L(i+1,j)\) 与 \(L(i,j+1)\)。
若其中一边更小，说明那一边是唯一能够保持最短性的选择；若两边相等，说明先取 \(A\) 或先取 \(B\) 都能得到最短公共超序列。这时决定字典序的关键就是当前输出的第一位，因此直接选择较小的那个数字，也就是 \(\min(a_i,b_j)\)。对剩余后缀长度做归纳，就能说明这个局部贪心的 tie-break 规则会得到全局字典序最小的最短答案。
若最终答案写成 \(d_1d_2\dots d_t\)，则它对 \(10^9+7\) 的余数可以逐位更新：
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}.$$
因此完全没有必要把整个超级整数作为大整数对象保存下来。算法在重建每一位的同时，就可以把模值一起推进。
前十个素数的数字根为
$$P_{10}=(2,3,5,7,2,4,8,1,5,2),$$
前十个合数的数字根为
$$C_{10}=(4,6,8,9,1,3,5,6,7,9).$$
公共子序列 \((4,8,1,5)\) 已经说明答案长度会小于 \(20\)，而动态规划表进一步确认真正的最优长度恰好是 \(16\)。在长度最优的前提下按字典序取最小，得到的最短公共超序列是
$$2357246891352679.$$
这正是程序用于校验的 \(f(10)\) 检查值；同时还会验证 \(f(100)\equiv 771661825 \pmod{10^9+7}\)。
C++、Python 和 Java 实现遵循同一条主线。首先，它们筛出足够大的整数范围，从中依次收集前 \(n\) 个素数和前 \(n\) 个合数，并立即把每个数映射为数字根。接着，它们建立一个 \((n+1)\times(n+1)\) 的动态规划表，并从右下角向左上角回填，使得每个状态都已经知道对应后缀对的最优剩余长度。
随后，程序按位重建答案。若当前两位相等，就合并成一位；若不相等，就查看表中相邻的两个后继状态；若两边都还能保持最短长度，就输出较小的那个数字。与此同时，答案对 \(10^9+7\) 的余数也按十进制逐位更新。对于小规模校验案例，可以额外把完整数字串保留下来；但在最终 \(n=10000\) 的计算中，只维护模值就足够了。
设 \(M\) 为为了收集到 \(n\) 个素数和 \(n\) 个合数而需要筛到的最大整数。筛法部分的时间复杂度为 \(O(M\log\log M)\)，空间复杂度为 \(O(M)\)。由于素数比分布更稀疏，它决定了 \(M\) 的数量级，因此有 \(M=\Theta(n\log n)\)。
真正占主导的是 SCS 动态规划：填完整张长度表需要 \(O(n^2)\) 时间和 \(O(n^2)\) 空间。重建答案只再花 \(O(t)\) 时间，其中 \(t\le 2n\)。对目标规模 \(n=10000\) 而言，二次规模的动态规划是主要成本。
Пусть \(p_1,p_2,\dots\) обозначают простые числа, а \(c_1,c_2,\dots\) обозначают составные числа. Определим последовательности цифровых корней
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n)),$$
где
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
Нужно построить кратчайшую десятичную строку цифр, которая содержит и \(P_n\), и \(C_n\) как подпоследовательности. Если таких кратчайших строк несколько, выбирается лексикографически наименьшая; поскольку все цифры лежат в \(\{1,\dots,9\}\), это одновременно и численно наименьший кратчайший суперinteger. Требуется вернуть значение этого огромного числа по модулю \(10^9+7\); в реальном вычислении берется \(n=10000\).
Обозначим
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
Тогда задача сводится к поиску лексикографически наименьшей кратчайшей общей суперпоследовательности двух цифровых последовательностей \(A\) и \(B\).
Сначала идет чисто арифметический этап. Целые числа перебираются начиная с \(2\), делятся на простые и составные, после чего каждое принятое число сразу заменяется своим цифровым корнем. Так как
$$\operatorname{dr}(x)\in\{1,2,\dots,9\},$$
обе последовательности состоят из обычных десятичных цифр и не содержат нулей. Это важно: среди строк одинаковой длины лексикографический порядок точно совпадает с порядком соответствующих десятичных чисел.
Кратчайшая общая суперпоследовательность (SCS) для \(A\) и \(B\) - это кратчайшая строка, в которой обе последовательности встречаются как подпоследовательности с сохранением порядка. Поэтому любой допустимый ответ обязан сохранять внутренний порядок элементов \(A\) и внутренний порядок элементов \(B\). Если \(a_i=b_j\), одна выходная цифра может обслужить сразу обе стороны; если цифры различны, следующая цифра должна быть взята либо из \(A\), либо из \(B\).
Итак, основа решения - это не работа с длинной арифметикой, а оптимальное слияние двух упорядоченных потоков цифр.
Пусть \(L(i,j)\) - длина кратчайшей общей суперпоследовательности для суффиксов
$$a_i a_{i+1}\dots a_n\qquad\text{и}\qquad b_j b_{j+1}\dots b_n,$$
причем \(L(n+1,n+1)=0\). Граничные случаи таковы:
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1.$$
Для внутренних состояний действует рекуррентная формула
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j. \end{cases}$$
Если текущие цифры совпадают, они сливаются в одну. Если нет, приходится сделать один вывод сейчас и выбрать тот из двух последующих вариантов, который оставляет минимальную длину хвоста.
Таблица длин говорит, какие переходы сохраняют оптимальность. При восстановлении применяются правила:
1. Если одна последовательность уже исчерпана, к ответу дописывается остаток другой.
2. Если \(a_i=b_j\), эта цифра выводится один раз, а оба индекса сдвигаются.
3. Если \(a_i\ne b_j\), сравниваются \(L(i+1,j)\) и \(L(i,j+1)\).
Если одна ветвь оставляет меньшую длину, выбор принудителен. Если обе ветви дают одинаковую оптимальную длину, то обе ведут к кратчайшим суперпоследовательностям, и тогда лексикографический порядок определяется уже первой цифрой. Значит, нужно вывести \(\min(a_i,b_j)\). Индукция по длине оставшегося суффикса показывает, что такой локальный выбор дает глобально лексикографически минимальный кратчайший ответ.
Если итоговая строка цифр равна \(d_1d_2\dots d_t\), то ее значение по модулю \(10^9+7\) можно обновлять на лету:
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}.$$
Поэтому нет необходимости хранить целиком огромное целое число. Достаточно восстанавливать ответ по одной цифре и сразу обновлять модуль.
Первые десять цифровых корней простых чисел равны
$$P_{10}=(2,3,5,7,2,4,8,1,5,2),$$
а для первых десяти составных чисел получаем
$$C_{10}=(4,6,8,9,1,3,5,6,7,9).$$
Общая подпоследовательность \((4,8,1,5)\) уже показывает, что длина ответа может быть меньше \(20\), а таблица динамического программирования подтверждает, что истинный оптимум равен \(16\). После лексикографического tie-break получается суперпоследовательность
$$2357246891352679.$$
Это и есть контрольное значение для \(f(10)\). Дополнительно проверяется, что \(f(100)\equiv 771661825 \pmod{10^9+7}\).
Реализации на C++, Python и Java идут по одной и той же схеме. Сначала они просеивают достаточно большой диапазон чисел, чтобы набрать первые \(n\) простых и первые \(n\) составных, сразу преобразуя каждое выбранное число в его цифровой корень. Затем строится таблица динамического программирования размера \((n+1)\times(n+1)\), которая заполняется от правого нижнего угла к левому верхнему, так что в каждом состоянии уже известна оптимальная остаточная длина для соответствующих двух суффиксов.
После этого ответ восстанавливается по одной цифре. Равные цифры сливаются, разные обращаются к двум соседним состояниям таблицы, а при равенстве выбирается меньшая следующая цифра. Одновременно значение результата обновляется по модулю \(10^9+7\). Для небольших контрольных случаев можно дополнительно материализовать полную строку цифр, но для окончательного случая \(n=10000\) достаточно только модульного значения.
Пусть \(M\) - наибольшее число, до которого нужно выполнить решето, чтобы получить \(n\) простых и \(n\) составных чисел. Построение информации о простоте до \(M\) требует \(O(M\log\log M)\) времени и \(O(M)\) памяти. Поскольку редкой стороной являются именно простые числа, величина \(M\) имеет порядок \(n\)-го простого, то есть \(M=\Theta(n\log n)\).
Но главным узким местом является этап SCS: заполнение таблицы длин занимает \(O(n^2)\) времени и \(O(n^2)\) памяти. Восстановление ответа добавляет лишь \(O(t)\) времени, где \(t\le 2n\). Для целевого случая \(n=10000\) именно квадратичная динамика определяет основную стоимость вычисления.
لتكن \(p_1,p_2,\dots\) هي الأعداد الأولية، ولتكن \(c_1,c_2,\dots\) هي الأعداد المركبة. نعرّف سلسلتي الجذر الرقمي على الصورة
$$P_n=(\operatorname{dr}(p_1),\dots,\operatorname{dr}(p_n)),\qquad C_n=(\operatorname{dr}(c_1),\dots,\operatorname{dr}(c_n)),$$
حيث
$$\operatorname{dr}(x)=1+((x-1)\bmod 9).$$
المطلوب هو بناء أقصر سلسلة من الأرقام العشرية تحتوي كلًا من \(P_n\) و\(C_n\) كتتابعين جزئيين. وإذا وُجد أكثر من جواب بالطول الأدنى نفسه، نأخذ الأصغر معجميًا؛ وبما أن جميع الأرقام تقع في \(\{1,\dots,9\}\) فلا توجد أصفار بادئة، ولذلك يطابق هذا أيضًا أصغر عدد ممكن بين جميع السلاسل الدنيا الطول. في النهاية نعيد قيمة هذا العدد الضخم بترديد \(10^9+7\)، والحالة المستهدفة في التنفيذ هي \(n=10000\).
لنكتب
$$A=(a_1,\dots,a_n)=P_n,\qquad B=(b_1,\dots,b_n)=C_n.$$
وبذلك تصبح المسألة هي إيجاد أقصر تسلسل علوي مشترك لهاتين السلسلتين، ثم اختيار الأصغر معجميًا بين جميع الحلول المثلى.
المرحلة الأولى حسابية بحتة. نمسح الأعداد الصحيحة ابتداءً من \(2\)، ونفصل الأولي عن المركب، ثم نستبدل كل عدد مقبول بجذره الرقمي مباشرة. وبما أن
$$\operatorname{dr}(x)\in\{1,2,\dots,9\},$$
فإن السلسلتين الناتجتين تتكونان فقط من أرقام عشرية عادية ولا تحتويان على الصفر. وهذه نقطة مهمة، لأن المقارنة المعجمية بين سلسلتين لهما الطول نفسه تطابق تمامًا المقارنة العددية بين العددين العشريين اللذين تمثلانهما.
أقصر تسلسل علوي مشترك هو أقصر سلسلة تحتوي \(A\) و\(B\) كتتابعين جزئيين مع الحفاظ على الترتيب الداخلي لكل منهما. لذلك يجب أن يحافظ أي جواب صحيح على ترتيب عناصر \(A\) وعلى ترتيب عناصر \(B\). إذا تحقق \(a_i=b_j\)، فإن رقمًا واحدًا في الخرج يكفي لخدمة السلسلتين معًا؛ أما إذا اختلف الرقمان، فلا بد أن يأتي الرقم التالي إما من \(A\) أو من \(B\).
إذن جوهر الحل ليس حساب عدد كبير أولًا، بل دمج سلسلتين منظمتين بأقل عدد ممكن من الخانات.
لتكن \(L(i,j)\) هي طول أقصر تسلسل علوي مشترك للذيلين
$$a_i a_{i+1}\dots a_n,\qquad b_j b_{j+1}\dots b_n,$$
مع الاتفاق على أن \(L(n+1,n+1)=0\). حالتا الحد هما
$$L(n+1,j)=n-j+1,\qquad L(i,n+1)=n-i+1.$$
أما داخل الجدول فالعلاقة هي
$$L(i,j)= \begin{cases} 1+L(i+1,j+1), & a_i=b_j,\\ 1+\min\{L(i+1,j),L(i,j+1)\}, & a_i\ne b_j. \end{cases}$$
إذا كان الرقمان الحاليان متساويين فإننا نخرجهما مرة واحدة ونتحرك قطريًا. وإذا كانا مختلفين فنحن مضطرون إلى إخراج خانة الآن، ثم نختار الامتداد الذي يترك أقصر طول متبقٍ.
جدول الأطوال يحدد الحركات التي تبقي الحل في الطول الأدنى. وعند إعادة البناء نتبع القواعد الآتية:
1. إذا انتهت إحدى السلسلتين، نُلحق بقية السلسلة الأخرى كما هي.
2. إذا كان \(a_i=b_j\)، نطبع هذا الرقم مرة واحدة ونتقدم في السلسلتين معًا.
3. إذا كان \(a_i\ne b_j\)، نقارن بين \(L(i+1,j)\) و\(L(i,j+1)\).
إذا كان أحد الفرعين يعطي طولًا متبقيًا أصغر فهو الفرع الإجباري. وإذا كان الفرعان يحافظان على الطول الأمثل نفسه، فكل منهما يؤدي إلى حل أقصر ممكن، وعندها تحسم الخانة الأولى الترتيب المعجمي فورًا. لذلك نأخذ \(\min(a_i,b_j)\). وبالاستقراء على طول الذيل المتبقي، ينتج عن قاعدة كسر التعادل هذه الحل المعجمي الأصغر عالميًا بين جميع الحلول المثلى.
إذا كانت السلسلة النهائية هي \(d_1d_2\dots d_t\)، فيمكن تحديث قيمتها بترديد \(10^9+7\) تدريجيًا عبر
$$V_0=0,\qquad V_{k+1}\equiv 10V_k+d_{k+1}\pmod{10^9+7}.$$
وهكذا لا حاجة إلى تمثيل العدد النهائي كعدد صحيح ضخم. يكفي معرفة الرقم التالي أثناء إعادة البناء وتحديث الباقي في اللحظة نفسها.
الجذور الرقمية لأول عشرة أعداد أولية هي
$$P_{10}=(2,3,5,7,2,4,8,1,5,2),$$
ولأول عشرة أعداد مركبة نحصل على
$$C_{10}=(4,6,8,9,1,3,5,6,7,9).$$
التتابع الجزئي المشترك \((4,8,1,5)\) يبين بالفعل أن طول الجواب يمكن أن يكون أقل من \(20\)، ثم يثبت جدول البرمجة الديناميكية أن الطول الأمثل الحقيقي هو \(16\). وبعد تطبيق كسر التعادل المعجمي نحصل على
$$2357246891352679.$$
وهذه هي قيمة التحقق المستخدمة للحالة \(f(10)\). كما يجري التحقق أيضًا من أن \(f(100)\equiv 771661825 \pmod{10^9+7}\).
تتبع تطبيقات C++ وPython وJava المسار نفسه. فهي تبدأ ببناء غربال على مجال كبير بما يكفي لجمع أول \(n\) عدد أولي وأول \(n\) عدد مركب، مع تحويل كل عدد مقبول فورًا إلى جذره الرقمي. بعد ذلك تُملأ مصفوفة برمجة ديناميكية بحجم \((n+1)\times(n+1)\) من الزاوية اليمنى السفلية إلى الزاوية اليسرى العلوية، بحيث يعرف كل موضع الطول الأمثل المتبقي لذيليه المقابلين.
ثم يُعاد بناء الجواب رقمًا بعد رقم. الأرقام المتساوية تُدمج في خانة واحدة، والأرقام المختلفة تنظر إلى الخليتين المجاورتين في جدول الأطوال، وعند التعادل يُختار الرقم الأصغر. وفي الوقت نفسه تُحدَّث قيمة الناتج بترديد \(10^9+7\). وفي حالات التحقق الصغيرة يمكن الاحتفاظ بالسلسلة الكاملة، أما في الحساب النهائي عندما \(n=10000\) فالمطلوب عمليًا هو القيمة المعيارية فقط.
لتكن \(M\) أكبر قيمة يجب غربلتها كي نحصل على \(n\) عددًا أوليًا و\(n\) عددًا مركبًا. بناء معلومات الأولية حتى \(M\) يحتاج إلى \(O(M\log\log M)\) زمنًا و\(O(M)\) ذاكرة. وبما أن الأعداد الأولية هي الجانب الأكثر ندرة، فإن \(M\) يكون من رتبة العدد الأولي رقم \(n\)، أي \(M=\Theta(n\log n)\).
لكن المرحلة المهيمنة هي جدول SCS نفسه: تعبئة الجدول تكلف \(O(n^2)\) زمنًا و\(O(n^2)\) ذاكرة. أما إعادة البناء فتضيف فقط \(O(t)\) زمنًا حيث \(t\le 2n\). وعند الحجم المستهدف \(n=10000\)، تكون البرمجة الديناميكية التربيعية هي الكلفة الأساسية.