For a positive integer \(n\), let \(F(n)=f(n)\) be the sum of all positive decimal integers that contain no zero digit and whose digit sum is exactly \(n\). Let \(A(n)\) denote how many such integers exist.
The problem asks for
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
A direct enumeration is impossible because \(13^{17}\) is enormous, so the implementation turns the digit-building process into a fixed linear recurrence and then evaluates that recurrence with matrix exponentiation.
Every valid number with digit sum \(n\) ends in exactly one digit \(d\in\{1,\dots,9\}\). After removing that last digit, the remaining prefix must still avoid zeros and must have digit sum \(n-d\). Therefore
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
To make the recurrence uniform, we use the standard empty-prefix convention
$$A(0)=1,\qquad A(n)=0 \text{ for } n\lt 0.$$
The value \(A(0)=1\) does not represent a positive integer. It represents the single empty prefix that allows one-digit numbers to be generated correctly.
Now let \(F(n)\) be the sum of all valid integers with digit sum \(n\). Fix the last digit \(d\). If a prefix value is \(x\), appending \(d\) on the right creates the new number \(10x+d\). Summing over all prefixes of digit sum \(n-d\) gives the contribution \(10F(n-d)+d\,A(n-d)\).
Adding the contributions of the nine possible last digits gives the coupled recurrence
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
with initial conditions
$$F(0)=0,\qquad F(n)=0 \text{ for } n\lt 0.$$
This pair of recurrences is exactly what the C++, Python, and Java solutions implement.
The valid numbers are \(5\); \(14,23,32,41\); \(113,122,131,212,221,311\); \(1112,1121,1211,2111\); and \(11111\). There are \(16\) such numbers, so \(A(5)=16\), and their total is
$$F(5)=17891.$$
The C++ program uses this identity as a checkpoint before it starts the large matrix-power computations.
Both recurrences only look back nine steps, so one state vector stores everything needed for the next update:
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
From the formulas above we obtain
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$$
All other coordinates of \(v_{n+1}\) are simple shifts of the previous window. Hence there exists a fixed \(18\times18\) matrix \(T\) such that
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
with initial state
$$v_0=(1,0,\dots,0,0,\dots,0)^T.$$
The required value \(F(n)\) is the 10th component of \(v_n\), which is why the implementations read state index \(9\).
The target indices are \(13,13^2,\dots,13^{17}\), so iterating the recurrence step by step is still infeasible. Instead the code precomputes
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
by repeated squaring modulo \(10^9\). For each exponent \(n\), the binary expansion of \(n\) tells us which precomputed powers must be applied to \(v_0\). Because the recurrence is linear, reducing every intermediate result modulo \(10^9\) is mathematically valid.
build_transition() constructs the sparse \(18\times18\) matrix described above. The first row contains nine ones for the count recurrence, the next eight rows shift the count window, the 10th row contains coefficients \(1,2,\dots,9\) for the count block and nine copies of \(10\) for the value-sum block, and the last eight rows shift the value-sum window.
The C++ version precomputes 64 matrix powers because \(13^{17}\) fits within 64 bits, then f_of_n() applies only the powers corresponding to set bits of \(n\). The Python and Java versions use the same transition and the same binary-exponentiation idea.
Let \(m\) be the largest queried index. Precomputing the matrix powers costs \(O(18^3\log m)\) time and \(O(18^2\log m)\) memory. After that, one evaluation of \(F(n)\) costs only \(O(18^2\log n)\) time because the query phase multiplies matrices by a vector, not by another matrix. For this problem there are only 17 queries, so the total runtime is dominated by a small constant number of \(18\times18\) operations.
Für eine positive ganze Zahl \(n\) sei \(F(n)=f(n)\) die Summe aller positiven Dezimalzahlen ohne Ziffer \(0\), deren Ziffernsumme genau \(n\) ist. Mit \(A(n)\) bezeichnen wir die Anzahl dieser Zahlen.
Gesucht ist
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
Eine direkte Enumeration ist unmöglich, weil \(13^{17}\) bereits riesig ist. Deshalb formt die Implementierung den Ziffernaufbau in eine feste lineare Rekurrenz um und wertet diese dann per Matrixpotenzierung aus.
Jede gültige Zahl mit Ziffernsumme \(n\) endet in genau einer Ziffer \(d\in\{1,\dots,9\}\). Entfernt man diese letzte Ziffer, dann bleibt ein Präfix ohne Nullen und mit Ziffernsumme \(n-d\). Also gilt
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
Damit die Rekurrenz ohne Sonderfälle funktioniert, verwendet man die übliche Konvention des leeren Präfixes:
$$A(0)=1,\qquad A(n)=0 \text{ für } n\lt 0.$$
Der Wert \(A(0)=1\) steht nicht für eine positive Zahl, sondern für genau ein leeres Präfix, aus dem die einstelligen Zahlen korrekt entstehen.
Nun sei \(F(n)\) die Summe aller gültigen Zahlen mit Ziffernsumme \(n\). Fixiere die letzte Ziffer \(d\). Hat ein Präfix den Wert \(x\), dann entsteht durch Anhängen von \(d\) rechts die neue Zahl \(10x+d\). Summiert man über alle Präfixe mit Ziffernsumme \(n-d\), erhält man den Beitrag \(10F(n-d)+d\,A(n-d)\).
Über alle neun möglichen Endziffern folgt damit die gekoppelte Rekurrenz
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
mit Anfangswerten
$$F(0)=0,\qquad F(n)=0 \text{ für } n\lt 0.$$
Genau dieses Rekurrenzpaar wird in den C++-, Python- und Java-Lösungen umgesetzt.
Die zulässigen Zahlen sind \(5\); \(14,23,32,41\); \(113,122,131,212,221,311\); \(1112,1121,1211,2111\); sowie \(11111\). Es gibt also \(16\) Stück, also \(A(5)=16\), und ihre Summe ist
$$F(5)=17891.$$
Das C++-Programm verwendet diese Identität als Kontrollwert, bevor es die großen Matrixpotenzen berechnet.
Beide Rekurrenzen schauen nur neun Schritte zurück. Daher genügt ein Zustandsvektor, der alle für den nächsten Schritt nötigen Werte speichert:
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
Aus den Formeln oben folgt
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$$
Alle übrigen Koordinaten von \(v_{n+1}\) sind nur Verschiebungen des bisherigen Fensters. Damit existiert eine feste \(18\times18\)-Matrix \(T\) mit
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
und Anfangszustand
$$v_0=(1,0,\dots,0,0,\dots,0)^T.$$
Der gesuchte Wert \(F(n)\) ist die 10. Komponente von \(v_n\); deshalb lesen die Implementierungen den Zustand an Index \(9\) aus.
Die Zielindizes sind \(13,13^2,\dots,13^{17}\). Auch mit der Rekurrenz wäre ein schrittweises Weiterlaufen zu teuer. Stattdessen berechnet der Code
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
durch wiederholtes Quadrieren modulo \(10^9\). Für jeden Exponenten \(n\) bestimmt dann seine Binärdarstellung, welche vorberechneten Potenzen auf \(v_0\) angewendet werden müssen. Wegen der Linearität der Rekurrenz darf nach jedem Zwischenschritt modulo \(10^9\) reduziert werden.
build_transition() konstruiert die oben beschriebene dünn besetzte \(18\times18\)-Matrix. Die erste Zeile enthält neun Einsen für die Zählrekurrenz, die nächsten acht Zeilen verschieben das Zählfenster, die 10. Zeile enthält die Koeffizienten \(1,2,\dots,9\) für den Zählblock und neun Zehner für den Wertsummenblock, und die letzten acht Zeilen verschieben das Wertsummenfenster.
Die C++-Version berechnet 64 Matrixpotenzen vor, weil \(13^{17}\) in 64 Bit passt. Anschließend wendet f_of_n() nur die Potenzen an, die zu gesetzten Bits von \(n\) gehören. Die Python- und Java-Versionen verwenden dieselbe Übergangsmatrix und dieselbe Idee der binären Exponentiation.
Sei \(m\) der größte abgefragte Index. Das Vorberechnen der Matrixpotenzen kostet \(O(18^3\log m)\) Zeit und \(O(18^2\log m)\) Speicher. Danach benötigt eine einzelne Auswertung von \(F(n)\) nur \(O(18^2\log n)\) Zeit, weil in der Abfragephase Matrix-Vektor-Produkte und keine Matrix-Matrix-Produkte berechnet werden. Für dieses Problem gibt es nur 17 Abfragen, daher bleibt die Gesamtzeit sehr klein.
Pozitif bir \(n\) için \(F(n)=f(n)\), basamaklarında hiç \(0\) bulunmayan ve basamak toplamı tam olarak \(n\) olan tüm pozitif onluk sayıların toplamı olsun. \(A(n)\) ise bu sayıların adedini göstersin.
İstenen değer
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
\(13^{17}\) çok büyük olduğu için doğrudan üretim mümkün değildir. Bu yüzden çözüm, basamak ekleme sürecini sabit katsayılı lineer bir reküransa dönüştürür ve ardından bu reküransı matris üs alma ile değerlendirir.
Basamak toplamı \(n\) olan her geçerli sayı mutlaka \(d\in\{1,\dots,9\}\) kümesinden bir son basamakla biter. Bu son basamak kaldırıldığında elde kalan önek yine sıfır içermemeli ve basamak toplamı \(n-d\) olmalıdır. Dolayısıyla
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
Reküransı tek biçimde yazabilmek için boş önek konvansiyonu kullanılır:
$$A(0)=1,\qquad A(n)=0 \text{ for } n\lt 0.$$
\(A(0)=1\) değeri gerçek bir pozitif sayıyı temsil etmez; tek basamaklı sayıların doğru üretilmesini sağlayan tek bir boş öneği temsil eder.
Şimdi \(F(n)\), basamak toplamı \(n\) olan tüm geçerli sayıların toplamı olsun. Son basamağı \(d\) olarak sabitleyelim. Bir önek değeri \(x\) ise sağa \(d\) eklemek yeni sayıyı \(10x+d\) yapar. Basamak toplamı \(n-d\) olan tüm önekler üzerinden toplarsak katkı \(10F(n-d)+d\,A(n-d)\) olur.
Dokuz olası son basamağın tamamı toplandığında bağlı rekürans elde edilir:
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
başlangıç koşulları da
$$F(0)=0,\qquad F(n)=0 \text{ for } n\lt 0.$$
C++, Python ve Java çözümleri tam olarak bu iki reküransı uygular.
Geçerli sayılar \(5\); \(14,23,32,41\); \(113,122,131,212,221,311\); \(1112,1121,1211,2111\); ve \(11111\) şeklindedir. Toplam \(16\) sayı vardır; yani \(A(5)=16\), ve bunların toplamı
$$F(5)=17891$$
olur. C++ çözümündeki kontrol noktası da budur.
Her iki rekürans da yalnızca son dokuz adıma baktığı için, bir sonraki güncelleme için gerekli tüm bilgiyi tek bir durum vektöründe tutmak yeterlidir:
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
Yukarıdaki formüllerden
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i)$$
elde edilir. \(v_{n+1}\) içindeki diğer bileşenler sadece önceki pencerenin kaydırılmış halidir. Bu nedenle sabit bir \(18\times18\) matrisi \(T\) vardır ve
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
başlangıç durumu da
$$v_0=(1,0,\dots,0,0,\dots,0)^T$$
şeklindedir. İstenen \(F(n)\) değeri \(v_n\) vektörünün 10. bileşenidir; bu yüzden kodlar durum dizisinin \(9\). indisinden sonucu okur.
Hedef indisler \(13,13^2,\dots,13^{17}\) olduğundan reküransı adım adım ilerletmek yine pahalı olur. Bunun yerine kod
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
matrislerini \(10^9\) modunda tekrarlı karesini alma yöntemiyle önceden hesaplar. Her \(n\) için, \(n\)'in ikili açılımı hangi hazır kuvvetlerin \(v_0\) üzerine uygulanacağını belirler. Rekürans lineer olduğu için ara adımlarda mod \(10^9\) almak matematiksel olarak doğrudur.
build_transition(), yukarıda tarif edilen seyrek \(18\times18\) geçiş matrisini kurar. İlk satır sayım reküransı için dokuz adet \(1\) içerir, sonraki sekiz satır sayım penceresini kaydırır, 10. satır sayım bloğu için \(1,2,\dots,9\) katsayılarını ve değer toplamı bloğu için dokuz adet \(10\) değerini içerir, son sekiz satır da değer toplamı penceresini kaydırır.
C++ sürümü \(13^{17}\) 64 bit içine sığdığı için 64 matris kuvvetini önceden hesaplar. Ardından f_of_n() yalnızca \(n\)'in ikili gösteriminde set edilmiş bitlere karşılık gelen kuvvetleri uygular. Python ve Java sürümleri de aynı geçiş matrisini ve aynı ikili üs alma fikrini kullanır.
\(m\) en büyük sorgu indisi olsun. Matris kuvvetlerini önceden hesaplamak \(O(18^3\log m)\) zaman ve \(O(18^2\log m)\) bellek ister. Bundan sonra tek bir \(F(n)\) hesabı yalnızca \(O(18^2\log n)\) zaman alır; çünkü sorgu aşamasında matris-matris yerine matris-vektör çarpımları yapılır. Bu problemde sadece 17 sorgu bulunduğundan toplam çalışma süresi küçüktür.
Para un entero positivo \(n\), sea \(F(n)=f(n)\) la suma de todos los enteros decimales positivos que no contienen ningún dígito \(0\) y cuya suma de dígitos es exactamente \(n\). Denotemos por \(A(n)\) la cantidad de tales enteros.
Se pide calcular
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
Una enumeración directa es imposible porque \(13^{17}\) ya es enorme. Por eso la implementación convierte la construcción por dígitos en una recurrencia lineal fija y luego evalúa esa recurrencia mediante exponenciación de matrices.
Todo número válido con suma de dígitos \(n\) termina en un dígito \(d\in\{1,\dots,9\}\). Si quitamos ese último dígito, el prefijo restante también debe evitar ceros y debe tener suma de dígitos \(n-d\). Por lo tanto,
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
Para que la recurrencia sea uniforme usamos la convención estándar del prefijo vacío:
$$A(0)=1,\qquad A(n)=0 \text{ para } n\lt 0.$$
El valor \(A(0)=1\) no representa un entero positivo real; representa el único prefijo vacío que permite generar correctamente los números de una sola cifra.
Ahora sea \(F(n)\) la suma de todos los números válidos con suma de dígitos \(n\). Fijemos el último dígito \(d\). Si un prefijo tiene valor \(x\), al añadir \(d\) a la derecha obtenemos el nuevo número \(10x+d\). Al sumar sobre todos los prefijos con suma de dígitos \(n-d\), la contribución es \(10F(n-d)+d\,A(n-d)\).
Al sumar las nueve posibilidades para el último dígito se obtiene la recurrencia acoplada
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
con condiciones iniciales
$$F(0)=0,\qquad F(n)=0 \text{ para } n\lt 0.$$
Esto es exactamente lo que implementan las soluciones en C++, Python y Java.
Los números válidos son \(5\); \(14,23,32,41\); \(113,122,131,212,221,311\); \(1112,1121,1211,2111\); y \(11111\). Hay \(16\) en total, así que \(A(5)=16\), y su suma vale
$$F(5)=17891.$$
El programa en C++ usa esta identidad como verificación antes de pasar a las potencias grandes de la matriz.
Ambas recurrencias solo dependen de los nueve valores anteriores. Por eso basta un único vector de estado para guardar toda la información necesaria para el siguiente paso:
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
De las fórmulas anteriores se deduce
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$$
Las demás coordenadas de \(v_{n+1}\) son simples desplazamientos de la ventana anterior. En consecuencia, existe una matriz fija \(18\times18\) \(T\) tal que
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
con estado inicial
$$v_0=(1,0,\dots,0,0,\dots,0)^T.$$
El valor buscado \(F(n)\) es la décima componente de \(v_n\), por eso las implementaciones leen el índice \(9\) del vector de estado.
Los índices objetivo son \(13,13^2,\dots,13^{17}\), así que avanzar la recurrencia paso a paso sigue siendo inviable. En su lugar, el código precalcula
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
mediante cuadrados sucesivos módulo \(10^9\). Para cada exponente \(n\), la expansión binaria de \(n\) indica qué potencias precalculadas deben aplicarse a \(v_0\). Como la recurrencia es lineal, reducir cada resultado intermedio módulo \(10^9\) es correcto.
build_transition() construye la matriz dispersa \(18\times18\) descrita arriba. La primera fila contiene nueve unos para la recurrencia de conteo, las ocho filas siguientes desplazan la ventana de conteos, la décima fila contiene los coeficientes \(1,2,\dots,9\) para el bloque de conteos y nueve copias de \(10\) para el bloque de sumas, y las últimas ocho filas desplazan la ventana de sumas.
La versión en C++ precalcula 64 potencias de la matriz porque \(13^{17}\) cabe en 64 bits. Luego f_of_n() aplica solo las potencias correspondientes a los bits activos de \(n\). Las versiones en Python y Java usan la misma transición y la misma idea de exponenciación binaria.
Sea \(m\) el mayor índice consultado. Precalcular las potencias de la matriz cuesta \(O(18^3\log m)\) tiempo y \(O(18^2\log m)\) memoria. Después, una sola evaluación de \(F(n)\) cuesta \(O(18^2\log n)\) tiempo porque durante la consulta se multiplican matrices por un vector, no por otra matriz. Como en este problema solo hay 17 consultas, el tiempo total es muy pequeño.
对正整数 \(n\)，记 \(F(n)=f(n)\) 为所有“不含数字 \(0\)”且“各位数字之和恰好等于 \(n\)”的正十进制整数之和，再记 \(A(n)\) 为这类整数的个数。
题目要求计算
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
由于 \(13^{17}\) 已经极大，不可能按数值逐个枚举。实现采用的思路是：先把“按末位扩展数字”的过程写成固定的线性递推，再用矩阵快速幂在巨大下标上求值。
任何一个数位和为 \(n\) 的合法整数，都必然以某个 \(d\in\{1,\dots,9\}\) 结尾。去掉最后一位之后，剩下的前缀仍然不能含 \(0\)，并且其数位和必须是 \(n-d\)。因此有
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
为了让递推没有额外分支，程序采用空前缀的标准约定：
$$A(0)=1,\qquad A(n)=0 \text{ for } n\lt 0.$$
这里的 \(A(0)=1\) 不代表一个真正的正整数，它只表示“唯一的空前缀”，这样一位数的情况才能自然地纳入同一套公式。
再令 \(F(n)\) 表示所有合法整数的数值总和。固定最后一位 \(d\)。如果某个前缀的数值是 \(x\)，那么在右侧追加 \(d\) 后，新数变成 \(10x+d\)。对所有数位和为 \(n-d\) 的前缀求和，就得到贡献 \(10F(n-d)+d\,A(n-d)\)。
把九种可能的末位全部加起来，就得到耦合递推
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
并配合初值
$$F(0)=0,\qquad F(n)=0 \text{ for } n\lt 0.$$
仓库中的 C++、Python、Java 三份解法实现的正是这对递推关系。
当 \(n=5\) 时，合法整数依次是 \(5\)；\(14,23,32,41\)；\(113,122,131,212,221,311\)；\(1112,1121,1211,2111\)；以及 \(11111\)。因此共有 \(16\) 个，即 \(A(5)=16\)，它们的总和是
$$F(5)=17891.$$
C++ 版本在进入大规模矩阵幂计算之前，先用这个值做检查点验证。
这两个递推都只依赖最近九项，因此只需一个状态向量就能保存下一步所需的全部信息：
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
由上面的公式可得
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$$
\(v_{n+1}\) 的其他坐标只是把旧窗口整体右移一格，所以一定存在一个固定的 \(18\times18\) 矩阵 \(T\)，满足
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
其中初始状态为
$$v_0=(1,0,\dots,0,0,\dots,0)^T.$$
所需的 \(F(n)\) 正好是 \(v_n\) 的第 10 个分量，这也是代码最终读取状态下标 \(9\) 的原因。
目标下标是 \(13,13^2,\dots,13^{17}\)，即使已经得到递推，也不能逐项迭代到那么远。代码改为预处理
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
这些矩阵幂，并且全部在模 \(10^9\) 下通过反复平方得到。对任意 \(n\)，只要查看 \(n\) 的二进制展开，就知道该把哪些预处理幂作用到 \(v_0\) 上。由于整个系统是线性的，所以每一步都先取模在数学上完全成立。
build_transition() 负责构造上面描述的稀疏 \(18\times18\) 转移矩阵。第一行放入九个 \(1\)，对应计数递推；接下来的八行负责把计数窗口向后平移；第 10 行在计数块中放入系数 \(1,2,\dots,9\)，并在求和块中放入九个 \(10\)；最后八行再把求和值窗口向后平移。
C++ 实现之所以预处理 64 个矩阵幂，是因为 \(13^{17}\) 可以放进 64 位整数。随后 f_of_n() 只对 \(n\) 的二进制中为 \(1\) 的那些位应用相应矩阵。Python 和 Java 版本采用完全相同的转移结构与快速幂思路。
设最大查询下标为 \(m\)。预处理矩阵幂需要 \(O(18^3\log m)\) 时间和 \(O(18^2\log m)\) 空间。预处理完成后，单次计算 \(F(n)\) 只需 \(O(18^2\log n)\) 时间，因为查询阶段做的是“矩阵乘向量”，而不是“矩阵乘矩阵”。本题只需要 17 次查询，所以整体运行代价很小。
Для положительного целого \(n\) обозначим через \(F(n)=f(n)\) сумму всех положительных десятичных чисел, которые не содержат цифру \(0\) и имеют сумму цифр ровно \(n\). Через \(A(n)\) обозначим количество таких чисел.
Нужно вычислить
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
Прямой перебор невозможен, потому что \(13^{17}\) слишком велико. Поэтому реализация переводит процесс построения числа по цифрам в фиксированную линейную рекуррентность, а затем вычисляет ее с помощью возведения матрицы в степень.
Любое допустимое число с суммой цифр \(n\) оканчивается некоторой цифрой \(d\in\{1,\dots,9\}\). Если удалить эту последнюю цифру, оставшийся префикс тоже не должен содержать нулей и должен иметь сумму цифр \(n-d\). Следовательно,
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
Чтобы рекуррентность работала без отдельных случаев, вводится стандартное соглашение о пустом префиксе:
$$A(0)=1,\qquad A(n)=0 \text{ for } n\lt 0.$$
Значение \(A(0)=1\) не соответствует настоящему положительному числу; оно означает единственный пустой префикс, благодаря которому однозначные числа естественно входят в ту же формулу.
Теперь пусть \(F(n)\) обозначает сумму самих допустимых чисел с суммой цифр \(n\). Зафиксируем последнюю цифру \(d\). Если значение префикса равно \(x\), то после приписывания \(d\) справа получаем число \(10x+d\). Суммирование по всем префиксам с суммой цифр \(n-d\) дает вклад \(10F(n-d)+d\,A(n-d)\).
Суммируя по всем девяти возможным последним цифрам, получаем связанную рекуррентность
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
с начальными условиями
$$F(0)=0,\qquad F(n)=0 \text{ for } n\lt 0.$$
Именно эта пара рекуррентностей реализована в версиях на C++, Python и Java.
Допустимые числа таковы: \(5\); \(14,23,32,41\); \(113,122,131,212,221,311\); \(1112,1121,1211,2111\); и \(11111\). Всего их \(16\), то есть \(A(5)=16\), а их сумма равна
$$F(5)=17891.$$
Версия на C++ использует это равенство как проверочный контрольный пример перед вычислением больших степеней матрицы.
Обе рекуррентности зависят только от девяти предыдущих значений, поэтому достаточно одного вектора состояния, который хранит все данные, необходимые для следующего шага:
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
Из формул выше получаем
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$$
Остальные координаты \(v_{n+1}\) являются просто сдвигами предыдущего окна. Значит, существует фиксированная матрица \(18\times18\) \(T\), такая что
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
где начальное состояние равно
$$v_0=(1,0,\dots,0,0,\dots,0)^T.$$
Искомое значение \(F(n)\) находится в 10-й компоненте вектора \(v_n\), поэтому реализации читают элемент состояния с индексом \(9\).
Нужные индексы равны \(13,13^2,\dots,13^{17}\), поэтому даже с рекуррентностью пошаговый проход был бы слишком дорогим. Вместо этого код предварительно вычисляет
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
методом repeated squaring по модулю \(10^9\). Для каждого \(n\) его двоичная запись указывает, какие предвычисленные степени нужно применить к \(v_0\). Поскольку вся система линейна, взятие по модулю \(10^9\) после каждого промежуточного шага полностью корректно.
build_transition() строит описанную выше разреженную матрицу перехода \(18\times18\). Первая строка содержит девять единиц для рекуррентности подсчета, следующие восемь строк сдвигают окно подсчета, десятая строка содержит коэффициенты \(1,2,\dots,9\) для блока \(A\) и девять десяток для блока \(F\), а последние восемь строк сдвигают окно сумм.
Версия на C++ предвычисляет 64 степени матрицы, потому что \(13^{17}\) помещается в 64 бита. Затем функция f_of_n() применяет только те степени, которые соответствуют установленным битам числа \(n\). Версии на Python и Java используют ту же матрицу перехода и ту же идею двоичного возведения в степень.
Пусть \(m\) - максимальный запрашиваемый индекс. Предвычисление степеней матрицы стоит \(O(18^3\log m)\) по времени и \(O(18^2\log m)\) по памяти. После этого одно вычисление \(F(n)\) требует только \(O(18^2\log n)\) времени, потому что на этапе запроса выполняются умножения матрицы на вектор, а не матрицы на матрицу. В задаче всего 17 запросов, так что общее время работы мало.
لعدد صحيح موجب \(n\)، نرمز بـ \(F(n)=f(n)\) إلى مجموع جميع الأعداد العشرية الموجبة التي لا تحتوي على أي رقم \(0\) ويكون مجموع أرقامها مساويًا تمامًا لـ \(n\). كما نرمز بـ \(A(n)\) إلى عدد هذه الأعداد.
المطلوب هو حساب
$$\sum_{k=1}^{17} F(13^k)\pmod{10^9}.$$
العد المباشر مستحيل عمليًا لأن \(13^{17}\) كبير جدًا. لذلك تحوّل الحلول عملية بناء العدد رقمًا رقمًا إلى علاقة خطية ثابتة، ثم تستعمل الأس السريع للمصفوفات للوصول إلى هذه الفهارس الضخمة.
كل عدد صالح مجموع أرقامه \(n\) لا بد أن ينتهي برقم \(d\in\{1,\dots,9\}\). وإذا حذفنا هذا الرقم الأخير، فإن البادئة المتبقية يجب أيضًا ألا تحتوي على أصفار وأن يكون مجموع أرقامها \(n-d\). لذلك نحصل على
$$A(n)=\sum_{d=1}^{9} A(n-d).$$
ولكي تبقى العلاقة موحدة دون حالات خاصة، نستخدم اصطلاح البادئة الفارغة:
$$A(0)=1,\qquad A(n)=0 \text{ for } n\lt 0.$$
القيمة \(A(0)=1\) لا تمثل عددًا موجبًا فعليًا، بل تمثل البادئة الفارغة الوحيدة التي تسمح بتوليد الأعداد ذات الرقم الواحد ضمن الصيغة نفسها.
الآن لتكن \(F(n)\) مجموع قيم جميع الأعداد الصالحة ذات مجموع الأرقام \(n\). ثبّت الرقم الأخير \(d\). إذا كانت قيمة البادئة هي \(x\)، فإن إلحاق \(d\) إلى اليمين يعطي العدد الجديد \(10x+d\). وعند الجمع على كل البوادئ ذات مجموع الأرقام \(n-d\)، تكون المساهمة \(10F(n-d)+d\,A(n-d)\).
بجمع مساهمات الأرقام التسعة الممكنة نحصل على العلاقة المزدوجة
$$F(n)=\sum_{d=1}^{9}\left(10F(n-d)+d\,A(n-d)\right),$$
مع الشروط الابتدائية
$$F(0)=0,\qquad F(n)=0 \text{ for } n\lt 0.$$
وهذه هي العلاقة نفسها الموجودة في حلول C++ وPython وJava في المستودع.
الأعداد الصالحة هنا هي \(5\)؛ ثم \(14,23,32,41\)؛ ثم \(113,122,131,212,221,311\)؛ ثم \(1112,1121,1211,2111\)؛ وأخيرًا \(11111\). إذن عددها \(16\)، أي \(A(5)=16\)، ومجموعها يساوي
$$F(5)=17891.$$
نسخة C++ تستخدم هذه القيمة كنقطة فحص قبل الدخول في حسابات قوى المصفوفة الكبيرة.
كلتا العلاقتين تعتمدان فقط على آخر تسع قيم، لذلك يكفي متجه حالة واحد لتخزين كل ما نحتاج إليه في الخطوة التالية:
$$v_n=\bigl(A(n),A(n-1),\dots,A(n-8),F(n),F(n-1),\dots,F(n-8)\bigr)^T.$$
ومن الصيغ السابقة نستنتج
$$A(n+1)=A(n)+A(n-1)+\cdots+A(n-8),$$
$$F(n+1)=\sum_{i=0}^{8}(i+1)A(n-i)+10\sum_{i=0}^{8}F(n-i).$$
أما بقية مركبات \(v_{n+1}\) فهي مجرد إزاحات للنافذة السابقة. لذلك توجد مصفوفة ثابتة \(18\times18\) اسمها \(T\) تحقق
$$v_{n+1}=T\,v_n,\qquad v_n=T^n v_0,$$
حيث الحالة الابتدائية هي
$$v_0=(1,0,\dots,0,0,\dots,0)^T.$$
القيمة المطلوبة \(F(n)\) هي المركبة العاشرة من المتجه \(v_n\)، ولهذا تقرأ الشيفرات العنصر ذي الفهرس \(9\).
الفهارس المطلوبة هي \(13,13^2,\dots,13^{17}\)، ولذلك يبقى التقدم خطوة بخطوة غير عملي حتى بعد الحصول على العلاقة. بدلًا من ذلك يسبق الكود حساب
$$T^{2^0},T^{2^1},T^{2^2},\dots$$
بطريقة التربيع المتكرر modulo \(10^9\). ولكل \(n\)، يحدد التمثيل الثنائي لـ \(n\) أي القوى المحسوبة مسبقًا يجب تطبيقها على \(v_0\). وبما أن النظام خطي، فإن أخذ الباقي modulo \(10^9\) بعد كل خطوة وسيطة أمر صحيح رياضيًا.
الدالة build_transition() تبني مصفوفة الانتقال المتناثرة \(18\times18\) الموصوفة أعلاه. الصف الأول يحتوي على تسعة آحاد لعلاقة العد، والصفوف الثمانية التالية تحرّك نافذة العد، والصف العاشر يحتوي على المعاملات \(1,2,\dots,9\) لكتلة \(A\) وتسع قيم \(10\) لكتلة \(F\)، ثم تقوم الصفوف الثمانية الأخيرة بتحريك نافذة مجموع القيم.
نسخة C++ تحسب 64 قوة للمصفوفة مسبقًا لأن \(13^{17}\) يقع ضمن 64 بت. وبعد ذلك تطبق الدالة f_of_n() فقط القوى المطابقة للبتات المفعلة في \(n\). أما نسختا Python وJava فتستخدمان مصفوفة الانتقال نفسها والفكرة نفسها للرفع الثنائي.
إذا كان \(m\) هو أكبر فهرس مطلوب، فإن التحضير المسبق لقوى المصفوفة يكلف \(O(18^3\log m)\) زمنًا و\(O(18^2\log m)\) ذاكرة. بعد ذلك تصبح كلفة حساب \(F(n)\) مرة واحدة هي فقط \(O(18^2\log n)\)، لأن مرحلة الاستعلام تستعمل ضرب مصفوفة في متجه، لا ضرب مصفوفتين. وبما أن المسألة تطلب 17 قيمة فقط، فالتكلفة الإجمالية صغيرة.