For each pair \((s,m)\), let \(f(s,m)\) be the \(m\)-th positive integer whose decimal digits sum to \(s\), with numbers ordered in the usual increasing order. The target quantity is
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
For the full input range, both the digit sums and the occurrence ranks are far too large for brute force. The solution therefore counts how many admissible numbers lie in each length block, identifies the block containing the required rank, and then reconstructs the number digit by digit.
The key simplification is to replace each digit by its deficit from \(9\). That turns the digit-sum constraint into a bounded composition problem, which can be counted exactly with inclusion-exclusion.
Suppose an \(\ell\)-digit number has decimal digits \(a_1,\dots,a_\ell\). Define deficits
$$b_i=9-a_i.$$
Then every \(b_i\) lies in \(\{0,\dots,9\}\), and
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
The first digit cannot be zero, so \(a_1\ge 1\), which means
$$b_1\in\{0,\dots,8\}.$$
All remaining deficits may still range from \(0\) to \(9\). Therefore an \(\ell\)-digit number with digit sum \(s\) is equivalent to choosing \(b_1,\dots,b_\ell\) with one slightly tighter bound on the first coordinate.
The smallest feasible length is
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
because even the largest possible \(\ell\)-digit number contributes only \(9\ell\) to the digit sum.
Let \(A(d,t)\) denote the number of length-\(d\) strings over \(\{0,\dots,9\}\) whose digits sum to \(t\). Without the upper bound \(9\), stars and bars gives \(\binom{d+t-1}{t}\). To enforce the upper bound, subtract cases where one or more coordinates are at least \(10\). The resulting exact formula is
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
This is the counting engine used throughout the algorithm. The values can be enormous, so the implementation evaluates them with arbitrary-precision integers instead of reducing them modulo \(10^9+7\).
Let \(C_\ell(s)\) be the number of positive \(\ell\)-digit integers whose digit sum is \(s\). Once the first deficit \(b_1\) is chosen, the remaining \(\ell-1\) positions form an unrestricted bounded composition. Hence
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
Numbers with fewer digits are always smaller than numbers with more digits, so the desired occurrence rank \(m\) lies in the first length \(\ell\) satisfying
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$$
After that, the rank inside the chosen block is simply \(m\) minus the total contribution of all shorter lengths.
Now suppose \(r\) positions remain to be filled and the remaining deficit to distribute is \(D\). If the next digit has deficit \(b\), then the number of valid completions is
$$A(r-1,D-b).$$
To preserve increasing numeric order, candidate digits are tested from smallest to largest. In terms of deficits, that means testing from largest to smallest. Whenever the target rank exceeds the size of a whole block, that block is skipped and its size is subtracted from the rank. The first block not skipped determines the next digit.
If \(D=0\), all remaining digits must be \(9\). More generally, the lexicographically last block is the block beginning with a run of \(9\)s. If \(q\) leading \(9\)s are fixed while \(r\) positions remain, then the surviving suffix count is
$$A(r-q,D),$$
so the number of admissible suffixes that come before that block is
$$A(r,D)-A(r-q,D).$$
This monotone quantity is why the implementation can binary-search the length of a leading run of \(9\)s and append that run in one jump.
The smallest feasible length is \(\lceil 10/9\rceil=2\). The two-digit numbers with digit sum \(10\) are
$$19,28,37,46,55,64,73,82,91,$$
so \(C_2(10)=9\). Therefore the 10th occurrence does not lie in the two-digit block; it is the first element of the three-digit block.
For \(\ell=3\), the deficit is
$$\Delta=27-10=17.$$
Trying first digit \(1\) means first deficit \(8\), leaving deficit \(9\) across the last two digits. The number of completions is
$$A(2,9)=10,$$
so rank \(1\) already lies in that first block. Thus the leading digit is \(1\). Among the remaining two-digit suffixes with digit sum \(9\), the smallest is \(09\), so the first three-digit number with total digit sum \(10\) is \(109\). Hence
$$f(10,10)=109.$$
The C++, Python, and Java implementations all follow the same mathematical pipeline. First, they evaluate exact combinatorial counts for bounded digit sums using arbitrary-precision integers, because the intermediate ranks are much larger than machine integers. Second, they accumulate length counts until the target occurrence rank enters one specific length block. Third, they reconstruct the required number digit by digit by repeatedly asking how many completions each candidate next digit allows.
The number itself is never materialized as a gigantic decimal integer. Instead, the implementation keeps the constructed value modulo \(10^9+7\) and updates it through the recurrence \(x\mapsto 10x+d\). When an entire run of \(9\)s is known at once, it appends that run with
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}.$$
Finally, the outer summation evaluates the procedure for each \(n\) with \(s=n^3\) and occurrence rank \(n^4\). The C++ implementation optionally partitions that outer loop across threads, while the Python and Java implementations use the same logic serially.
For one query \(f(s,m)\), suppose the selected number has length \(\ell\). The length-location phase evaluates \(C_t(s)\) for consecutive lengths \(t\) from \(\lceil s/9\rceil\) up to \(\ell\). The unranking phase performs \(O(\ell)\) digit decisions, with a constant number of bounded-composition counts at each step and an occasional \(O(\log \ell)\) binary search when jumping across a run of \(9\)s.
The dominant arithmetic cost comes from the inclusion-exclusion formula for \(A(d,t)\), which contains \(O(\lfloor t/10\rfloor+1)\) terms and uses big-integer binomial coefficients. Memory usage is modest: apart from the big integers storing counts and ranks, only a small amount of state is maintained. In practice this is fast enough for the full sum up to \(k=10^4\), especially when the outer loop is parallelized.
Für jedes Paar \((s,m)\) sei \(f(s,m)\) die \(m\)-te positive Zahl, deren Dezimalziffern die Summe \(s\) haben; geordnet wird nach der üblichen aufsteigenden Zahlenreihenfolge. Gesucht ist
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
Im vollen Parameterbereich sind sowohl die Ziffernsummen als auch die Ränge viel zu groß für brute force. Deshalb zählt die Lösung zuerst, wie viele zulässige Zahlen in jedem Längenblock liegen, bestimmt den Block mit dem gesuchten Rang und rekonstruiert anschließend die Zahl Ziffer für Ziffer.
Die entscheidende Vereinfachung besteht darin, jede Ziffer durch ihren Abstand zu \(9\) zu ersetzen. Dadurch wird die Ziffernsummenbedingung zu einem Problem über beschränkte Kompositionen, das sich mit Inklusion-Exklusion exakt zählen lässt.
Hat eine \(\ell\)-stellige Zahl die Ziffern \(a_1,\dots,a_\ell\), so definieren wir Defizite durch
$$b_i=9-a_i.$$
Dann gilt \(b_i\in\{0,\dots,9\}\) und
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
Die erste Ziffer darf nicht \(0\) sein, also ist \(a_1\ge 1\) und damit
$$b_1\in\{0,\dots,8\}.$$
Alle übrigen Defizite dürfen weiterhin zwischen \(0\) und \(9\) liegen. Eine \(\ell\)-stellige Zahl mit Ziffernsumme \(s\) entspricht daher einer Wahl von \(b_1,\dots,b_\ell\) mit einer etwas strengeren Schranke nur in der ersten Koordinate.
Die kleinste mögliche Länge ist
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
denn selbst wenn alle \(\ell\) Ziffern gleich \(9\) sind, beträgt die Ziffernsumme höchstens \(9\ell\).
Sei \(A(d,t)\) die Anzahl der Folgen der Länge \(d\) über \(\{0,\dots,9\}\), deren Ziffernsumme \(t\) ist. Ohne die obere Schranke \(9\) liefert Stars-and-Bars den Wert \(\binom{d+t-1}{t}\). Um die Schranke zu erzwingen, werden alle Fälle abgezogen, in denen eine oder mehrere Koordinaten mindestens \(10\) sind. Das ergibt die exakte Formel
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
Diese Funktion ist der Zählkern des gesamten Verfahrens. Da die Werte extrem groß werden können, verwendet die Implementierung Ganzzahlen mit beliebiger Präzision und nicht bloß Rechnungen modulo \(10^9+7\).
Sei \(C_\ell(s)\) die Anzahl positiver \(\ell\)-stelliger Zahlen mit Ziffernsumme \(s\). Ist das erste Defizit \(b_1\) fest gewählt, dann bilden die restlichen \(\ell-1\) Positionen eine unbeschränkte beschränkte Komposition. Deshalb gilt
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
Zahlen mit weniger Stellen sind immer kleiner als Zahlen mit mehr Stellen. Der gesuchte Rang \(m\) liegt also in der ersten Länge \(\ell\), für die
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m$$
erfüllt ist. Danach erhält man den Rang innerhalb des gewählten Blocks, indem man die Beiträge aller kürzeren Längen von \(m\) abzieht.
Angenommen, es sind noch \(r\) Positionen zu füllen und das verbleibende Defizit ist \(D\). Hat die nächste Ziffer das Defizit \(b\), dann ist die Anzahl möglicher Fortsetzungen gleich
$$A(r-1,D-b).$$
Um die aufsteigende Zahlenreihenfolge zu respektieren, testet man Kandidatenziffern von klein nach groß. In Defiziten ausgedrückt bedeutet das: von groß nach klein. Wenn der Zielrang größer als ein ganzer Block ist, wird dieser Block übersprungen und seine Größe vom Rang abgezogen. Der erste Block, der nicht übersprungen wird, bestimmt die nächste Ziffer.
Falls \(D=0\), müssen alle restlichen Ziffern gleich \(9\) sein. Allgemeiner ist der lexikographisch letzte Block der Block, der mit einer Folge von \(9\)en beginnt. Werden bei noch \(r\) freien Positionen die ersten \(q\) Stellen als \(9\) festgelegt, dann bleiben
$$A(r-q,D)$$
zulässige Suffixe übrig, und davor liegen
$$A(r,D)-A(r-q,D)$$
gültige Suffixe. Wegen dieser Monotonie kann die Implementierung die Länge eines führenden \(9\)-Blocks per binärer Suche bestimmen und den ganzen Block auf einmal anhängen.
Die kleinste mögliche Länge ist \(\lceil 10/9\rceil=2\). Die zweistelligen Zahlen mit Ziffernsumme \(10\) sind
$$19,28,37,46,55,64,73,82,91,$$
also ist \(C_2(10)=9\). Die 10. Vorkommensstelle liegt daher nicht im zweistelligen Block, sondern als erstes Element im dreistelligen Block.
Für \(\ell=3\) ist das Defizit
$$\Delta=27-10=17.$$
Beginnt die Zahl mit \(1\), dann ist das erste Defizit \(8\), und für die letzten beiden Stellen bleibt ein Defizit von \(9\). Die Anzahl der Ergänzungen ist
$$A(2,9)=10.$$
Rang \(1\) liegt also bereits im ersten Block, somit ist die führende Ziffer \(1\). Unter den verbleibenden zweistelligen Suffixen mit Ziffernsumme \(9\) ist das kleinste \(09\). Folglich ist die erste dreistellige Zahl mit Ziffernsumme \(10\) gleich \(109\), also
$$f(10,10)=109.$$
Die Implementierungen in C++, Python und Java folgen alle derselben mathematischen Pipeline. Zuerst berechnen sie exakte kombinatorische Zählwerte für beschränkte Ziffernsummen mit Ganzzahlen beliebiger Präzision, weil die Zwischenränge viel größer sind als Maschinenzahlen. Danach summieren sie Längenblöcke auf, bis der Zielrang in genau einen Block hinein fällt. Anschließend rekonstruieren sie die gesuchte Zahl Ziffer für Ziffer, indem sie wiederholt fragen, wie viele Fortsetzungen jede mögliche nächste Ziffer zulässt.
Die Zahl selbst wird nie als riesige Dezimalzahl vollständig aufgebaut. Stattdessen hält die Implementierung nur den bisher konstruierten Wert modulo \(10^9+7\) und aktualisiert ihn über \(x\mapsto 10x+d\). Wenn eine ganze Folge von \(9\)en auf einmal feststeht, wird sie mit
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}$$
in einem Schritt angehängt. Schließlich wird dieses Verfahren für jedes \(n\) mit \(s=n^3\) und Rang \(n^4\) ausgewertet. Die C++-Implementierung kann diese äußere Schleife optional auf mehrere Threads verteilen; die Python- und Java-Implementierungen verwenden dieselbe Mathematik seriell.
Für eine einzelne Anfrage \(f(s,m)\) sei \(\ell\) die Länge der ausgewählten Zahl. In der Längensuche werden die Werte \(C_t(s)\) für aufeinanderfolgende Längen \(t\) von \(\lceil s/9\rceil\) bis \(\ell\) ausgewertet. Das Unranking benötigt \(O(\ell)\) Zifferentscheidungen, mit jeweils nur konstant vielen Zählaufrufen und gelegentlich einer zusätzlichen binären Suche der Größe \(O(\log \ell)\), wenn ein Block aus \(9\)en übersprungen wird.
Der dominierende arithmetische Aufwand entsteht durch die Inklusion-Exklusions-Formel für \(A(d,t)\). Sie besitzt \(O(\lfloor t/10\rfloor+1)\) Summanden und verwendet Binomialkoeffizienten mit großen Ganzzahlen. Der Speicherbedarf bleibt überschaubar: Neben den großen Ganzzahlen für Zählwerte und Ränge wird nur wenig weiterer Zustand gehalten. In der Praxis ist das schnell genug für die volle Summe bis \(k=10^4\), insbesondere mit Parallelisierung der äußeren Schleife.
Her \((s,m)\) çifti için \(f(s,m)\), rakamları toplamı \(s\) olan pozitif tamsayılar küçükten büyüğe sıralandığında \(m\). elemandır. Hesaplanmak istenen büyüklük
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
Tam giriş aralığında hem rakam toplamları hem de sıra numaraları brute force için fazla büyüktür. Bu yüzden çözüm önce her basamak uzunluğu bloğunda kaç uygun sayı olduğunu sayar, sonra aranan sıranın hangi blokta olduğunu bulur ve sayıyı soldan sağa yeniden kurar.
Temel fikir, her rakamı \(9\)'dan olan eksikliğiyle ifade etmektir. Böylece rakam toplamı koşulu, dahil et-çıkar ile tam olarak sayılabilen üstten sınırlı bir bileşim problemine dönüşür.
\(\ell\) basamaklı bir sayının rakamları \(a_1,\dots,a_\ell\) olsun. Şimdi
$$b_i=9-a_i$$
eksikliklerini tanımlayalım. O zaman her \(b_i\), \(\{0,\dots,9\}\) kümesindedir ve
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
İlk basamak sıfır olamayacağı için \(a_1\ge 1\) ve dolayısıyla
$$b_1\in\{0,\dots,8\}$$
olur. Kalan basamakların eksiklikleri ise hâlâ \(0\) ile \(9\) arasında olabilir. Böylece rakam toplamı \(s\) olan \(\ell\) basamaklı bir sayı, yalnızca ilk koordinatta biraz daha sıkı sınır bulunan bir \(b_1,\dots,b_\ell\) seçimine eşdeğerdir.
Mümkün olan en küçük uzunluk
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil$$
şeklindedir; çünkü tüm rakamlar \(9\) olsa bile toplam en fazla \(9\ell\) eder.
\(A(d,t)\), \(\{0,\dots,9\}\) içindeki rakamlardan oluşan uzunluğu \(d\) olan ve rakam toplamı \(t\) olan dizilerin sayısı olsun. Üst sınır \(9\) olmasaydı stars and bars yöntemi \(\binom{d+t-1}{t}\) verirdi. Bir veya daha fazla koordinatın \(10\) ya da daha büyük olduğu durumları çıkarınca tam formül elde edilir:
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
Algoritmanın her yerinde kullanılan sayım motoru budur. Bu değerler çok büyüyebildiği için uygulama bunları \(10^9+7\) modunda değil, keyfi hassasiyetli tamsayılarla hesaplar.
\(C_\ell(s)\), rakam toplamı \(s\) olan pozitif \(\ell\) basamaklı sayıların adedi olsun. İlk eksiklik \(b_1\) seçildikten sonra kalan \(\ell-1\) konum, standart sınırlı bileşim sayımına iner. Bu yüzden
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
Daha kısa sayılar her zaman daha uzun sayılardan küçüktür. Bu nedenle aranan sıra numarası \(m\),
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m$$
eşitsizliğini sağlayan ilk \(\ell\) uzunluğundaki blokta yer alır. Sonra blok içi sıra, daha kısa tüm blokların sayısı \(m\)'den çıkarılarak bulunur.
Kalan basamak sayısı \(r\), dağıtılacak kalan eksiklik de \(D\) olsun. Sıradaki basamağın eksikliği \(b\) ise, bu seçimden sonra mümkün tamamlanma sayısı
$$A(r-1,D-b)$$
olur. Sayıları artan düzende üretmek için aday rakamlar küçükten büyüğe denenir; eksiklik cinsinden bakılırsa bu, büyükten küçüğe denemek demektir. Hedef sıra bir bloğun tamamını aşıyorsa o blok atlanır ve büyüklüğü sıradan düşülür. Atlanmayan ilk blok bir sonraki rakamı belirler.
Eğer \(D=0\) ise kalan tüm rakamlar zorunlu olarak \(9\) olur. Daha genel durumda sözlük sırasındaki son blok, başında art arda \(9\)lar bulunan bloktur. Kalan \(r\) basamak varken ilk \(q\) basamak \(9\) sabitlenirse geriye
$$A(r-q,D)$$
adet geçerli son ek kalır; bu bloktan önce gelenler ise
$$A(r,D)-A(r-q,D)$$
kadardır. Bu tekdüze yapı sayesinde uygulama, öndeki \(9\) koşusunun uzunluğunu ikili aramayla bulup tek seferde ekleyebilir.
En küçük mümkün uzunluk \(\lceil 10/9\rceil=2\)'dir. Rakam toplamı \(10\) olan iki basamaklı sayılar
$$19,28,37,46,55,64,73,82,91$$
olduğundan \(C_2(10)=9\) olur. Demek ki 10. eleman iki basamaklı blokta değildir; üç basamaklı bloğun ilk elemanıdır.
\(\ell=3\) için eksiklik
$$\Delta=27-10=17$$
olur. İlk rakamı \(1\) denemek, ilk eksikliği \(8\) seçmek demektir ve son iki basamağa dağıtılacak eksiklik \(9\) kalır. Tamamlanma sayısı
$$A(2,9)=10$$
olduğundan, blok içi sıra \(1\) zaten bu ilk bloktadır. O hâlde ilk rakam \(1\) olur. Toplamı \(9\) olan kalan iki basamaklı son ekler içinde en küçük olan \(09\)'dur. Dolayısıyla toplam rakamı \(10\) olan ilk üç basamaklı sayı \(109\) ve sonuç
$$f(10,10)=109$$
şeklindedir.
C++, Python ve Java uygulamaları aynı matematiksel hattı izler. Önce üstten sınırlı rakam toplamları için tam kombinatorik sayımlar, ara sıra değerleri makine tamsayılarını aştığı için keyfi hassasiyetli tamsayılarla hesaplanır. Sonra hedef sıra tek bir uzunluk bloğuna düşene kadar uzunluk sayıları toplanır. Ardından, her aday sonraki rakam için kaç tamamlanma bulunduğu hesaplanarak sayı soldan sağa yeniden kurulur.
Sayı değeri dev bir ondalık tamsayı olarak tutulmaz. Bunun yerine uygulama inşa edilen değeri sürekli \(10^9+7\) modunda saklar ve \(x\mapsto 10x+d\) güncellemesiyle ilerler. Eğer bir anda tümüyle belli olan bir \(9\) bloğu varsa, bu blok
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}$$
formülüyle tek adımda eklenir. Son aşamada bu süreç her \(n\) için \(s=n^3\) ve sıra \(n^4\) olacak şekilde dış toplamda uygulanır. C++ uygulaması isterse bu dış döngüyü iş parçacıklarına bölebilir; Python ve Java uygulamaları ise aynı mantığı seri çalıştırır.
Tek bir \(f(s,m)\) sorgusunda seçilen sayının uzunluğu \(\ell\) olsun. Uzunluk bulma aşaması, \(t=\lceil s/9\rceil\) ile \(\ell\) arasındaki ardışık tüm \(C_t(s)\) değerlerini hesaplar. Unranking aşaması \(O(\ell)\) adet rakam kararı verir; her adımda sabit sayıda sınırlı bileşim sayımı gerekir ve bazen bir \(9\) bloğu atlanırken ek olarak \(O(\log \ell)\) ikili arama yapılır.
Baskın maliyet, \(A(d,t)\) için kullanılan dahil et-çıkar formülünden gelir. Bu formül \(O(\lfloor t/10\rfloor+1)\) terim içerir ve büyük tamsayı binom katsayıları kullanır. Bellek kullanımı düşüktür: sayımlar ve sıralar için gereken büyük tamsayıların dışında yalnızca az miktarda ek durum tutulur. Pratikte bu yöntem \(k=10^4\) için yeterince hızlıdır; dış döngü paralelleştirildiğinde daha da rahat çalışır.
Para cada par \((s,m)\), sea \(f(s,m)\) el \(m\)-ésimo entero positivo cuya suma decimal de dígitos es \(s\), ordenado de menor a mayor. La cantidad buscada es
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
En el rango completo del problema, tanto las sumas de dígitos como los rangos son demasiado grandes para un barrido directo. Por eso la solución primero cuenta cuántos números válidos hay en cada bloque de longitud, luego localiza el bloque que contiene el rango pedido y por último reconstruye el número dígito a dígito.
La simplificación decisiva consiste en reemplazar cada dígito por su déficit respecto de \(9\). Así la restricción sobre la suma de dígitos se convierte en un problema de composiciones acotadas que puede contarse exactamente con inclusión-exclusión.
Si un número de longitud \(\ell\) tiene dígitos \(a_1,\dots,a_\ell\), definimos
$$b_i=9-a_i.$$
Entonces cada \(b_i\) pertenece a \(\{0,\dots,9\}\), y además
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
El primer dígito no puede ser cero, de modo que \(a_1\ge 1\) y por tanto
$$b_1\in\{0,\dots,8\}.$$
Los demás déficits sí pueden tomar cualquier valor entre \(0\) y \(9\). Por lo tanto, un número positivo de \(\ell\) cifras con suma de dígitos \(s\) equivale a elegir \(b_1,\dots,b_\ell\) con una cota un poco más estricta solo en la primera posición.
La longitud mínima posible es
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
porque incluso usando solo dígitos \(9\), la suma máxima de un número de \(\ell\) cifras es \(9\ell\).
Sea \(A(d,t)\) el número de cadenas de longitud \(d\) sobre \(\{0,\dots,9\}\) cuya suma de dígitos vale \(t\). Sin la cota superior \(9\), el método de stars and bars daría \(\binom{d+t-1}{t}\). Para imponer la cota, se restan los casos en que una o más coordenadas son al menos \(10\). El resultado exacto es
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
Esta es la función de conteo central del algoritmo. Como los valores pueden ser enormes, la implementación los evalúa con enteros de precisión arbitraria y no solo módulo \(10^9+7\).
Sea \(C_\ell(s)\) la cantidad de enteros positivos de \(\ell\) cifras cuya suma de dígitos es \(s\). Una vez fijado el primer déficit \(b_1\), las \(\ell-1\) posiciones restantes forman una composición acotada estándar. Por ello
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
Los números con menos cifras siempre son menores que los que tienen más cifras. En consecuencia, el rango buscado \(m\) está en la primera longitud \(\ell\) que satisface
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$$
Una vez localizada esa longitud, el rango dentro del bloque se obtiene restando de \(m\) el total acumulado de todos los bloques anteriores.
Supongamos que quedan \(r\) posiciones por rellenar y que el déficit restante es \(D\). Si el siguiente dígito tiene déficit \(b\), el número de completaciones posibles es
$$A(r-1,D-b).$$
Para respetar el orden numérico creciente, los dígitos candidatos se prueban de menor a mayor; en términos de déficits, eso equivale a probar de mayor a menor. Si el rango buscado supera el tamaño de un bloque completo, ese bloque se descarta y su tamaño se resta al rango. El primer bloque que no se descarta fija el siguiente dígito.
Si \(D=0\), todos los dígitos restantes deben ser \(9\). Más en general, el último bloque en orden lexicográfico es el que empieza con una racha de \(9\)s. Si se fijan \(q\) nueves iniciales cuando quedan \(r\) posiciones, el número de sufijos supervivientes es
$$A(r-q,D),$$
y el número de sufijos válidos que aparecen antes de ese bloque es
$$A(r,D)-A(r-q,D).$$
Como esta cantidad es monótona, la implementación puede buscar por bisección la longitud de esa racha inicial de \(9\)s y añadirla de una sola vez.
La longitud mínima posible es \(\lceil 10/9\rceil=2\). Los números de dos cifras con suma de dígitos \(10\) son
$$19,28,37,46,55,64,73,82,91,$$
de modo que \(C_2(10)=9\). Por tanto, la décima aparición no está en el bloque de dos cifras; es el primer elemento del bloque de tres cifras.
Para \(\ell=3\), el déficit vale
$$\Delta=27-10=17.$$
Probar como primer dígito un \(1\) significa fijar déficit inicial \(8\), dejando déficit \(9\) para las dos cifras finales. El número de completaciones es
$$A(2,9)=10.$$
Así que el rango interno \(1\) ya cae en ese primer bloque. El dígito inicial es \(1\). Entre los sufijos de dos cifras con suma \(9\), el menor es \(09\). En consecuencia, el primer número de tres cifras con suma total \(10\) es \(109\), luego
$$f(10,10)=109.$$
Las implementaciones en C++, Python y Java siguen la misma secuencia matemática. Primero calculan conteos combinatorios exactos para sumas de dígitos acotadas usando enteros de precisión arbitraria, porque los rangos intermedios son mucho mayores que los enteros nativos. Después acumulan los conteos por longitud hasta que el rango buscado entra en un bloque concreto. Por último reconstruyen el número dígito a dígito, preguntando repetidamente cuántas completaciones permite cada posible siguiente dígito.
El valor numérico no se construye nunca como un entero decimal gigantesco. En su lugar, la implementación mantiene el valor ya formado módulo \(10^9+7\) y lo actualiza con la transformación \(x\mapsto 10x+d\). Si de una vez se conoce una racha completa de \(9\)s, esa racha se añade mediante
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}.$$
Finalmente, la suma exterior evalúa el procedimiento para cada \(n\) con \(s=n^3\) y rango \(n^4\). La implementación en C++ puede repartir opcionalmente ese lazo exterior entre varios hilos; las versiones en Python y Java usan la misma lógica en serie.
Para una consulta \(f(s,m)\), supongamos que la longitud seleccionada es \(\ell\). La fase de localización de longitud evalúa \(C_t(s)\) para longitudes consecutivas \(t\) desde \(\lceil s/9\rceil\) hasta \(\ell\). La fase de unranking realiza \(O(\ell)\) decisiones de dígitos, con un número constante de conteos de composiciones acotadas en cada paso y, ocasionalmente, una búsqueda binaria de coste \(O(\log \ell)\) al saltar una racha de \(9\)s.
El coste aritmético dominante proviene de la fórmula de inclusión-exclusión para \(A(d,t)\), que tiene \(O(\lfloor t/10\rfloor+1)\) términos y usa coeficientes binomiales con enteros grandes. El uso de memoria es moderado: aparte de los enteros grandes necesarios para conteos y rangos, solo se mantiene una pequeña cantidad de estado. En la práctica, esto es suficiente para calcular la suma completa hasta \(k=10^4\), especialmente cuando se paraleliza el lazo exterior.
对每个 \((s,m)\)，定义 \(f(s,m)\) 为“数位和等于 \(s\) 的正整数中，按通常从小到大顺序排列后的第 \(m\) 个”。题目要求计算
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
在完整数据范围内，数位和很大，排名 \(m\) 也极大，显然不能靠逐个枚举正整数来筛选。有效做法是先统计每个位数区间里一共有多少个合法数，再确定目标排名落在哪个位数区间，最后在该区间内按字典序逐位还原目标数。
核心变换是把每一位数字改写成它距离 \(9\) 的“亏空”。这样一来，数位和约束就会转化成一个带上界的拆分计数问题，而这个问题可以用容斥原理精确处理。
设一个 \(\ell\) 位十进制数的各位为 \(a_1,\dots,a_\ell\)。定义对应的亏空
$$b_i=9-a_i.$$
于是每个 \(b_i\) 都属于 \(\{0,\dots,9\}\)，并且
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
首位不能为 \(0\)，所以 \(a_1\ge 1\)，等价于
$$b_1\in\{0,\dots,8\}.$$
其余各位的亏空仍然可以是 \(0\) 到 \(9\)。因此，一个数位和为 \(s\) 的 \(\ell\) 位正整数，就等价于选择一组 \(b_1,\dots,b_\ell\)，其中只有第一位的取值范围略微更紧。
可行的最小位数为
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
因为即使每一位都取到最大值 \(9\)，总数位和也只有 \(9\ell\)。
记 \(A(d,t)\) 为长度为 \(d\)、每位都在 \(\{0,\dots,9\}\) 内且数位和为 \(t\) 的数字串个数。如果没有上界 \(9\)，那么 stars and bars 直接给出 \(\binom{d+t-1}{t}\)。但这里每一位都不能超过 \(9\)，所以要把某些坐标至少为 \(10\) 的情况扣掉。最终得到精确公式
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
这就是整个算法最基础的计数函数。由于这些数量本身可能远超普通整数范围，所以实现中会用任意精度整数保存这些计数，而不是一开始就模 \(10^9+7\)。
记 \(C_\ell(s)\) 为数位和等于 \(s\) 的正 \(\ell\) 位整数个数。只要首位亏空 \(b_1\) 确定，剩下的 \(\ell-1\) 位就变成了一个标准的受限拆分问题，因此
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
所有位数更短的正整数都严格小于所有位数更长的正整数，所以目标排名 \(m\) 一定落在满足下式的第一个位数 \(\ell\) 内：
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$$
一旦找到了这个 \(\ell\)，区间内部的排名就等于总排名 \(m\) 减去所有更短位数区间的累计个数。
假设当前还剩 \(r\) 位没有确定，需要继续分配的亏空总量是 \(D\)。如果下一位选择的亏空为 \(b\)，那么剩余部分的合法补全数恰好是
$$A(r-1,D-b).$$
为了保持数值从小到大的顺序，候选数字必须从小到大测试；换成亏空语言，就是从大到小测试。若目标排名超过某个整块的大小，就整体跳过这一块，并把它的大小从排名中减掉。第一个不能被跳过的块，就决定了当前这一位应该填什么数字。
如果 \(D=0\)，说明后面的每一位都只能是 \(9\)。更一般地说，字典序最后的一整块就是“前面连续若干位都是 \(9\)”的那一块。若在还剩 \(r\) 位时，先固定前 \(q\) 位都为 \(9\)，那么还保留下来的后缀个数是
$$A(r-q,D),$$
而排在这整块之前的合法后缀个数则是
$$A(r,D)-A(r-q,D).$$
这个量随着 \(q\) 单调变化，所以实现可以对前导 \(9\) 的长度做二分查找，然后一次性把整段 \(9\) 追加进去，而不必一位一位处理。
先看最小可能位数，\(\lceil 10/9\rceil=2\)。数位和等于 \(10\) 的两位数恰好是
$$19,28,37,46,55,64,73,82,91,$$
因此 \(C_2(10)=9\)。第 10 个目标数不在两位数区间里，而是三位数区间中的第 1 个。
对 \(\ell=3\)，总亏空为
$$\Delta=27-10=17.$$
如果首位尝试放 \(1\)，那么首位亏空是 \(8\)，后两位还需要承担亏空 \(9\)。此时补全数为
$$A(2,9)=10.$$
由于区间内部排名是 \(1\)，它已经落在这个首位为 \(1\) 的第一块里，所以首位确定为 \(1\)。剩下两位中，数位和为 \(9\) 的最小后缀是 \(09\)。于是三位数区间里的第一个合法数就是 \(109\)，从而
$$f(10,10)=109.$$
C++、Python 和 Java 三个实现遵循同一条数学流程。第一步，用任意精度整数精确计算各种受限数位和计数，因为中间的排名和计数远超普通机器整数范围。第二步，从最短可行位数开始逐段累加 \(C_\ell(s)\)，直到目标排名进入某一个确定的位数区间。第三步，在这个区间中逐位做逆排名构造，每次询问“如果当前位取某个候选数字，还会有多少种合法补全”。
真正的十进制大数本身并不会被完整构造出来。实现只维护当前已经构造出的值在 \(10^9+7\) 模下的结果，并通过 \(x\mapsto 10x+d\) 逐位更新。如果某一段连续的 \(9\) 已经可以整体确定，那么它会用
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}$$
一次性加入。最后，对每个 \(n\) 取 \(s=n^3\)、排名 \(n^4\)，并把对应结果累加起来。C++ 版本还可以把这个外层求和按线程拆分；Python 和 Java 版本则使用相同的数学逻辑串行执行。
对单次查询 \(f(s,m)\)，设最终选中的目标数长度为 \(\ell\)。位数定位阶段需要依次计算从 \(\lceil s/9\rceil\) 到 \(\ell\) 的各个 \(C_t(s)\)。逆排名阶段需要做 \(O(\ell)\) 次数位决策；每一步只调用常数次受限拆分计数，而当需要整段跳过前导 \(9\) 时，还会额外做一次 \(O(\log \ell)\) 的二分查找。
主导性的算术开销来自 \(A(d,t)\) 的容斥求和。这个求和有 \(O(\lfloor t/10\rfloor+1)\) 项，并且涉及大整数二项式系数。内存占用并不高：除了保存计数和排名所需的大整数外，只需要很少的附加状态。实践中，这套方法足以处理完整的 \(k=10^4\) 求和；如果外层循环并行化，运行会更轻松。
Для каждой пары \((s,m)\) обозначим через \(f(s,m)\) \(m\)-е положительное число, сумма десятичных цифр которого равна \(s\), если все такие числа упорядочить по возрастанию. Требуется вычислить
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
На полном диапазоне входных данных и суммы цифр, и номера в порядке настолько велики, что прямой перебор невозможен. Поэтому решение сначала считает, сколько допустимых чисел находится в каждом блоке фиксированной длины, затем находит блок, содержащий нужный ранг, а после этого восстанавливает само число цифра за цифрой.
Главная идея состоит в том, чтобы заменить каждую цифру ее дефицитом относительно \(9\). Тогда условие на сумму цифр превращается в задачу о композициях с верхней границей, а такую задачу удобно считать по принципу включения-исключения.
Пусть \(\ell\)-значное число имеет цифры \(a_1,\dots,a_\ell\). Введем дефициты
$$b_i=9-a_i.$$
Тогда каждый \(b_i\) принадлежит множеству \(\{0,\dots,9\}\), и выполняется эквивалентность
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
Первая цифра не может быть нулем, значит \(a_1\ge 1\), а потому
$$b_1\in\{0,\dots,8\}.$$
Для остальных позиций дефицит по-прежнему может принимать любые значения от \(0\) до \(9\). Следовательно, \(\ell\)-значное положительное число с суммой цифр \(s\) эквивалентно набору \(b_1,\dots,b_\ell\), где только первая координата имеет чуть более узкое ограничение.
Минимально возможная длина равна
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
поскольку даже если все цифры равны \(9\), суммарно они дают не больше \(9\ell\).
Пусть \(A(d,t)\) обозначает число строк длины \(d\) над \(\{0,\dots,9\}\) с суммой цифр \(t\). Без ограничения сверху \(9\) метод stars and bars дает \(\binom{d+t-1}{t}\). Чтобы учесть верхнюю границу, нужно вычесть случаи, где одна или несколько координат не меньше \(10\). Получаем точную формулу
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
Именно эта функция является счетным ядром алгоритма. Значения могут быть очень велики, поэтому реализация использует целые числа произвольной точности, а не сразу берет все по модулю \(10^9+7\).
Обозначим через \(C_\ell(s)\) количество положительных \(\ell\)-значных чисел с суммой цифр \(s\). После выбора первого дефицита \(b_1\) оставшиеся \(\ell-1\) позиций образуют стандартную ограниченную композицию. Поэтому
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
Все числа меньшей длины всегда меньше всех чисел большей длины, поэтому искомый ранг \(m\) попадает в первую длину \(\ell\), для которой
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$$
После нахождения этой длины внутренний ранг в блоке получается простым вычитанием суммарного числа всех более коротких блоков из \(m\).
Пусть осталось заполнить \(r\) позиций, а нераспределенный дефицит равен \(D\). Если следующая цифра имеет дефицит \(b\), то число допустимых продолжений равно
$$A(r-1,D-b).$$
Чтобы сохранить обычный числовой порядок, кандидаты по цифре проверяются от меньшей к большей; в терминах дефицитов это означает перебор от большего к меньшему. Если требуемый ранг превосходит размер целого блока, блок целиком пропускается, а его размер вычитается из ранга. Первый блок, который нельзя пропустить, задает следующую цифру.
Если \(D=0\), все оставшиеся цифры обязаны быть равны \(9\). В более общем виде последний по лексикографическому порядку блок начинается с серии цифр \(9\). Если при оставшихся \(r\) позициях мы фиксируем первые \(q\) из них равными \(9\), то размер оставшегося хвоста равен
$$A(r-q,D),$$
а количество допустимых суффиксов, идущих раньше этого блока, равно
$$A(r,D)-A(r-q,D).$$
Эта монотонность позволяет реализации двоичным поиском находить длину ведущей серии из \(9\) и добавлять всю серию за один шаг.
Минимально возможная длина равна \(\lceil 10/9\rceil=2\). Двузначные числа с суммой цифр \(10\) таковы:
$$19,28,37,46,55,64,73,82,91,$$
поэтому \(C_2(10)=9\). Следовательно, десятое вхождение лежит не в двузначном блоке, а является первым элементом трехзначного блока.
Для \(\ell=3\) дефицит равен
$$\Delta=27-10=17.$$
Если попробовать первой цифрой \(1\), то первый дефицит равен \(8\), а на последние две позиции остается дефицит \(9\). Число продолжений равно
$$A(2,9)=10.$$
Внутренний ранг \(1\) уже попадает в этот самый первый блок, значит ведущая цифра действительно \(1\). Среди двузначных суффиксов с суммой цифр \(9\) минимален \(09\). Поэтому первое трехзначное число с суммой цифр \(10\) равно \(109\), то есть
$$f(10,10)=109.$$
Реализации на C++, Python и Java следуют одной и той же математической схеме. Сначала они вычисляют точные комбинаторные количества для ограниченных сумм цифр с помощью целых чисел произвольной точности, потому что промежуточные ранги намного больше обычных машинных типов. Затем они суммируют количества по длинам, пока нужный ранг не попадет в один конкретный блок. После этого число восстанавливается по одной цифре, каждый раз вычисляя, сколько продолжений допускает очередной кандидат на следующую цифру.
Само число никогда не собирается как гигантское десятичное целое. Вместо этого реализация хранит уже построенное значение по модулю \(10^9+7\) и обновляет его правилом \(x\mapsto 10x+d\). Если сразу известна целая серия цифр \(9\), она добавляется формулой
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}.$$
Наконец, эта процедура выполняется для каждого \(n\), где \(s=n^3\), а ранг равен \(n^4\). Реализация на C++ при необходимости делит внешнюю сумму по потокам, а версии на Python и Java выполняют ту же математику последовательно.
Для одного запроса \(f(s,m)\) пусть длина найденного числа равна \(\ell\). На этапе поиска длины вычисляются значения \(C_t(s)\) для последовательных длин \(t\) от \(\lceil s/9\rceil\) до \(\ell\). Этап восстановления требует \(O(\ell)\) решений по цифрам; на каждом шаге используется константное число подсчетов ограниченных композиций, а иногда дополнительно выполняется двоичный поиск за \(O(\log \ell)\), когда перескакивается серия из \(9\).
Основная арифметическая стоимость связана с формулой включения-исключения для \(A(d,t)\). Она содержит \(O(\lfloor t/10\rfloor+1)\) членов и использует биномиальные коэффициенты с большими целыми числами. Памяти требуется немного: кроме больших чисел для счетчиков и рангов, хранится лишь небольшой объем дополнительного состояния. На практике этого достаточно для полного вычисления суммы до \(k=10^4\), особенно если распараллелить внешний цикл.
لكل زوج \((s,m)\)، نرمز بـ \(f(s,m)\) إلى العدد الموجب رقم \(m\) الذي يساوي مجموع أرقامه العشرية \(s\) عند ترتيب جميع هذه الأعداد تصاعديًا ترتيبًا عدديًا عاديًا. والمطلوب هو حساب
$$S(k)=\sum_{n=1}^{k} f(n^3,n^4)\pmod{10^9+7}.$$
في المجال الكامل للمسألة تكون قيم مجموع الأرقام والرتب المطلوبة كبيرة جدًا، لذلك لا يصلح الفحص المباشر. ولهذا تعتمد الفكرة على عدّ عدد الأعداد الصالحة داخل كل كتلة ذات طول ثابت، ثم تحديد الكتلة التي تحتوي الرتبة المطلوبة، ثم إعادة بناء العدد رقمًا رقمًا.
التبسيط الحاسم هو استبدال كل رقم بعجزه بالنسبة إلى \(9\). عندها يصبح شرط مجموع الأرقام مسألة تركيب محدود بحد أعلى، ويمكن عدّه بدقة باستخدام مبدأ الاحتواء والاستبعاد.
إذا كان للعدد ذي الطول \(\ell\) الأرقام \(a_1,\dots,a_\ell\)، فنعرّف العجوزات
$$b_i=9-a_i.$$
وعندئذ يكون كل \(b_i\) ضمن \(\{0,\dots,9\}\)، كما أن
$$a_1+\cdots+a_\ell=s \iff b_1+\cdots+b_\ell=9\ell-s=: \Delta.$$
الرقم الأول لا يمكن أن يكون صفرًا، أي إن \(a_1\ge 1\)، وهذا يكافئ
$$b_1\in\{0,\dots,8\}.$$
أما بقية العجوزات فتبقى بين \(0\) و\(9\). لذلك فإن العدد الموجب ذي \(\ell\) خانة ومجموع الأرقام \(s\) يكافئ اختيار \(b_1,\dots,b_\ell\) مع قيد أشد قليلًا على الخانة الأولى فقط.
وأصغر طول ممكن هو
$$\ell_{\min}=\left\lceil \frac{s}{9}\right\rceil,$$
لأن أكبر مجموع يمكن أن نحصل عليه من \(\ell\) خانات هو \(9\ell\).
لنعرّف \(A(d,t)\) بأنه عدد السلاسل ذات الطول \(d\) على الأبجدية \(\{0,\dots,9\}\) والتي يساوي مجموع أرقامها \(t\). من دون القيد العلوي \(9\)، تعطي طريقة stars and bars القيمة \(\binom{d+t-1}{t}\). لكن لأن كل خانة يجب ألا تتجاوز \(9\)، فعلينا طرح الحالات التي تكون فيها خانة واحدة أو أكثر على الأقل مساوية لـ \(10\) أو أكبر. فنحصل على الصيغة الدقيقة
$$A(d,t)=\sum_{j=0}^{\lfloor t/10\rfloor} (-1)^j \binom{d}{j}\binom{d+t-10j-1}{t-10j}.$$
هذه هي دالة العد الأساسية في الحل كله. ولأن القيم قد تصبح ضخمة جدًا، تستخدم الشيفرة أعدادًا صحيحة ذات دقة غير محدودة بدل الاكتفاء بالحساب بترديد \(10^9+7\).
ليكن \(C_\ell(s)\) عدد الأعداد الموجبة ذات \(\ell\) خانة ومجموع الأرقام \(s\). بعد تثبيت العجز الأول \(b_1\)، تصبح الخانات \(\ell-1\) المتبقية مسألة تركيب محدود عادية. لذلك
$$C_\ell(s)=\sum_{b_1=0}^{\min(8,\Delta)} A(\ell-1,\Delta-b_1), \qquad \Delta=9\ell-s.$$
كل الأعداد الأقصر طولًا أصغر دائمًا من كل الأعداد الأطول طولًا، ولهذا تقع الرتبة المطلوبة \(m\) في أول طول \(\ell\) يحقق
$$\sum_{t=\ell_{\min}}^{\ell} C_t(s)\ge m.$$
وبعد معرفة هذا الطول، تصبح الرتبة داخل الكتلة المختارة مساوية لـ \(m\) بعد طرح مجموع أعداد جميع الأطوال الأقصر.
افترض أن عدد الخانات المتبقية هو \(r\)، وأن العجز المتبقي الذي يجب توزيعه هو \(D\). إذا كان الرقم التالي المختار له عجز \(b\)، فإن عدد الإكمالات الصالحة يساوي
$$A(r-1,D-b).$$
ولكي نحافظ على الترتيب العددي التصاعدي، نجرب الأرقام المرشحة من الأصغر إلى الأكبر؛ وبصياغة العجز فهذا يعني التجريب من الأكبر إلى الأصغر. فإذا كانت الرتبة المطلوبة تتجاوز حجم كتلة كاملة، نتخطى هذه الكتلة ونطرح حجمها من الرتبة. وأول كتلة لا يمكن تجاوزها تحدد الرقم التالي.
إذا كان \(D=0\)، فكل الخانات المتبقية يجب أن تكون \(9\). وبصورة أعم، فإن آخر كتلة في الترتيب المعجمي هي الكتلة التي تبدأ بسلسلة من الأرقام \(9\). إذا ثبتنا أول \(q\) خانات على أنها \(9\) بينما بقي \(r\) خانات، فإن عدد النهايات الباقية هو
$$A(r-q,D),$$
أما عدد النهايات الصالحة التي تقع قبل هذه الكتلة فهو
$$A(r,D)-A(r-q,D).$$
ولأن هذه الكمية تتغير بشكل رتيب، تستطيع الشيفرة استخدام البحث الثنائي لإيجاد طول مقطع ابتدائي من \(9\)ات ثم إضافته دفعة واحدة.
أصغر طول ممكن هو \(\lceil 10/9\rceil=2\). والأعداد ذات الخانتين التي مجموع أرقامها \(10\) هي
$$19,28,37,46,55,64,73,82,91,$$
ولذلك \(C_2(10)=9\). إذن الظهور العاشر لا يقع في كتلة الأعداد ذات الخانتين، بل هو أول عنصر في كتلة الأعداد ذات الثلاث خانات.
عندما \(\ell=3\)، يكون العجز الكلي
$$\Delta=27-10=17.$$
إذا جربنا أن تكون الخانة الأولى \(1\)، فهذا يعني أن العجز الأول يساوي \(8\)، ويبقى عجز مقداره \(9\) موزعًا على آخر خانتين. وعدد الإكمالات الممكنة هو
$$A(2,9)=10.$$
وبما أن الرتبة داخل هذه الكتلة هي \(1\)، فهي تقع أصلًا داخل أول كتلة، وبالتالي تكون الخانة الأولى \(1\). وأصغر لاحقة من خانتين مجموعها \(9\) هي \(09\). إذن أول عدد من ثلاث خانات مجموع أرقامه \(10\) هو \(109\)، وبالتالي
$$f(10,10)=109.$$
تتبع تطبيقات C++ وPython وJava التسلسل الرياضي نفسه. في البداية تُحسب قيم العد التوافقي الدقيقة لمجاميع الأرقام المقيدة باستخدام أعداد صحيحة ذات دقة غير محدودة، لأن الرتب الوسيطة أكبر بكثير من حدود الأنواع العددية العادية. بعد ذلك تُجمع كتل الأطوال تدريجيًا حتى تدخل الرتبة المطلوبة في كتلة طول واحدة محددة. ثم يُعاد بناء العدد خانة بخانة عبر السؤال المتكرر: كم عدد الإكمالات الممكنة إذا اخترنا هذه القيمة كرقم تالٍ؟
العدد نفسه لا يُبنى كعدد عشري ضخم كامل. بدلًا من ذلك، تحتفظ الشيفرة بالقيمة الحالية بترديد \(10^9+7\) وتحدثها بالقانون \(x\mapsto 10x+d\). وإذا أمكن تحديد سلسلة كاملة من \(9\)ات دفعة واحدة، فإنها تُلحق بواسطة
$$x \mapsto x\cdot 10^q + (10^q-1)\pmod{10^9+7}.$$
وفي النهاية تُطبَّق هذه العملية على كل \(n\) مع \(s=n^3\) والرتبة \(n^4\)، ثم تُجمع النتائج. ويمكن لنسخة C++ أن تقسم هذه الحلقة الخارجية على عدة خيوط، بينما تطبق نسختا Python وJava المنطق نفسه بصورة تسلسلية.
بالنسبة إلى استعلام واحد \(f(s,m)\)، ولنفترض أن طول العدد الناتج هو \(\ell\). في مرحلة تحديد الطول نحسب القيم \(C_t(s)\) للأطوال المتتالية \(t\) من \(\lceil s/9\rceil\) حتى \(\ell\). أما مرحلة فك الترتيب فتتطلب \(O(\ell)\) قرارات رقمية، مع عدد ثابت من عمليات عد التركيبات المحدودة في كل خطوة، وأحيانًا بحثًا ثنائيًا إضافيًا بكلفة \(O(\log \ell)\) عند القفز فوق مقطع من \(9\)ات.
تأتي الكلفة الحسابية الغالبة من صيغة الاحتواء والاستبعاد الخاصة بـ \(A(d,t)\)، إذ تحتوي على \(O(\lfloor t/10\rfloor+1)\) حدًا وتستخدم معاملات ثنائية حدية كبيرة جدًا. أما الذاكرة فتبقى معتدلة: بخلاف الأعداد الكبيرة اللازمة لتخزين العدود والرتب، لا يحتاج الحل إلا إلى حالة إضافية صغيرة. عمليًا، هذا يكفي لحساب المجموع الكامل حتى \(k=10^4\)، ويصبح التنفيذ أسهل عند توزيع الحلقة الخارجية على عدة خيوط.