For each positive integer \(n\), let \(s(n)\) be the smallest positive integer whose decimal digit sum equals \(n\). Define
$$S(k)=\sum_{n=1}^{k} s(n).$$
The task is to evaluate
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$$
where \(F_0=0\), \(F_1=1\), and the remaining \(F_i\) are Fibonacci numbers. The key point is that \(F_{90}\) is far too large for any direct construction of all the numbers \(s(1),s(2),\dots,s(F_{90})\), so the solution must use a closed formula.
The implementation uses two observations. First, the smallest number with a fixed digit sum has a very rigid decimal form. Second, once those values are grouped into blocks of nine, the cumulative sum becomes a short expression involving a power of \(10\).
Write
$$n=9a+b,\qquad 0\le b<9.$$
Every decimal digit contributes at most \(9\), so the smallest possible number uses as few digits as possible. Among all numbers with that many digits, the smallest one places the largest digits at the far right and keeps the leftmost nonzero digit as small as possible. Therefore
$$s(n)=(b+1)10^a-1.$$
This is easy to visualize: if \(b>0\), the decimal expansion is the digit \(b\) followed by \(a\) copies of \(9\); if \(b=0\), the value is simply \(10^a-1\), namely \(a\) copies of \(9\).
Now write
$$k=9q+r,\qquad 0\le r<9.$$
For a fixed \(a\ge 0\), the nine inputs \(9a+1,9a+2,\dots,9a+9\) contribute
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
The sum of that block is
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$$
So the first \(q\) complete blocks contribute
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q.$$
After the \(q\) full blocks, there are \(r\) extra terms:
$$9q+1,9q+2,\dots,9q+r.$$
Using the formula from Step 1, their contribution is
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$$
Since
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2},$$
the tail becomes
$$\frac{r(r+3)}{2}10^q-r.$$
Putting the block sum and the tail together gives
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
This is the central identity used by the implementations. Once \(10^q\) is known modulo \(10^9+7\), the whole value of \(S(k)\) follows from a constant number of modular additions and multiplications.
Here
$$20=9\cdot 2+2,$$
so \(q=2\) and \(r=2\). The single-value formula gives
$$s(20)=(2+1)10^2-1=299.$$
For the cumulative sum, substitute \(q=2\) and \(r=2\):
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
This is exactly the small checkpoint used before the full Fibonacci accumulation.
The required answer is not a single \(S(k)\), but
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$$
So the algorithm generates Fibonacci numbers from \(F_0\) through \(F_{90}\), applies the closed form to each \(F_i\), and adds the results modulo \(10^9+7\). No huge decimal string for \(s(F_i)\) is ever constructed explicitly.
The C++, Python, and Java implementations all follow the same structure. They first build the Fibonacci sequence up to index \(90\) using ordinary integer arithmetic. For each Fibonacci value \(k\), they split it into \(k=9q+r\), compute \(10^q \bmod 10^9+7\) by binary exponentiation, evaluate the closed form for \(S(k)\), normalize any intermediate subtraction back into the modular range, and add the result to the running total. The C++ implementation also performs a small exact sanity check at \(k=20\) to confirm that the closed form matches direct enumeration before processing the full sum.
Evaluating one term \(S(k)\) requires one modular exponentiation, so the cost is \(O(\log q)=O(\log k)\). The outer sum has only \(89\) terms, from \(F_2\) through \(F_{90}\), so the total running time is
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$$
which is effectively constant for this input size. The implementations store \(91\) Fibonacci numbers and a few scalar values, so the memory usage is \(O(90)\), again effectively constant.
Für jede positive ganze Zahl \(n\) sei \(s(n)\) die kleinste positive Zahl, deren Dezimalziffernsumme gleich \(n\) ist. Definiere
$$S(k)=\sum_{n=1}^{k} s(n).$$
Gesucht ist
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$$
wobei \(F_0=0\), \(F_1=1\) und die restlichen \(F_i\) Fibonacci-Zahlen sind. Eine direkte Konstruktion aller Werte bis \(F_{90}\) ist völlig unpraktikabel, daher braucht man eine geschlossene Formel.
Die Lösung beruht auf zwei Ideen. Erstens hat die kleinste Zahl mit gegebener Ziffernsumme eine sehr starre Dezimalstruktur. Zweitens lässt sich die Summe dieser Werte in Blöcke zu je neun Eingaben zerlegen, was eine kompakte Formel mit einer Zehnerpotenz liefert.
Schreibe
$$n=9a+b,\qquad 0\le b<9.$$
Jede Dezimalziffer trägt höchstens \(9\) zur Ziffernsumme bei, also muss die kleinste mögliche Zahl so wenige Stellen wie möglich haben. Unter allen Zahlen mit dieser Stellenzahl erhält man den kleinsten Wert, wenn die großen Ziffern ganz rechts stehen und die kleinste nichtverschwindende Vorderziffer ganz links steht. Deshalb gilt
$$s(n)=(b+1)10^a-1.$$
Anschaulich bedeutet das: Für \(b>0\) besteht die Zahl aus der Ziffer \(b\) gefolgt von \(a\) Neunen; für \(b=0\) erhält man einfach \(10^a-1\), also genau \(a\) Neunen.
Schreibe nun
$$k=9q+r,\qquad 0\le r<9.$$
Für ein festes \(a\ge 0\) liefern die neun Eingaben \(9a+1,9a+2,\dots,9a+9\) die Beiträge
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
Die Summe dieses Blocks ist
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$$
Die ersten \(q\) vollständigen Blöcke tragen also
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q$$
bei.
Nach den \(q\) vollständigen Blöcken bleiben noch \(r\) Werte:
$$9q+1,9q+2,\dots,9q+r.$$
Mit der Formel aus Schritt 1 ergibt sich
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$$
Wegen
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2}$$
ist der Restterm gleich
$$\frac{r(r+3)}{2}10^q-r.$$
Durch Zusammenfassen des Blockanteils und des Restanteils erhält man
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
Genau diese Identität wird im Code modulo \(10^9+7\) ausgewertet. Sobald \(10^q\) modulo \(10^9+7\) bekannt ist, braucht man nur noch wenige modulare Rechenoperationen.
Hier gilt
$$20=9\cdot 2+2,$$
also \(q=2\) und \(r=2\). Die Einzelwertformel liefert
$$s(20)=(2+1)10^2-1=299.$$
Für die Summenformel folgt
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
Dieser Wert stimmt mit dem kleinen exakten Prüfschritt vor der Hauptberechnung überein.
Gesucht ist nicht nur ein einzelnes \(S(k)\), sondern
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$$
Daher erzeugt der Algorithmus die Fibonacci-Zahlen von \(F_0\) bis \(F_{90}\), setzt jede davon in die geschlossene Formel ein und addiert alles modulo \(10^9+7\). Eine explizite Konstruktion riesiger Dezimalzahlen ist dabei nie nötig.
Die C++-, Python- und Java-Implementierungen verwenden denselben Ablauf. Zuerst wird die Fibonacci-Folge bis Index \(90\) mit gewöhnlicher Ganzzahlarithmetik erzeugt. Für jeden Fibonacci-Wert \(k\) wird \(k=9q+r\) zerlegt, dann \(10^q \bmod 10^9+7\) per binärer Exponentiation berechnet, anschließend die geschlossene Formel für \(S(k)\) ausgewertet, und negative Zwischenterme werden wieder in den Modulbereich zurückgeführt. Zum Schluss werden alle Beiträge aufaddiert. In der C++-Implementierung gibt es zusätzlich einen kleinen exakten Test bei \(k=20\), der die Formel vor der Gesamtauswertung absichert.
Die Auswertung eines Terms \(S(k)\) benötigt genau eine modulare Potenzierung und kostet daher \(O(\log q)=O(\log k)\). Die äußere Summe umfasst nur \(89\) Fibonacci-Zahlen, nämlich \(F_2\) bis \(F_{90}\). Insgesamt ergibt sich also
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$$
was für diese Problemgröße praktisch konstant ist. Gespeichert werden \(91\) Fibonacci-Werte und einige Skalare, also \(O(90)\) Speicher.
Her pozitif \(n\) için \(s(n)\), rakamları toplamı \(n\) olan en küçük pozitif tamsayı olsun. Ayrıca
$$S(k)=\sum_{n=1}^{k} s(n)$$
tanımlansın. İstenen değer
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7}$$
ifadesidir; burada \(F_0=0\), \(F_1=1\) ve diğer \(F_i\) değerleri Fibonacci dizisidir. \(F_{90}\) çok büyük olduğundan, tüm \(s(n)\) değerlerini tek tek üretmek yerine kapalı bir formül bulmak gerekir.
Uygulama iki temel fikre dayanır. Birincisi, sabit rakam toplamına sahip en küçük sayının ondalık yazımı çok katı bir yapıya sahiptir. İkincisi, bu değerler 9'lu bloklar halinde toplandığında sonuç yalnızca bir \(10\) kuvveti içeren kısa bir ifadeye dönüşür.
Şöyle yazalım:
$$n=9a+b,\qquad 0\le b<9.$$
Her ondalık basamak en fazla \(9\) katkı yaptığı için en küçük sayı, mümkün olan en az basamak sayısını kullanmalıdır. Aynı basamak sayısı içinde değeri daha da küçültmek için büyük rakamlar sağa, en küçük sıfır olmayan rakam sola yerleştirilir. Bu yüzden
$$s(n)=(b+1)10^a-1$$
elde edilir. \(b>0\) ise bu, solda \(b\) ve sağda \(a\) tane \(9\) demektir; \(b=0\) ise sonuç \(10^a-1\), yani yalnızca \(a\) tane \(9\)'dur.
Şimdi
$$k=9q+r,\qquad 0\le r<9$$
yazalım. Sabit bir \(a\ge 0\) için \(9a+1,9a+2,\dots,9a+9\) girişleri şu katkıları verir:
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
Bu dokuz terimin toplamı
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9$$
olur. Böylece ilk \(q\) tam bloktan gelen toplam
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q$$
şeklindedir.
\(q\) tam bloktan sonra \(r\) tane ek terim kalır:
$$9q+1,9q+2,\dots,9q+r.$$
Adım 1'deki formülle bunların toplamı
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r$$
olur. Ayrıca
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2}$$
olduğundan kuyruk katkısı
$$\frac{r(r+3)}{2}10^q-r$$
şeklini alır.
Blok toplamı ile kuyruk toplamını birleştirince
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
ifadesi elde edilir. Uygulamanın merkezindeki özdeşlik budur. \(10^q \bmod 10^9+7\) hesaplandıktan sonra geri kalan her şey sabit sayıda modüler toplama ve çarpmadır.
Burada
$$20=9\cdot 2+2$$
olduğundan \(q=2\), \(r=2\). Tek değer formülü
$$s(20)=(2+1)10^2-1=299$$
verir. Kümülatif toplam için yerine yazalım:
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
Bu değer, tam Fibonacci toplamına geçmeden önce kullanılan küçük doğrulama noktasıyla aynıdır.
Hedef yalnızca tek bir \(S(k)\) değil,
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}$$
ifadesidir. Bu yüzden algoritma \(F_0\)'dan \(F_{90}\)'a kadar Fibonacci sayıları üretir, her biri için kapalı formülü uygular ve sonuçları mod \(10^9+7\) altında toplar. Hiçbir aşamada \(s(F_i)\) değerinin tam ondalık yazımı kurulmaz.
C++, Python ve Java implementasyonları aynı planı izler. Önce Fibonacci dizisi \(90\). indekse kadar normal tamsayı aritmetiğiyle üretilir. Sonra her Fibonacci değeri \(k\) için \(k=9q+r\) ayrışımı yapılır, \(10^q \bmod 10^9+7\) ikili üs alma ile hesaplanır, kapalı formül mod altında değerlendirilir, çıkarma işlemlerinden sonra sonuç tekrar uygun mod aralığına normalize edilir ve toplam güncellenir. C++ implementasyonunda ayrıca \(k=20\) için küçük bir tam sayım kontrolü bulunur.
Tek bir \(S(k)\) değerlendirmesi bir modüler üs alma içerir; dolayısıyla maliyet \(O(\log q)=O(\log k)\) olur. Dış toplam yalnızca \(89\) terim içerir; yani \(F_2\) ile \(F_{90}\) arasındaki Fibonacci değerleri kullanılır. Bu nedenle toplam çalışma süresi
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90})$$
şeklindedir ve bu boyut için pratikte sabit sayılır. Bellek kullanımı \(91\) Fibonacci değeri ve birkaç skalerden oluşur; yani \(O(90)\), pratikte yine sabittir.
Para cada entero positivo \(n\), sea \(s(n)\) el menor entero positivo cuya suma de cifras decimal es \(n\). Definimos
$$S(k)=\sum_{n=1}^{k} s(n).$$
Hay que calcular
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$$
donde \(F_0=0\), \(F_1=1\) y los demás \(F_i\) son números de Fibonacci. Como \(F_{90}\) es enorme, no sirve construir todos los valores individualmente; la solución depende de una fórmula cerrada.
La idea central tiene dos partes. Primero, el menor número con suma de cifras fija tiene una forma decimal completamente determinada. Segundo, al sumar esos valores por bloques de nueve, la expresión total se reduce a una fórmula muy corta con una potencia de \(10\).
Escribimos
$$n=9a+b,\qquad 0\le b<9.$$
Cada cifra aporta como máximo \(9\), así que el número mínimo debe usar la menor cantidad posible de cifras. Entre todos los números con esa longitud, el menor se obtiene colocando las cifras grandes a la derecha y dejando la cifra no nula más pequeña posible a la izquierda. Por eso
$$s(n)=(b+1)10^a-1.$$
Si \(b>0\), esto representa la cifra \(b\) seguida por \(a\) nueves. Si \(b=0\), el resultado es simplemente \(10^a-1\), es decir, \(a\) nueves.
Ahora escribimos
$$k=9q+r,\qquad 0\le r<9.$$
Para un \(a\ge 0\) fijo, las nueve entradas \(9a+1,9a+2,\dots,9a+9\) producen
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
La suma del bloque es
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$$
Por tanto, los primeros \(q\) bloques completos aportan
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q.$$
Después de esos \(q\) bloques completos quedan \(r\) términos extra:
$$9q+1,9q+2,\dots,9q+r.$$
Usando la fórmula del Paso 1, su contribución es
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$$
Como
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2},$$
la cola vale
$$\frac{r(r+3)}{2}10^q-r.$$
Al combinar el aporte de los bloques completos con la cola obtenemos
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
Esta es exactamente la identidad que evalúan las implementaciones. Una vez conocido \(10^q \bmod 10^9+7\), el resto se resuelve con pocas operaciones modulares.
Aquí
$$20=9\cdot 2+2,$$
de modo que \(q=2\) y \(r=2\). La fórmula individual da
$$s(20)=(2+1)10^2-1=299.$$
Para la suma acumulada:
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
Ese valor coincide con la comprobación exacta pequeña antes de procesar toda la suma sobre Fibonacci.
La respuesta pedida no es un único \(S(k)\), sino
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$$
Por ello, el algoritmo genera \(F_0,\dots,F_{90}\), aplica la fórmula cerrada a cada \(F_i\) y acumula los resultados bajo el módulo \(10^9+7\). Nunca hace falta construir explícitamente el enorme entero \(s(F_i)\).
Las implementaciones en C++, Python y Java siguen el mismo esquema. Primero generan la sucesión de Fibonacci hasta el índice \(90\) con aritmética entera normal. Luego, para cada valor \(k\), separan \(k=9q+r\), calculan \(10^q \bmod 10^9+7\) mediante exponenciación binaria, sustituyen ese valor en la fórmula cerrada de \(S(k)\), corrigen las restas para mantener todo dentro del rango modular y suman el resultado al acumulado final. La implementación en C++ además incluye una pequeña comprobación exacta en \(k=20\) para validar la fórmula antes del bucle principal.
Evaluar un término \(S(k)\) requiere una sola exponenciación modular, así que cuesta \(O(\log q)=O(\log k)\). La suma exterior contiene solo \(89\) términos, desde \(F_2\) hasta \(F_{90}\). En consecuencia, el tiempo total es
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$$
que para este tamaño de entrada es prácticamente constante. Se almacenan \(91\) números de Fibonacci y unas pocas variables escalares, de modo que el uso de memoria es \(O(90)\).
对每个正整数 \(n\)，定义 \(s(n)\) 为“十进制各位数字之和等于 \(n\) 的最小正整数”。再定义
$$S(k)=\sum_{n=1}^{k} s(n).$$
本题要求计算
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$$
其中 \(F_0=0\)、\(F_1=1\)，其余 \(F_i\) 为斐波那契数。由于 \(F_{90}\) 已经非常大，显然不能把 \(s(1),s(2),\dots,s(F_{90})\) 全部直接构造出来，所以必须先把数学结构压缩成闭式。
实现依赖两个关键观察。第一，固定数位和时，最小整数的十进制形状其实是完全确定的。第二，把这些值按 9 个一组求和后，累加式会化成只含 \(10\) 的幂的短公式，因此可以直接做模运算。
把 \(n\) 写成
$$n=9a+b,\qquad 0\le b<9.$$
因为任意一位数字最多贡献 \(9\)，所以要让数最小，首先必须让位数尽量少。在位数已经最少的前提下，还要让高位尽可能小，因此应把尽可能多的 \(9\) 放在最低位一侧，把剩余的小数字放在最左边。于是得到
$$s(n)=(b+1)10^a-1.$$
这个式子对应的十进制外观非常直观：若 \(b>0\)，它就是“左边一个数字 \(b\)，后面跟着 \(a\) 个 \(9\)”；若 \(b=0\)，就变成 \(10^a-1\)，也就是恰好 \(a\) 个 \(9\)。例如 \(20=9\cdot 2+2\)，所以 \(s(20)=299\)。
再把求和上界写成
$$k=9q+r,\qquad 0\le r<9.$$
对固定的 \(a\ge 0\)，连续九个输入 \(9a+1,9a+2,\dots,9a+9\) 的对应最小值为
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
因此这一个完整 9 项块的和是
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$$
前 \(q\) 个完整块的贡献就是
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q.$$
这里使用的是等比数列求和公式，所以大规模求和被压缩成了一个关于 \(10^q\) 的表达式。
如果 \(r\neq 0\)，在 \(q\) 个完整块之后还剩下
$$9q+1,9q+2,\dots,9q+r$$
这 \(r\) 项。根据步骤 1，它们的和为
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$$
而
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2},$$
所以尾部贡献化简为
$$\frac{r(r+3)}{2}10^q-r.$$
当 \(r=0\) 时，这一项自然消失，公式仍然成立。
把完整块与尾部相加，就得到本题最重要的恒等式：
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
这正是实现直接计算的公式。换句话说，只要能快速得到 \(10^q \bmod 10^9+7\)，整个 \(S(k)\) 就能在常数次模加、模乘、模减中完成，而不必枚举任何大整数。
令
$$20=9\cdot 2+2,$$
于是 \(q=2\)、\(r=2\)。单点值先给出
$$s(20)=(2+1)10^2-1=299.$$
再代入累计和公式：
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
这个结果恰好对应实现里用于校验公式正确性的那个小样例，因此既能验证推导，也能说明闭式与直接求和完全一致。
题目最终要求的不是单个 \(S(k)\)，而是
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$$
因此算法先生成 \(F_0\) 到 \(F_{90}\)，然后对每个 \(F_i\) 套用上面的闭式并在模 \(10^9+7\) 下累加。整个过程中都不会真的构造出 \(s(F_i)\) 的十进制展开，这正是算法能够高效处理大下标的原因。
C++、Python 和 Java 三个实现采用完全相同的思路。首先用普通整数运算生成到 \(F_{90}\) 为止的斐波那契数列。随后对每个斐波那契值 \(k\)，拆成 \(k=9q+r\)，再用二进制快速幂求出 \(10^q \bmod 10^9+7\)。接着把这个幂代入上面的闭式，所有减法都在模意义下重新规范到合法范围，最后把当前项加入总答案。C++ 实现还额外保留了一个 \(k=20\) 的小规模精确检查，用来在主循环前确认闭式没有推导错误。
单次计算 \(S(k)\) 的主要代价是一遍模快速幂，因此时间复杂度是 \(O(\log q)=O(\log k)\)。外层只需要处理 \(F_2\) 到 \(F_{90}\) 这 \(89\) 项，所以总时间为
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$$
在本题规模下几乎可以视为常数时间。空间方面，只需保存 \(91\) 个斐波那契数以及少量标量，因此是 \(O(90)\)，实际同样近似常数。
Для каждого положительного целого \(n\) обозначим через \(s(n)\) наименьшее положительное число, сумма десятичных цифр которого равна \(n\). Далее определим
$$S(k)=\sum_{n=1}^{k} s(n).$$
Нужно вычислить
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$$
где \(F_0=0\), \(F_1=1\), а остальные \(F_i\) образуют последовательность Фибоначчи. Значение \(F_{90}\) слишком велико для прямого перебора, поэтому решение строится на явной формуле.
В основе решения лежат два наблюдения. Во-первых, минимальное число при фиксированной сумме цифр имеет очень жесткую десятичную структуру. Во-вторых, если складывать такие значения блоками по девять, получается короткая формула, в которой единственный крупный объект - степень числа \(10\).
Представим \(n\) в виде
$$n=9a+b,\qquad 0\le b<9.$$
Каждая цифра дает не более \(9\), значит минимальное число должно иметь как можно меньше цифр. При фиксированной длине число будет минимальным, если большие цифры сдвинуть вправо, а самый маленький ненулевой остаток поставить слева. Отсюда следует формула
$$s(n)=(b+1)10^a-1.$$
Если \(b>0\), это цифра \(b\), после которой идут \(a\) девяток. Если \(b=0\), выражение превращается в \(10^a-1\), то есть просто в \(a\) девяток.
Теперь запишем
$$k=9q+r,\qquad 0\le r<9.$$
Для фиксированного \(a\ge 0\) девять подряд идущих аргументов \(9a+1,9a+2,\dots,9a+9\) дают
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
Сумма этого блока равна
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$$
Следовательно, вклад первых \(q\) полных блоков составляет
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q.$$
После \(q\) полных блоков остаются еще \(r\) слагаемых:
$$9q+1,9q+2,\dots,9q+r.$$
По формуле из первого шага их сумма равна
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$$
Так как
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2},$$
получаем хвостовой вклад
$$\frac{r(r+3)}{2}10^q-r.$$
Складывая полный блок и хвост, получаем основное тождество:
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
Именно эта формула вычисляется в реализации по модулю \(10^9+7\). После нахождения \(10^q \bmod 10^9+7\) остается лишь несколько модульных операций.
Здесь
$$20=9\cdot 2+2,$$
то есть \(q=2\) и \(r=2\). Формула для одного значения дает
$$s(20)=(2+1)10^2-1=299.$$
Теперь подставим в формулу для суммы:
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
Это значение совпадает с маленькой точной проверкой, которая выполняется перед основной суммой по числам Фибоначчи.
Требуется вычислить не одно \(S(k)\), а
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$$
Поэтому алгоритм сначала строит \(F_0,\dots,F_{90}\), затем для каждого \(F_i\) применяет замкнутую формулу и складывает результаты по модулю \(10^9+7\). Огромные десятичные записи чисел \(s(F_i)\) нигде не строятся явно.
Реализации на C++, Python и Java устроены одинаково. Сначала они генерируют последовательность Фибоначчи до индекса \(90\) в обычной целочисленной арифметике. Затем для каждого значения \(k\) разбивают его как \(k=9q+r\), вычисляют \(10^q \bmod 10^9+7\) методом быстрого возведения в степень, подставляют это значение в замкнутую формулу для \(S(k)\), нормализуют промежуточные вычитания обратно в диапазон по модулю и добавляют вклад к итоговой сумме. В реализации на C++ есть также маленькая точная проверка для \(k=20\), подтверждающая правильность формулы до запуска основного цикла.
Вычисление одного значения \(S(k)\) требует одной модульной степени, поэтому стоит \(O(\log q)=O(\log k)\). Внешняя сумма содержит только \(89\) членов, от \(F_2\) до \(F_{90}\). Итак, общее время работы равно
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$$
что для данного размера входа практически постоянно. По памяти нужно хранить \(91\) число Фибоначчи и несколько скаляров, то есть \(O(90)\).
لكل عدد صحيح موجب \(n\)، نعرّف \(s(n)\) بأنه أصغر عدد موجب يكون مجموع أرقامه العشرية مساويًا لـ \(n\). ثم نعرّف
$$S(k)=\sum_{n=1}^{k} s(n).$$
المطلوب هو حساب
$$\sum_{i=2}^{90} S(F_i) \pmod{10^9+7},$$
حيث \(F_0=0\) و\(F_1=1\) وبقية \(F_i\) هي أعداد فيبوناتشي. بما أن \(F_{90}\) كبير جدًا، فلا يمكن بناء جميع القيم \(s(1),s(2),\dots,s(F_{90})\) مباشرة، لذلك يعتمد الحل على اشتقاق صيغة مغلقة.
الفكرة الأساسية تتكوّن من ملاحظتين. الأولى أن أصغر عدد ذي مجموع أرقام ثابت يملك شكلًا عشريًا محددًا جدًا. والثانية أن جمع هذه القيم على كتل من تسعة عناصر يحوّل المجموع إلى تعبير قصير يعتمد أساسًا على قوة للعدد \(10\).
نكتب
$$n=9a+b,\qquad 0\le b<9.$$
كل خانة عشرية تساهم بحد أقصى مقداره \(9\)، لذلك فإن أصغر عدد ممكن يجب أن يستخدم أقل عدد ممكن من الخانات. وبعد تثبيت عدد الخانات، نصغّر القيمة بوضع الأرقام الكبيرة في الجهة اليمنى، ووضع أصغر رقم غير صفري ممكن في اليسار. من هنا نحصل على
$$s(n)=(b+1)10^a-1.$$
إذا كان \(b>0\)، فهذا يعني رقمًا أوليًا هو \(b\) ثم \(a\) خانات من الرقم \(9\). وإذا كان \(b=0\)، فإن القيمة تصبح \(10^a-1\)، أي \(a\) خانات من \(9\) فقط.
الآن نكتب
$$k=9q+r,\qquad 0\le r<9.$$
ولـ \(a\ge 0\) ثابت، فإن القيم التسع \(9a+1,9a+2,\dots,9a+9\) تعطي
$$\begin{aligned} s(9a+1)&=2\cdot 10^a-1,\\ s(9a+2)&=3\cdot 10^a-1,\\ &\ \vdots\\ s(9a+8)&=9\cdot 10^a-1,\\ s(9a+9)&=10^{a+1}-1. \end{aligned}$$
ومجموع هذه الكتلة يساوي
$$\sum_{m=1}^{9} s(9a+m)=\left(2+3+\cdots+9+10\right)10^a-9=54\cdot 10^a-9.$$
إذن مساهمة أول \(q\) كتل كاملة هي
$$\sum_{a=0}^{q-1}\left(54\cdot 10^a-9\right)=54\sum_{a=0}^{q-1}10^a-9q=6(10^q-1)-9q.$$
بعد الكتل الكاملة يبقى \(r\) حدود إضافية:
$$9q+1,9q+2,\dots,9q+r.$$
وباستخدام صيغة الخطوة الأولى نحصل على
$$\sum_{m=1}^{r}\left((m+1)10^q-1\right)=\left(\sum_{m=1}^{r}(m+1)\right)10^q-r.$$
ولأن
$$\sum_{m=1}^{r}(m+1)=\frac{r(r+1)}{2}+r=\frac{r(r+3)}{2},$$
فإن مساهمة الذيل تساوي
$$\frac{r(r+3)}{2}10^q-r.$$
بجمع مساهمة الكتل الكاملة مع مساهمة الذيل نحصل على الهوية الأساسية
$$\boxed{S(k)=6(10^q-1)-9q+\frac{r(r+3)}{2}10^q-r,\qquad k=9q+r,\ 0\le r<9.}$$
هذه هي الصيغة التي تقيمها التنفيذات مباشرةً تحت المودولو \(10^9+7\). وبمجرد معرفة \(10^q \bmod 10^9+7\)، يصبح باقي الحساب مجموعة صغيرة من عمليات الجمع والطرح والضرب المعيارية.
لدينا
$$20=9\cdot 2+2,$$
أي \(q=2\) و\(r=2\). وصيغة القيمة المفردة تعطينا
$$s(20)=(2+1)10^2-1=299.$$
أما للمجموع التراكمي فنحسب
$$\begin{aligned} S(20)&=6(10^2-1)-9\cdot 2+\frac{2(2+3)}{2}10^2-2\\ &=6\cdot 99-18+5\cdot 100-2\\ &=594-18+500-2\\ &=1074. \end{aligned}$$
وهذه هي نفس القيمة الصغيرة التي تُستخدم للتحقق من صحة الصيغة قبل تنفيذ التجميع الكامل على أعداد فيبوناتشي.
الجواب النهائي ليس قيمة واحدة لـ \(S(k)\)، بل
$$\sum_{i=2}^{90} S(F_i)\pmod{10^9+7}.$$
لذلك تقوم الخوارزمية بتوليد الأعداد \(F_0\) حتى \(F_{90}\)، ثم تطبق الصيغة المغلقة على كل \(F_i\) وتجمع النتائج تحت المودولو \(10^9+7\). لا حاجة في أي لحظة إلى بناء التمثيل العشري الضخم لـ \(s(F_i)\) بشكل صريح.
تنفيذات C++ وPython وJava تتبع الخطة نفسها. أولًا تُبنى متتالية فيبوناتشي حتى الفهرس \(90\) باستخدام حسابات صحيحة عادية. بعد ذلك، لكل قيمة \(k\)، يتم تفكيكها إلى \(k=9q+r\)، ثم يُحسب \(10^q \bmod 10^9+7\) بواسطة الرفع السريع للأس، وبعدها تُطبّق الصيغة المغلقة لـ \(S(k)\)، وتُعاد أي قيم سالبة ناتجة عن الطرح إلى المجال المعياري الصحيح، ثم يُضاف الناتج إلى المجموع الكلي. كما يحتوي تنفيذ C++ على فحص صغير دقيق عند \(k=20\) للتأكد من أن الصيغة المغلقة تطابق العد المباشر قبل الدخول في الحلقة الرئيسية.
حساب قيمة واحدة \(S(k)\) يحتاج إلى عملية أس معيارية واحدة، لذا تكون الكلفة \(O(\log q)=O(\log k)\). أما المجموع الخارجي ففيه \(89\) حدًا فقط، من \(F_2\) حتى \(F_{90}\). وعليه يكون الزمن الكلي
$$O\!\left(\sum_{i=2}^{90}\log F_i\right)=O(90\log F_{90}),$$
وهو عمليًا ثابت بالنسبة إلى حجم هذه المسألة. من ناحية الذاكرة، تُخزَّن \(91\) قيمة فيبوناتشي مع عدد قليل من المتغيرات القياسية، أي \(O(90)\)، وهو أيضًا عمليًا ثابت.