For each integer \(x\) with \(0 \le x < 10^n\), write \(x\) as an \(n\)-digit decimal string by allowing leading zeros. Sort those \(n\) digits into nondecreasing order, then read the result as an ordinary base-10 integer, so any leading zeros disappear automatically. The task is to compute the total of these sorted values for \(n=18\), modulo \(1123455689\).
A naive computation would examine all \(10^{18}\) inputs. The key observation is that the sorted result depends only on how many times each digit appears, not on the original order of the digits.
Let \(S(n)\) be the required sum over all \(n\)-digit strings with leading zeros allowed.
For one decimal string, let \(c_d\) be the number of occurrences of digit \(d\), where \(d \in \{0,1,\dots,9\}\). Then
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
Once these counts are known, the sorted image of the number is fixed. Therefore we can sum by digit-multiplicity vectors instead of by individual numbers.
The implementations iterate over \(c_1,\dots,c_9\) and infer the zero count from
$$c_0=n-\sum_{d=1}^9 c_d.$$
This is enough because zeros contribute to the multiplicity of the multiset, but after sorting they only create leading zeros, which do not affect the final integer value.
Define the repunit of length \(k\) by
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$$
If digit \(d\) appears \(c_d\) times, then its block in the sorted number contributes \(dR_{c_d}\). That block must then be shifted left by the number of digits that appear to its right, namely
$$t_d=\sum_{j=d+1}^9 c_j.$$
So the sorted value attached to the count vector is
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$$
This formula automatically ignores the leading zero block. It is equivalent to appending digit blocks one by one in increasing order, using the recurrence
$$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c.$$
For a fixed digit multiset \((c_0,\dots,c_9)\), the number of different original strings is the multinomial coefficient
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
Since the search chooses only the nonzero counts explicitly, it is convenient to write
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s,$$
and therefore
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$$
This weight counts all permutations of the multiset, including those that begin with zero. That is correct, because the original problem ranges over all integers from \(0\) to \(10^n-1\), equivalently over all \(n\)-digit strings with leading zeros allowed.
Combining the sorted value with its multiplicity gives
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
The final answer required by the problem is
$$S(18)\bmod 1123455689.$$
This formula matches the exact combinatorial structure used by the implementations: one term for each admissible vector of digit counts, no term for the astronomically many raw input strings.
For \(n=2\), the method groups the \(100\) strings from \(00\) to \(99\) by their digit multisets.
If the digits are \(\{0,d\}\) with \(1\le d\le 9\), the sorted value is \(d\), and there are \(2\) original strings: \(0d\) and \(d0\).
If the digits are \(\{d,d\}\) with \(1\le d\le 9\), the sorted value is \(11d\), and there is \(1\) original string.
If the digits are \(\{a,b\}\) with \(1\le a<b\le 9\), the sorted value is \(10a+b\), and there are \(2\) original strings.
Hence
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
Evaluating the three parts gives
$$S(2)=90+495+2880=3465.$$
As a local multiset example, counts \((c_0,c_1,c_3)=(1,2,1)\) correspond to the sorted value \(113\), and the multiplicity is \(4!/(1!\,2!\,1!)=12\), so that single multiset contributes \(1356\).
The C++, Python, and Java implementations precompute three short tables up to \(n\): factorials, powers of \(10\) modulo the target modulus, and repunits modulo the same modulus. Because \(n=18\), the exact factorial values still fit comfortably in 64-bit arithmetic, so the multinomial weights can be formed exactly before the final modular reduction.
After that, the implementation performs a depth-first search over digits \(1\) through \(9\). At each step it chooses how many copies of the current digit to use, updates the product of factorial denominators, and appends the new repeated-digit block to the current sorted value with
$$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c \pmod{1123455689}.$$
When the search reaches digit \(9\), the remaining unused positions are exactly the zeros. The implementation then computes the multinomial multiplicity, multiplies it by the accumulated sorted value, and adds the result to the answer modulo \(1123455689\).
The search enumerates all nonnegative \(9\)-tuples \((c_1,\dots,c_9)\) with total at most \(n\). By stars and bars, the number of leaves is
$$\binom{n+9}{9}.$$
Each transition uses only constant-time arithmetic, so the total running time is \(O\!\left(\binom{n+9}{9}\right)\). The auxiliary tables use \(O(n)\) space, and the recursion depth is \(9\). For \(n=18\), this means \(\binom{27}{9}=4686825\) terminal multiplicity vectors, which is entirely manageable.
Für jede ganze Zahl \(x\) mit \(0 \le x < 10^n\) betrachten wir ihre \(n\)-stellige Dezimalschreibweise mit führenden Nullen. Diese \(n\) Ziffern werden nicht absteigend, sondern in nichtfallender Reihenfolge sortiert; danach liest man das Ergebnis als gewöhnliche Basis-10-Zahl, sodass führende Nullen automatisch verschwinden. Gesucht ist die Summe aller so entstehenden Werte für \(n=18\), modulo \(1123455689\).
Direktes Durchprobieren aller \(10^{18}\) Fälle ist unmöglich. Entscheidend ist daher, dass der sortierte Wert nur von den Ziffernhäufigkeiten abhängt und nicht von der ursprünglichen Anordnung.
Sei \(S(n)\) die gesuchte Summe über alle \(n\)-stelligen Zeichenketten mit erlaubten führenden Nullen.
Für eine Dezimalfolge sei \(c_d\) die Anzahl der Vorkommen der Ziffer \(d\), wobei \(d \in \{0,1,\dots,9\}\). Dann gilt
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
Sind diese Häufigkeiten fest, dann ist auch das sortierte Bild der Zahl fest. Deshalb kann man über Häufigkeitsvektoren summieren statt über einzelne Zahlen.
Die Implementierungen iterieren nur über \(c_1,\dots,c_9\) und bestimmen die Anzahl der Nullen durch
$$c_0=n-\sum_{d=1}^9 c_d.$$
Das genügt, weil Nullen zwar die Multiplizität des Multimengentyps beeinflussen, im sortierten Ergebnis aber nur einen führenden Nullblock erzeugen, der den Zahlenwert nicht verändert.
Definiere die Repunit-Zahl der Länge \(k\) durch
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$$
Wenn die Ziffer \(d\) genau \(c_d\)-mal vorkommt, dann liefert ihr Block im sortierten Ergebnis den Beitrag \(dR_{c_d}\). Dieser Block muss noch um die Anzahl der rechts davon stehenden Ziffern nach links verschoben werden, also um
$$t_d=\sum_{j=d+1}^9 c_j.$$
Damit lautet der sortierte Wert
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$$
Diese Formel ignoriert führende Nullen automatisch. Sie ist äquivalent dazu, die Ziffernblöcke in aufsteigender Reihenfolge anzuhängen und dabei rekursiv
$$v_{\text{neu}}=v_{\text{alt}}\,10^c+dR_c$$
zu verwenden.
Für eine feste Multimenge \((c_0,\dots,c_9)\) ist die Anzahl verschiedener Ausgangsfolgen der Multinomialkoeffizient
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
Weil die Suche nur die Nichtnull-Ziffern explizit auswählt, ist die Schreibweise
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s,$$
praktisch, also
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$$
Diese Gewichtung zählt auch Folgen, die mit einer Null beginnen. Genau das ist gewünscht, denn die Aufgabenstellung summiert effektiv über alle Zahlen von \(0\) bis \(10^n-1\), also über alle \(n\)-stelligen Folgen mit führenden Nullen.
Sortierter Wert und Multiplizität zusammen ergeben
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
Gesucht ist dann konkret
$$S(18)\bmod 1123455689.$$
Genau so arbeitet auch das Programm: ein Summand pro zulässigem Häufigkeitsvektor, statt eine Schleife über astronomisch viele Rohzahlen.
Für \(n=2\) werden die \(100\) Folgen von \(00\) bis \(99\) nach ihren Ziffernmultimengen gruppiert.
Bei Ziffern \(\{0,d\}\) mit \(1\le d\le 9\) ist der sortierte Wert gleich \(d\), und es gibt \(2\) Ausgangsfolgen: \(0d\) und \(d0\).
Bei \(\{d,d\}\) mit \(1\le d\le 9\) ist der sortierte Wert \(11d\), und es gibt genau \(1\) Ausgangsfolge.
Bei \(\{a,b\}\) mit \(1\le a<b\le 9\) ist der sortierte Wert \(10a+b\), und es gibt \(2\) Ausgangsfolgen.
Daher
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
Die Auswertung liefert
$$S(2)=90+495+2880=3465.$$
Als lokales Beispiel erzeugen die Häufigkeiten \((c_0,c_1,c_3)=(1,2,1)\) den sortierten Wert \(113\), und die Multiplizität beträgt \(4!/(1!\,2!\,1!)=12\). Dieser einzelne Multimengentyp trägt also \(1356\) bei.
Die C++-, Python- und Java-Implementierungen berechnen zunächst drei kurze Tabellen bis \(n\) vor: Fakultäten, Potenzen von \(10\) modulo des Zielmoduls und Repunits modulo desselben Moduls. Weil \(n=18\) gilt, passen die exakten Fakultätswerte noch bequem in 64-Bit-Arithmetik, sodass die Multinomialgewichte zuerst exakt und erst am Ende modular reduziert werden.
Anschließend läuft eine Tiefensuche über die Ziffern \(1\) bis \(9\). In jedem Schritt wird gewählt, wie oft die aktuelle Ziffer verwendet wird; zugleich werden das Produkt der Fakultätsnenner und der aktuelle sortierte Wert aktualisiert. Das Anhängen eines Blocks gleicher Ziffern geschieht mit
$$v_{\text{neu}}=v_{\text{alt}}\,10^c+dR_c \pmod{1123455689}.$$
Wenn die Suche die letzte Ziffer erreicht, sind alle restlichen Plätze automatisch Nullen. Dann berechnet die Implementierung die Multinomial-Multiplizität, multipliziert sie mit dem aufgelaufenen sortierten Wert und addiert den Beitrag modulo \(1123455689\).
Die Suche enumeriert alle nichtnegativen \(9\)-Tupel \((c_1,\dots,c_9)\) mit Gesamtzahl höchstens \(n\). Nach Stars-and-Bars ist die Anzahl der Blätter
$$\binom{n+9}{9}.$$
Jeder Übergang benutzt nur Arithmetik mit konstantem Aufwand, also beträgt die Gesamtlaufzeit \(O\!\left(\binom{n+9}{9}\right)\). Die Hilfstabellen benötigen \(O(n)\) Speicher, die Rekursionstiefe ist \(9\). Für \(n=18\) erhält man \(\binom{27}{9}=4686825\) terminale Häufigkeitsvektoren, was gut beherrschbar ist.
Her \(x\) sayısı için, \(0 \le x < 10^n\) aralığında olmak üzere, sayıyı baştaki sıfırlara izin veren \(n\) basamaklı bir onluk gösterim olarak düşünelim. Sonra bu \(n\) rakamı küçükten büyüğe sıralayıp ortaya çıkan diziyi normal bir onluk tamsayı gibi okuyalım; bu sırada baştaki sıfırlar doğal olarak kaybolur. Amaç, \(n=18\) için elde edilen bütün bu sıralanmış değerlerin toplamını \(1123455689\) modunda bulmaktır.
Doğrudan çözüm \(10^{18}\) girdiyi gezmeyi gerektirir. Esas gözlem şudur: sıralandıktan sonraki sonuç, rakamların ilk dizilişine değil sadece her rakamın kaç kere geçtiğine bağlıdır.
\(S(n)\), baştaki sıfırlara izin verilen tüm \(n\) basamaklı diziler üzerindeki istenen toplam olsun.
Bir onluk dizi için \(c_d\), \(d \in \{0,1,\dots,9\}\) rakamının görülme sayısı olsun. O zaman
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
Bu sayılar bilindiğinde, rakamlar sıralandığında elde edilecek sonuç tamamen belirlenir. Bu yüzden tek tek sayılar yerine rakam çokluk vektörleri üzerinden toplamak yeterlidir.
Uygulamalar \(c_1,\dots,c_9\) değerlerini açıkça dolaşır ve sıfır sayısını
$$c_0=n-\sum_{d=1}^9 c_d$$
ile çıkarır. Bunun sebebi, sıfırların çokluk ağırlığını etkilemesine rağmen sıralanmış tamsayının değerine yalnızca baştaki sıfırlar olarak yansımasıdır.
Uzunluğu \(k\) olan repunit sayısını
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0$$
olarak tanımlayalım.
Rakam \(d\), \(c_d\) kez geçiyorsa sıralı blok katkısı \(dR_{c_d}\) olur. Bu blok, sağında kalan rakam sayısı kadar sola kaydırılmalıdır; yani
$$t_d=\sum_{j=d+1}^9 c_j.$$
Dolayısıyla çokluk vektörünün ürettiği sıralanmış tamsayı
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}$$
şeklindedir. Bu ifade baştaki sıfırları otomatik olarak yok sayar. Aynı fikir, artan rakam sırasıyla blok ekleyen şu yineleme ile de aynıdır:
$$v_{\text{yeni}}=v_{\text{eski}}\,10^c+dR_c.$$
Sabit bir \((c_0,\dots,c_9)\) çokluğu için farklı başlangıç dizilerinin sayısı multinomial katsayıdır:
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
Arama yalnızca sıfır olmayan rakam sayılarını açıkça seçtiği için
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s$$
yazıp
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}$$
biçimini kullanmak uygundur. Bu ağırlık, başında sıfır olan dizileri de sayar. Bu doğrudur; çünkü problem aslında \(0\) ile \(10^n-1\) arasındaki tüm sayıları, yani baştaki sıfırlara izin verilmiş tüm \(n\) basamaklı dizileri kapsar.
Sıralanmış değer ile combinatorik ağırlığı birleştirince
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
elde edilir. Sorunun istediği çıktı ise
$$S(18)\bmod 1123455689$$
değeridir. Böylece astronomik sayıdaki ham girdi yerine, yalnızca izin verilen rakam sayım vektörleri kadar terim toplanır.
\(n=2\) olduğunda \(00\) ile \(99\) arasındaki \(100\) diziyi çokluklarına göre gruplarız.
Rakamlar \(\{0,d\}\) ise, \(1\le d\le 9\), sıralanmış değer \(d\) olur ve \(0d\), \(d0\) olmak üzere \(2\) özgün dizi vardır.
Rakamlar \(\{d,d\}\) ise, \(1\le d\le 9\), sıralanmış değer \(11d\) olur ve yalnızca \(1\) özgün dizi vardır.
Rakamlar \(\{a,b\}\) ise, \(1\le a<b\le 9\), sıralanmış değer \(10a+b\) olur ve \(2\) özgün dizi vardır.
Böylece
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
Bu da
$$S(2)=90+495+2880=3465$$
sonucunu verir. Yerel bir örnek olarak \((c_0,c_1,c_3)=(1,2,1)\) sayımları sıralanınca \(113\) oluşur; bu çokluğun permütasyon sayısı \(4!/(1!\,2!\,1!)=12\) olduğundan tek başına \(1356\) katkı yapar.
C++, Python ve Java uygulamaları önce \(n\)'e kadar üç kısa tablo hazırlar: faktöriyeller, hedef modüle göre \(10\) kuvvetleri ve yine aynı modüle göre repunit değerleri. \(n=18\) olduğundan faktöriyel büyüklükleri 64 bit içinde güvenle tutulabildiği için multinomial ağırlıklar son mod alma adımına kadar tam olarak hesaplanabilir.
Daha sonra uygulama, \(1\) ile \(9\) arasındaki rakamlar üzerinde derinlik öncelikli bir arama yapar. Her adımda mevcut rakamdan kaç tane kullanılacağı seçilir; buna paralel olarak faktöriyel payda çarpımı ve birikmiş sıralı değer güncellenir. Aynı rakamdan oluşan yeni blok
$$v_{\text{yeni}}=v_{\text{eski}}\,10^c+dR_c \pmod{1123455689}$$
kuralıyla eklenir. Arama son rakama ulaştığında kalan tüm boş yerler sıfır demektir; bu anda multinomial ağırlık hesaplanır, birikmiş değerle çarpılır ve sonuç moda göre toplama eklenir.
Arama, toplamı en fazla \(n\) olan tüm negatif olmayan \(9\)-li vektörleri \((c_1,\dots,c_9)\) gezer. Stars and bars sonucuna göre yaprak sayısı
$$\binom{n+9}{9}$$
olur. Her geçiş sabit zamanlı aritmetik kullandığından toplam çalışma süresi \(O\!\left(\binom{n+9}{9}\right)\) olur. Yardımcı tablolar \(O(n)\) alan kaplar, özyineleme derinliği \(9\)'dur. \(n=18\) için \(\binom{27}{9}=4686825\) terminal çokluk vektörü vardır; bu sayı rahatça yönetilebilir.
Para cada entero \(x\) con \(0 \le x < 10^n\), se toma su escritura decimal de longitud \(n\) permitiendo ceros a la izquierda. Después se ordenan esos \(n\) dígitos en orden no decreciente y el resultado se lee como un entero decimal ordinario, de modo que los ceros iniciales desaparecen automáticamente. La tarea consiste en sumar todos esos valores ordenados para \(n=18\), módulo \(1123455689\).
Un recorrido directo exigiría examinar \(10^{18}\) entradas. La observación decisiva es que el valor final depende solo de cuántas veces aparece cada dígito, no del orden original.
Sea \(S(n)\) la suma pedida sobre todas las cadenas decimales de longitud \(n\) con ceros iniciales permitidos.
Para una cadena decimal, sea \(c_d\) el número de apariciones del dígito \(d\), con \(d \in \{0,1,\dots,9\}\). Entonces
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
Una vez fijadas estas cantidades, el valor ordenado queda completamente determinado. Por eso conviene sumar por vectores de multiplicidades y no por números individuales.
Las implementaciones recorren explícitamente \(c_1,\dots,c_9\) y deducen la cantidad de ceros mediante
$$c_0=n-\sum_{d=1}^9 c_d.$$
Esto basta porque los ceros afectan al peso combinatorio del multiconjunto, pero en el entero ordenado solo forman un bloque inicial de ceros que no cambia el valor numérico.
Definimos el repunit de longitud \(k\) por
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$$
Si el dígito \(d\) aparece \(c_d\) veces, su bloque aporta \(dR_{c_d}\). Ese bloque debe desplazarse a la izquierda según el número de dígitos que quedan a su derecha, es decir,
$$t_d=\sum_{j=d+1}^9 c_j.$$
Así, el valor ordenado asociado al vector de cuentas es
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$$
La fórmula ignora automáticamente el bloque inicial de ceros. Es equivalente a ir concatenando bloques de dígitos iguales en orden creciente mediante
$$v_{\text{nuevo}}=v_{\text{anterior}}\,10^c+dR_c.$$
Para un multiconjunto fijo \((c_0,\dots,c_9)\), el número de cadenas originales distintas es el coeficiente multinomial
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
Como la búsqueda elige de forma explícita solo las cuentas no nulas, resulta útil escribir
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s,$$
y entonces
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$$
Este peso incluye también las cadenas que empiezan con cero. Eso es correcto, porque el problema recorre todos los enteros desde \(0\) hasta \(10^n-1\), o de manera equivalente todas las cadenas de longitud \(n\) con ceros iniciales permitidos.
Al combinar el valor ordenado con su multiplicidad obtenemos
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
La respuesta pedida por el problema es
$$S(18)\bmod 1123455689.$$
La fórmula coincide exactamente con la lógica combinatoria de las implementaciones: un término por cada vector admisible de cuentas, en lugar de un término por cada una de las \(10^{18}\) entradas crudas.
Cuando \(n=2\), se agrupan las \(100\) cadenas de \(00\) a \(99\) por sus multiconjuntos de dígitos.
Si los dígitos son \(\{0,d\}\) con \(1\le d\le 9\), el valor ordenado es \(d\) y hay \(2\) cadenas originales: \(0d\) y \(d0\).
Si los dígitos son \(\{d,d\}\) con \(1\le d\le 9\), el valor ordenado es \(11d\) y solo hay \(1\) cadena original.
Si los dígitos son \(\{a,b\}\) con \(1\le a<b\le 9\), el valor ordenado es \(10a+b\) y hay \(2\) cadenas originales.
Por tanto,
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
Al evaluar las tres partes resulta
$$S(2)=90+495+2880=3465.$$
Como ejemplo local, las cuentas \((c_0,c_1,c_3)=(1,2,1)\) producen el valor ordenado \(113\), y su multiplicidad es \(4!/(1!\,2!\,1!)=12\), así que ese multiconjunto aporta \(1356\).
Las implementaciones en C++, Python y Java precalculan tres tablas cortas hasta \(n\): factoriales, potencias de \(10\) módulo el módulo objetivo y repunits módulo el mismo valor. Como \(n=18\), los factoriales exactos siguen cabiendo con holgura en aritmética de 64 bits, de modo que los pesos multinomiales se forman exactamente antes de reducir módulo \(1123455689\).
Después, la implementación hace una búsqueda en profundidad sobre los dígitos del \(1\) al \(9\). En cada paso decide cuántas copias usar del dígito actual, actualiza el producto de factoriales del denominador y añade el nuevo bloque repetido al valor ordenado acumulado mediante
$$v_{\text{nuevo}}=v_{\text{anterior}}\,10^c+dR_c \pmod{1123455689}.$$
Cuando la búsqueda alcanza el último dígito, las posiciones no usadas restantes corresponden exactamente a los ceros. Entonces se calcula la multiplicidad multinomial, se multiplica por el valor ordenado acumulado y se añade la contribución a la respuesta modular.
La búsqueda enumera todos los \(9\)-tuplos no negativos \((c_1,\dots,c_9)\) cuya suma total es como máximo \(n\). Por stars and bars, el número de hojas es
$$\binom{n+9}{9}.$$
Cada transición usa solo aritmética de tiempo constante, así que el coste total es \(O\!\left(\binom{n+9}{9}\right)\). Las tablas auxiliares ocupan \(O(n)\) memoria y la profundidad de recursión es \(9\). Para \(n=18\), esto significa \(\binom{27}{9}=4686825\) vectores terminales de multiplicidades.
对每个满足 \(0 \le x < 10^n\) 的整数 \(x\)，先把它看成一个长度恰好为 \(n\) 的十进制字符串，允许前导零。然后把这 \(n\) 个数字按非降序排列，再把结果当作普通十进制整数读取，因此前导零会自然消失。题目要求的是 \(n=18\) 时所有这些“排序后整数”的总和，并对 \(1123455689\) 取模。
如果逐个枚举，就要处理 \(10^{18}\) 个输入，不可能直接完成。真正有用的观察是：排序后的结果只取决于每个数字出现了多少次，而与原始顺序无关。
记 \(S(n)\) 为允许前导零的所有 \(n\) 位十进制串所对应的目标总和。
对一个十进制串，设 \(c_d\) 表示数字 \(d\) 的出现次数，其中 \(d \in \{0,1,\dots,9\}\)。于是有
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
一旦这些计数固定，排序后的整数也就唯一确定。因此求和时没有必要按原始数字串逐个处理，只需要按“数字多重集”分类即可。
实现中显式枚举的是 \(c_1,\dots,c_9\)，而零的个数由
$$c_0=n-\sum_{d=1}^9 c_d$$
自动确定。这样做成立的原因是：零虽然会影响同一多重集对应的原始排列数，但在排序后的整数里只会出现在最前面，不改变最终数值。
定义长度为 \(k\) 的 repunit 为
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$$
如果数字 \(d\) 出现 \(c_d\) 次，那么在排序结果中，它形成的连续块对应数值 \(dR_{c_d}\)。这个块还要根据右侧还有多少位数字整体左移，其位数正是
$$t_d=\sum_{j=d+1}^9 c_j.$$
因此，与计数向量对应的排序后整数可以写成
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$$
这个公式自动忽略了开头的零块。它也等价于按数字从小到大逐块拼接，满足递推关系
$$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c.$$
也就是说，当前已经拼好的部分整体左移 \(c\) 位，再把 \(c\) 个相同数字组成的块接到末尾。
对于固定的数字计数 \((c_0,\dots,c_9)\)，具有这些数字的原始字符串个数是多项式系数
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
由于搜索时只显式决定非零数字的数量，写成
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s$$
更方便，于是
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$$
这个权重也把以零开头的字符串算进去，这正是题意所需要的，因为题目覆盖的是从 \(0\) 到 \(10^n-1\) 的所有整数，等价于所有允许前导零的 \(n\) 位字符串。
把排序后的值和其组合重数合在一起，得到
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
题目真正要求的是
$$S(18)\bmod 1123455689.$$
这正是实现所采用的数学结构：每个合法的计数向量贡献一个项，而不是面对无法承受的 \(10^{18}\) 个原始输入。
当 \(n=2\) 时，所有输入就是从 \(00\) 到 \(99\) 的 \(100\) 个两位字符串。按照数字多重集分类后，只剩下几种情况。
若数字集合是 \(\{0,d\}\)，其中 \(1\le d\le 9\)，排序后整数为 \(d\)，原始字符串有 \(0d\) 与 \(d0\) 两个。
若数字集合是 \(\{d,d\}\)，其中 \(1\le d\le 9\)，排序后整数为 \(11d\)，原始字符串只有一个。
若数字集合是 \(\{a,b\}\)，其中 \(1\le a<b\le 9\)，排序后整数为 \(10a+b\)，原始字符串有两个。
因此
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
把三部分分别算出来，就得到
$$S(2)=90+495+2880=3465.$$
再看一个局部多重集例子：若 \((c_0,c_1,c_3)=(1,2,1)\)，排序后整数是 \(113\)，而对应的原始排列数是 \(4!/(1!\,2!\,1!)=12\)，因此这一类输入的总贡献是 \(1356\)。这个例子清楚展示了“先按计数归类，再乘以排列数”的核心思想。
C++、Python 和 Java 实现都会先预计算三张很短的表：到 \(n\) 为止的阶乘表、模 \(1123455689\) 的 \(10\) 的幂，以及同模数下的 repunit 值。由于这里 \(n=18\)，相关阶乘仍然可以安全地保存在 64 位整数范围内，因此组合权重可以先精确算出，再在最后一步取模。
随后，实现对数字 \(1\) 到 \(9\) 做一次深度优先搜索。每走到一个数字，就决定当前数字要放多少个，同时更新分母中的阶乘乘积，并用
$$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c \pmod{1123455689}$$
把新的重复数字块接到当前排序值后面。当搜索处理完 \(9\) 以后，所有剩余位置就都是零；这时实现计算该计数向量的多项式系数，把它与当前排序值相乘，再累加到最终答案中。
搜索枚举的是所有满足总和不超过 \(n\) 的非负 \(9\) 元组 \((c_1,\dots,c_9)\)。根据 stars and bars，终端叶子数为
$$\binom{n+9}{9}.$$
每一步只进行常数次算术运算，因此总时间复杂度是 \(O\!\left(\binom{n+9}{9}\right)\)。辅助表需要 \(O(n)\) 空间，递归深度固定为 \(9\)。当 \(n=18\) 时，叶子数量是 \(\binom{27}{9}=4686825\)，完全在可处理范围内。
Для каждого целого числа \(x\) из диапазона \(0 \le x < 10^n\) рассмотрим его десятичную запись длины \(n\), разрешая ведущие нули. Затем отсортируем эти \(n\) цифр по неубыванию и прочитаем результат как обычное десятичное число; ведущие нули при этом автоматически исчезнут. Требуется найти сумму всех таких отсортированных значений при \(n=18\) по модулю \(1123455689\).
Прямой перебор потребовал бы обработать \(10^{18}\) входов. Главное наблюдение состоит в том, что итоговое значение определяется только кратностями цифр, а не их исходным порядком.
Обозначим через \(S(n)\) искомую сумму по всем десятичным строкам длины \(n\) с разрешенными ведущими нулями.
Для одной десятичной строки пусть \(c_d\) означает число вхождений цифры \(d\), где \(d \in \{0,1,\dots,9\}\). Тогда
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
Когда эти количества заданы, отсортированное значение уже полностью определено. Поэтому суммирование можно вести по векторам кратностей, а не по отдельным числам.
Реализации явно перебирают только \(c_1,\dots,c_9\), а число нулей получают из
$$c_0=n-\sum_{d=1}^9 c_d.$$
Этого достаточно, потому что нули влияют на комбинаторический вес мультимножества, но в отсортированном числе образуют лишь начальный блок нулей, не меняющий числового значения.
Определим repunit длины \(k\) как
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$$
Если цифра \(d\) встречается \(c_d\) раз, то ее блок в отсортированной записи дает вклад \(dR_{c_d}\). Этот блок нужно сдвинуть влево на число цифр справа от него, то есть на
$$t_d=\sum_{j=d+1}^9 c_j.$$
Поэтому отсортированное значение для заданного вектора кратностей равно
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$$
Формула автоматически игнорирует ведущий блок нулей. Она эквивалентна последовательному добавлению блоков одинаковых цифр в возрастающем порядке по правилу
$$v_{\text{нов}}=v_{\text{стар}}\,10^c+dR_c.$$
Для фиксированного мультимножества \((c_0,\dots,c_9)\) число различных исходных строк равно мультиномиальному коэффициенту
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
Так как поиск явно выбирает только количества ненулевых цифр, удобно записать
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s,$$
и тогда
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$$
Этот вес включает и строки, начинающиеся с нуля. Именно это и нужно, потому что задача фактически суммирует по всем целым от \(0\) до \(10^n-1\), то есть по всем строкам длины \(n\) с разрешенными ведущими нулями.
Объединяя отсортированное значение и его кратность, получаем
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
В задаче требуется найти
$$S(18)\bmod 1123455689.$$
Именно эта формула и реализована программно: один вклад на каждый допустимый вектор кратностей, а не на каждое из \(10^{18}\) исходных чисел.
При \(n=2\) мы группируем \(100\) строк от \(00\) до \(99\) по их мультимножествам цифр.
Если цифры равны \(\{0,d\}\), где \(1\le d\le 9\), то отсортированное значение равно \(d\), а исходных строк две: \(0d\) и \(d0\).
Если цифры равны \(\{d,d\}\), где \(1\le d\le 9\), то отсортированное значение равно \(11d\), а исходная строка только одна.
Если цифры равны \(\{a,b\}\), где \(1\le a<b\le 9\), то отсортированное значение равно \(10a+b\), а исходных строк две.
Следовательно,
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
После вычисления трех частей получается
$$S(2)=90+495+2880=3465.$$
Локальный пример: кратности \((c_0,c_1,c_3)=(1,2,1)\) дают отсортированное число \(113\), а число исходных перестановок равно \(4!/(1!\,2!\,1!)=12\). Значит, этот мультимножественный класс дает вклад \(1356\).
Реализации на C++, Python и Java сначала предварительно строят три короткие таблицы до \(n\): факториалы, степени \(10\) по модулю \(1123455689\) и repunit-значения по тому же модулю. Поскольку здесь \(n=18\), точные значения факториалов еще удобно помещаются в 64-битную арифметику, поэтому мультиномиальные веса можно вычислять точно и сокращать по модулю только в конце.
После этого выполняется поиск в глубину по цифрам от \(1\) до \(9\). На каждом шаге выбирается, сколько раз используется текущая цифра, обновляется произведение факториалов в знаменателе и к накопленному отсортированному значению добавляется новый блок одинаковых цифр по формуле
$$v_{\text{нов}}=v_{\text{стар}}\,10^c+dR_c \pmod{1123455689}.$$
Когда поиск доходит до последней цифры, все неиспользованные позиции автоматически являются нулями. Затем вычисляется мультиномиальный вес, умножается на накопленное отсортированное значение и добавляется к ответу по модулю.
Поиск перечисляет все неотрицательные \(9\)-кортежи \((c_1,\dots,c_9)\) с суммой не больше \(n\). По формуле stars and bars число листьев равно
$$\binom{n+9}{9}.$$
Каждый переход использует лишь арифметику постоянной стоимости, поэтому общая сложность равна \(O\!\left(\binom{n+9}{9}\right)\). Вспомогательные таблицы занимают \(O(n)\) памяти, глубина рекурсии равна \(9\). Для \(n=18\) это дает \(\binom{27}{9}=4686825\) конечных векторов кратностей.
لكل عدد صحيح \(x\) يحقق \(0 \le x < 10^n\)، نكتبه على صورة سلسلة عشرية طولها \(n\) مع السماح بالأصفار البادئة. بعد ذلك نرتب هذه الأرقام ترتيبًا غير تنازلي، ثم نقرأ الناتج بوصفه عددًا عشريًا عاديًا، فتختفي الأصفار في البداية تلقائيًا. المطلوب هو مجموع كل هذه القيم المرتبة عندما \(n=18\)، بترديد \(1123455689\).
الحل المباشر يتطلب المرور على \(10^{18}\) حالة، وهذا غير عملي. الفكرة الحاسمة هي أن القيمة بعد الترتيب لا تعتمد على ترتيب الأرقام الأصلي، بل تعتمد فقط على عدد مرات ظهور كل رقم.
لنرمز بـ \(S(n)\) إلى المجموع المطلوب على جميع السلاسل العشرية ذات الطول \(n\) مع السماح بالأصفار البادئة.
لسلسلة عشرية واحدة، ليكن \(c_d\) هو عدد مرات ظهور الرقم \(d\)، حيث \(d \in \{0,1,\dots,9\}\). عندئذ
$$c_0+c_1+\cdots+c_9=n,\qquad c_d\ge 0.$$
بمجرد معرفة هذه الأعداد، تصبح القيمة بعد الترتيب محددة بالكامل. لذلك يمكننا الجمع على متجهات التكرار بدلًا من الجمع على الأعداد المفردة.
تقوم التطبيقات بتعداد \(c_1,\dots,c_9\) صراحةً، ثم تستنتج عدد الأصفار من
$$c_0=n-\sum_{d=1}^9 c_d.$$
وهذا كافٍ لأن الأصفار تؤثر في الوزن التركيبي للتعددية، لكنها بعد الترتيب تظهر فقط ككتلة من الأصفار في البداية، ولا تغيّر القيمة العددية النهائية.
نعرّف عدد repunit بطول \(k\) على أنه
$$R_k=1+10+\cdots+10^{k-1}=\frac{10^k-1}{9},\qquad R_0=0.$$
إذا ظهر الرقم \(d\) عدد \(c_d\) من المرات، فإن كتلته في العدد المرتب تساهم بمقدار \(dR_{c_d}\). ويجب إزاحة هذه الكتلة إلى اليسار بعدد الأرقام الواقعة على يمينها، أي
$$t_d=\sum_{j=d+1}^9 c_j.$$
لذلك فإن القيمة المرتبة الموافقة لمتجه التكرارات هي
$$V(c_1,\dots,c_9)=\sum_{d=1}^9 d\,R_{c_d}\,10^{t_d}.$$
هذه الصيغة تتجاهل كتلة الأصفار البادئة تلقائيًا. وهي مكافئة أيضًا لبناء العدد على مراحل بإلحاق كتل الأرقام المتساوية بترتيب تصاعدي وفق العلاقة
$$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c.$$
من أجل تعددية ثابتة \((c_0,\dots,c_9)\)، يكون عدد السلاسل الأصلية المختلفة هو المعامل متعدد الحدود
$$W(c_0,\dots,c_9)=\frac{n!}{c_0!\,c_1!\cdots c_9!}.$$
وبما أن البحث يختار فقط تكرارات الأرقام غير الصفرية صراحةً، فمن المناسب أن نكتب
$$s=\sum_{d=1}^9 c_d,\qquad c_0=n-s,$$
ومن ثم
$$W=\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}.$$
هذا الوزن يشمل السلاسل التي تبدأ بصفر أيضًا، وهذا صحيح تمامًا لأن المسألة تغطي جميع الأعداد من \(0\) إلى \(10^n-1\)، أي جميع السلاسل ذات الطول \(n\) مع السماح بالأصفار البادئة.
عند جمع القيمة المرتبة مع وزنها التركيبي نحصل على
$$\boxed{S(n)=\sum_{\substack{c_1,\dots,c_9\ge 0\\c_1+\cdots+c_9\le n}}\frac{n!}{(n-s)!\prod_{d=1}^9 c_d!}\,V(c_1,\dots,c_9),\qquad s=\sum_{d=1}^9 c_d.}$$
والكمية المطلوبة في المسألة هي
$$S(18)\bmod 1123455689.$$
هذه هي بالضبط البنية الرياضية التي تعتمد عليها التطبيقات: حد واحد لكل متجه تكرار مسموح، بدلًا من حد لكل إدخال خام من بين \(10^{18}\) إدخالًا.
عندما \(n=2\)، نعيد تجميع السلاسل المئة من \(00\) إلى \(99\) بحسب تعددية الأرقام فيها.
إذا كانت الأرقام هي \(\{0,d\}\) حيث \(1\le d\le 9\)، فإن القيمة بعد الترتيب هي \(d\)، وهناك سلسلتان أصليتان: \(0d\) و\(d0\).
إذا كانت الأرقام هي \(\{d,d\}\) حيث \(1\le d\le 9\)، فإن القيمة بعد الترتيب هي \(11d\)، وهناك سلسلة أصلية واحدة فقط.
إذا كانت الأرقام هي \(\{a,b\}\) حيث \(1\le a<b\le 9\)، فإن القيمة بعد الترتيب هي \(10a+b\)، وهناك سلسلتان أصليتان.
إذن
$$S(2)=2\sum_{d=1}^9 d+\sum_{d=1}^9 11d+2\sum_{1\le a<b\le 9}(10a+b).$$
وبحساب هذه الأجزاء نحصل على
$$S(2)=90+495+2880=3465.$$
ومثال محلي مفيد: التكرارات \((c_0,c_1,c_3)=(1,2,1)\) تعطي العدد المرتب \(113\)، وعدد ترتيباتها الأصلية هو \(4!/(1!\,2!\,1!)=12\)، ولذلك تسهم هذه الفئة وحدها بمقدار \(1356\).
تقوم تطبيقات C++ وPython وJava أولًا بحساب ثلاث جداول قصيرة حتى \(n\): جدول المضروبات، وجدول قوى \(10\) بترديد الهدف، وجدول أعداد repunit بالترديد نفسه. وبما أن \(n=18\)، فإن قيم المضروبات الدقيقة ما زالت تقع بأمان داخل الحساب ذي 64 بت، ولذلك يمكن تكوين الأوزان متعددة الحدود بدقة قبل الاختزال النهائي بترديد \(1123455689\).
بعد ذلك تنفذ الشيفرة بحثًا عمقيًا على الأرقام من \(1\) إلى \(9\). في كل خطوة تختار عدد النسخ من الرقم الحالي، وتحدّث حاصل ضرب المضروبات في المقام، وتضيف الكتلة الجديدة من الرقم المكرر إلى القيمة المرتبة المتراكمة وفق
$$v_{\text{new}}=v_{\text{old}}\,10^c+dR_c \pmod{1123455689}.$$
وعندما يصل البحث إلى الرقم الأخير، تكون جميع الخانات المتبقية أصفارًا بالضرورة. عندها يُحسب الوزن متعدد الحدود، ويُضرب في القيمة المرتبة المتراكمة، ثم تُضاف المساهمة إلى الجواب النهائي.
يعدّد البحث جميع المتجهات غير السالبة ذات التسع مركبات \((c_1,\dots,c_9)\) التي لا يزيد مجموعها على \(n\). وبحسب stars and bars فإن عدد الأوراق النهائية هو
$$\binom{n+9}{9}.$$
كل انتقال يستخدم حسابًا ثابت الكلفة، لذا فإن الزمن الكلي هو \(O\!\left(\binom{n+9}{9}\right)\). أما الجداول المساعدة فتحتاج إلى \(O(n)\) من الذاكرة، وعمق الاستدعاء يساوي \(9\). وعند \(n=18\) يصبح عدد المتجهات النهائية \(\binom{27}{9}=4686825\)، وهو حجم عملي تمامًا.