We must count all decimal strings of length \(d=18\), equivalently all integers \(0 \le n \lt 10^{18}\), such that
$$s(n)=s(137n),$$
where \(s(x)\) denotes the base-10 digit sum. Direct enumeration over \(10^{18}\) candidates is impossible, so we need to process the multiplication structurally, one digit at a time.
Write
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$
When we multiply by \(m=137\), the \(i\)-th output digit depends only on the current input digit \(a_i\) and the incoming carry \(c_i\):
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
Thus the low \(d\) digits of \(137n\) are produced digit by digit, and whatever remains above position \(d-1\) is exactly the final carry \(c_d\).
After processing the first \(i\) digits, define
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$
This is the difference between the digit sum already contributed by \(n\) and the digit sum already contributed by the low part of \(137n\). Once \((c_i,\Delta_i)\) is known, the future no longer depends on earlier digits individually. That is why the dynamic-programming state can be just
$$\text{state}_i=(c_i,\Delta_i).$$
If the next digit chosen is \(a_i\), then the produced output digit is \(b_i\), so the update is simply
$$\Delta_{i+1}=\Delta_i+a_i-b_i.$$
After all \(d\) input digits have been processed, the product has the form
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
The first term contributes digit sum \(\sum_{i=0}^{d-1} b_i\), and the untouched carry tail contributes \(s(c_d)\). Therefore
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
Since also \(s(n)=\sum_{i=0}^{d-1} a_i\), the target condition \(s(n)=s(137n)\) is equivalent to
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$$
that is, precisely
$$\boxed{\Delta_d=s(c_d).}$$
This is the key point: we never need the full product, only the final carry and the running digit-sum difference.
The carry is tightly bounded. If \(c_i\le 136\), then
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
Because \(c_0=0\), induction gives
$$0\le c_i\le 136\qquad \text{for all }i.$$
The difference \(\Delta_i\) also grows only linearly, since each step changes it by \(a_i-b_i\in[-9,9]\). So the reachable state space is tiny compared with \(10^{18}\) possibilities. The implementation uses a safe offset when packing \((carry,diff)\) into a hash-map key.
This is the smallest nonzero solution. We have
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
The DP sees this as one processed digit:
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
Hence
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
So the acceptance condition \(\Delta_1=s(c_1)\) holds exactly.
The code verifies the DP against brute force on smaller sizes:
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
After those checks, the program computes the required case
$$\text{solve}(18,137)=20444710234716473.$$
The implementation stores a hash map from packed keys \((carry,diff)\) to counts. For each of the \(18\) positions, it tries all \(10\) possible next digits, computes the new output digit and carry, updates the difference, and accumulates the new count. At the end it sums exactly those states for which diff == digit_sum(carry). A brute-force routine is included only for the small validation cases.
If \(S\) is the number of reachable \((carry,diff)\) states, then each layer tries \(10\) digits, so the running time is
$$O(d\cdot S\cdot 10),$$
with memory \(O(S)\). Here \(d=18\), and \(S\) is small because the carry is bounded by \(136\) and the difference range is narrow. This is exponentially smaller than testing all \(10^{18}\) candidates one by one.
Gesucht ist die Anzahl aller Dezimalstrings der Länge \(d=18\), also aller Zahlen \(0 \le n \lt 10^{18}\), für die
$$s(n)=s(137n)$$
gilt, wobei \(s(x)\) die Dezimalziffernsumme bezeichnet. Ein vollständiger Durchlauf über \(10^{18}\) Kandidaten ist unmöglich; man muss die Multiplikation stelleweise analysieren.
Schreibe
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$
Bei der Multiplikation mit \(m=137\) hängt die \(i\)-te Ausgabestelle nur von der aktuellen Ziffer \(a_i\) und dem eingehenden Übertrag \(c_i\) ab:
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
So entstehen die unteren \(d\) Stellen von \(137n\) sukzessive; alles oberhalb der Stelle \(d-1\) ist genau der Endübertrag \(c_d\).
Nach den ersten \(i\) Stellen definieren wir
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$
Dies ist die Differenz zwischen der bereits beigetragenen Ziffernsumme von \(n\) und der bereits beigetragenen Ziffernsumme des unteren Teils von \(137n\). Kennt man \((c_i,\Delta_i)\), dann hängt die Zukunft nicht mehr von den früheren Stellen einzeln ab. Daher genügt als DP-Zustand
$$\text{state}_i=(c_i,\Delta_i).$$
Wird als nächste Ziffer \(a_i\) gewählt, so entsteht Ausgabestelle \(b_i\), und damit
$$\Delta_{i+1}=\Delta_i+a_i-b_i.$$
Nach allen \(d\) Eingabestellen hat das Produkt die Form
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
Der erste Teil liefert Ziffernsumme \(\sum_{i=0}^{d-1} b_i\), der unverarbeitete Übertragsschwanz liefert \(s(c_d)\). Also
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
Da zugleich \(s(n)=\sum_{i=0}^{d-1} a_i\) gilt, ist die Zielgleichung \(s(n)=s(137n)\) äquivalent zu
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$$
also genau zu
$$\boxed{\Delta_d=s(c_d).}$$
Das ist der Kern der Lösung: Man braucht nicht das ganze Produkt, sondern nur Endübertrag und laufende Differenz.
Der Übertrag ist stark beschränkt. Gilt \(c_i\le 136\), dann folgt
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
Da \(c_0=0\), gilt induktiv
$$0\le c_i\le 136\qquad \text{für alle }i.$$
Auch \(\Delta_i\) wächst nur linear, denn pro Schritt ändert sich der Wert um \(a_i-b_i\in[-9,9]\). Deshalb ist der tatsächlich erreichbare Zustandsraum winzig im Vergleich zu \(10^{18}\) Kandidaten. Der Code verwendet beim Packen von \((carry,diff)\) in einen Schlüssel einfach einen großzügigen Offset.
Dies ist die kleinste nichttriviale Lösung. Es gilt
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
Im DP erscheint das als eine verarbeitete Stelle:
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
Also
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
Die Endbedingung \(\Delta_1=s(c_1)\) ist also exakt erfüllt.
Der Code prüft die DP zuerst gegen Bruteforce bei kleinen Größen:
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
Danach wird der eigentliche Zielwert berechnet:
$$\text{solve}(18,137)=20444710234716473.$$
Die Implementierung verwaltet eine Hash-Map von gepackten Zuständen \((carry,diff)\) auf Anzahlen. Für jede der \(18\) Stellen werden alle \(10\) möglichen nächsten Ziffern ausprobiert, die neue Ausgabestelle und der neue Übertrag berechnet, die Differenz aktualisiert und die Anzahl in der nächsten Tabelle akkumuliert. Am Ende werden genau die Zustände aufsummiert, für die diff == digit_sum(carry) gilt. Eine Bruteforce-Funktion existiert nur für die kleinen Prüfwerte.
Bezeichnet \(S\) die Zahl der erreichbaren Zustände \((carry,diff)\), so ist die Laufzeit
$$O(d\cdot S\cdot 10),$$
bei Speicherbedarf \(O(S)\). Hier ist \(d=18\), und \(S\) bleibt klein, weil der Übertrag durch \(136\) beschränkt ist und auch die Differenz nur in einem schmalen Bereich liegt. Das ist um Größenordnungen kleiner als ein Test aller \(10^{18}\) Zahlen.
İstenen şey, \(d=18\) uzunluğundaki tüm onluk dizgiler, yani \(0 \le n \lt 10^{18}\) aralığındaki tüm sayılar arasında
$$s(n)=s(137n)$$
koşulunu sağlayanların sayısıdır. Burada \(s(x)\) onluk basamak toplamıdır. \(10^{18}\) adayın tek tek denenmesi imkansız olduğu için çarpımı basamak basamak çözmek gerekir.
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}$$
olsun. \(m=137\) ile çarpımda \(i\). çıktı basamağı yalnızca o andaki girdi basamağı \(a_i\) ile taşıma \(c_i\)'ye bağlıdır:
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
Böylece \(137n\)'nin alt \(d\) basamağı tek tek üretilir; \(d-1\). basamağın üstünde kalan her şey tam olarak son taşıma \(c_d\)'dir.
İlk \(i\) basamak işlendiğinde
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j$$
tanımını yapalım. Bu, \(n\)'in şimdiye kadar eklenen basamak toplamı ile \(137n\)'nin şimdiye kadar eklenen alt basamak toplamı arasındaki farktır. \((c_i,\Delta_i)\) bilindiğinde, geleceğin önceki basamakların tam değerlerine artık ihtiyacı kalmaz. Bu yüzden DP durumu yalnızca
$$\text{state}_i=(c_i,\Delta_i)$$
olabilir. Yeni basamak \(a_i\) seçildiğinde üretilen çıktı basamağı \(b_i\) olur ve güncelleme
$$\Delta_{i+1}=\Delta_i+a_i-b_i$$
şeklindedir.
Tüm \(d\) girdi basamağı işlendiğinde çarpım şu biçimdedir:
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
İlk kısım \(\sum_{i=0}^{d-1} b_i\) kadar basamak toplamı verir; üstte kalan taşıma kuyruğu ise \(s(c_d)\) katkısı yapar. Dolayısıyla
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
Ayrıca \(s(n)=\sum_{i=0}^{d-1} a_i\) olduğundan, hedef eşitlik \(s(n)=s(137n)\) tam olarak
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d)$$
ile, yani
$$\boxed{\Delta_d=s(c_d)}$$
ile aynıdır. Çözümün püf noktası budur: tüm çarpımı saklamaya gerek yoktur; son taşıma ile yürüyen fark yeterlidir.
Taşıma ciddi biçimde sınırlıdır. Eğer \(c_i\le 136\) ise
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
\(c_0=0\) olduğundan tümevarımla
$$0\le c_i\le 136\qquad \text{her }i\text{ için}$$
elde edilir. \(\Delta_i\) de her adımda yalnızca \(a_i-b_i\in[-9,9]\) kadar değişir, yani doğrusal hızla büyür. Bu yüzden ulaşılabilen durum sayısı \(10^{18}\) olasılıktan çok daha küçüktür. Kod, \((carry,diff)\) çiftini hash anahtarına çevirirken güvenli bir offset kullanır.
Bu, sıfır dışındaki en küçük çözümdür:
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
DP açısından bu tek bir işlenmiş basamak demektir:
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
Buna göre
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
Yani kabul şartı \(\Delta_1=s(c_1)\) tam olarak sağlanır.
Kod, DP'yi önce küçük boyutlarda brute-force ile karşılaştırır:
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
Ardından istenen asıl değer hesaplanır:
$$\text{solve}(18,137)=20444710234716473.$$
Uygulama, hash-map içinde paketlenmiş \((carry,diff)\) anahtarlarını sayımlarla birlikte tutar. \(18\) basamağın her biri için olası \(10\) yeni rakam denenir; yeni çıktı rakamı ve yeni taşıma hesaplanır, fark güncellenir ve sonuç bir sonraki tabloya eklenir. Sonunda yalnızca diff == digit_sum(carry) koşulunu sağlayan durumların sayıları toplanır. Brute-force yordamı sadece küçük checkpoint doğrulamaları içindir.
Ulaşılabilen \((carry,diff)\) durum sayısı \(S\) olsun. Her katmanda \(10\) rakam denenir; dolayısıyla süre
$$O(d\cdot S\cdot 10)$$
ve bellek \(O(S)\) olur. Burada \(d=18\) ve \(S\) küçüktür; çünkü taşıma \(136\) ile sınırlıdır ve fark aralığı da dardır. Bu, tüm \(10^{18}\) adayı tek tek denemekten astronomik derecede daha küçüktür.
Debemos contar todas las cadenas decimales de longitud \(d=18\), es decir, todos los enteros \(0 \le n \lt 10^{18}\), que satisfacen
$$s(n)=s(137n),$$
donde \(s(x)\) es la suma de sus dígitos decimales. Recorrer \(10^{18}\) candidatos uno por uno es imposible, así que hay que analizar la multiplicación dígito a dígito.
Escribimos
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$
Al multiplicar por \(137\), el dígito de salida en la posición \(i\) depende solo del dígito actual \(a_i\) y del acarreo entrante \(c_i\):
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
Así se generan uno a uno los \(d\) dígitos bajos de \(137n\), y todo lo que quede por encima de la posición \(d-1\) es exactamente el acarreo final \(c_d\).
Tras procesar los primeros \(i\) dígitos, definimos
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$
Esta es la diferencia entre la suma de dígitos ya aportada por \(n\) y la suma de dígitos ya aportada por la parte baja de \(137n\). Una vez conocido \((c_i,\Delta_i)\), el futuro ya no depende de los dígitos anteriores individualmente. Por eso el estado del DP puede ser simplemente
$$\text{state}_i=(c_i,\Delta_i).$$
Si elegimos el siguiente dígito \(a_i\), el dígito producido es \(b_i\), y la actualización queda
$$\Delta_{i+1}=\Delta_i+a_i-b_i.$$
Después de consumir los \(d\) dígitos de entrada, el producto tiene la forma
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
La primera parte aporta suma de dígitos \(\sum_{i=0}^{d-1} b_i\), y la cola de acarreo aporta \(s(c_d)\). Por tanto
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
Como además \(s(n)=\sum_{i=0}^{d-1} a_i\), la igualdad objetivo \(s(n)=s(137n)\) equivale a
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$$
es decir, exactamente a
$$\boxed{\Delta_d=s(c_d).}$$
Ese es el paso decisivo: no hace falta guardar todo el producto, solo el acarreo final y la diferencia acumulada.
El acarreo está fuertemente acotado. Si \(c_i\le 136\), entonces
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
Como \(c_0=0\), por inducción se obtiene
$$0\le c_i\le 136\qquad \text{para todo }i.$$
Además, \(\Delta_i\) solo cambia por \(a_i-b_i\in[-9,9]\) en cada paso, así que también permanece en un rango estrecho. Por eso el número real de estados alcanzables es minúsculo comparado con \(10^{18}\). El código usa un desplazamiento seguro al empaquetar \((carry,diff)\) en una clave entera.
Esta es la solución no nula más pequeña:
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
En el DP esto corresponde a un único dígito procesado:
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
Entonces
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
La condición final \(\Delta_1=s(c_1)\) se cumple exactamente.
El código valida primero el DP frente a fuerza bruta en tamaños pequeños:
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
Después calcula el caso pedido:
$$\text{solve}(18,137)=20444710234716473.$$
La implementación mantiene una tabla hash desde claves empaquetadas \((carry,diff)\) hasta cantidades. Para cada una de las \(18\) posiciones prueba los \(10\) posibles dígitos siguientes, calcula el nuevo dígito de salida y el nuevo acarreo, actualiza la diferencia y acumula el nuevo conteo. Al final suma solo los estados que satisfacen diff == digit_sum(carry). La rutina de fuerza bruta se conserva únicamente para las validaciones pequeñas.
Si \(S\) es el número de estados alcanzables \((carry,diff)\), el tiempo total es
$$O(d\cdot S\cdot 10),$$
con memoria \(O(S)\). Aquí \(d=18\), y \(S\) es pequeño porque el acarreo está acotado por \(136\) y la diferencia también vive en un intervalo reducido. Es muchísimo menor que examinar los \(10^{18}\) candidatos directamente.
我们要统计所有长度为 \(d=18\) 的十进制串，也就是所有满足 \(0 \le n \lt 10^{18}\) 的整数，使得
$$s(n)=s(137n),$$
其中 \(s(x)\) 表示十进制数位和。显然不可能暴力枚举 \(10^{18}\) 个候选，所以必须把乘法拆成逐位递推。
写成
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$
乘以 \(137\) 时，第 \(i\) 位输出只依赖当前输入位 \(a_i\) 和进入该位的进位 \(c_i\)：
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
于是 \(137n\) 的低 \(d\) 位可以逐位生成，而高于第 \(d-1\) 位的剩余部分恰好就是最终进位 \(c_d\)。
处理完前 \(i\) 位以后，定义
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$
它表示目前为止 \(n\) 已贡献的数位和减去 \(137n\) 低位部分已贡献的数位和。一旦知道 \((c_i,\Delta_i)\)，未来就不再依赖更早的每一位具体是什么，因此动态规划状态只需要
$$\text{state}_i=(c_i,\Delta_i).$$
若下一位选 \(a_i\)，产生的输出位为 \(b_i\)，则更新为
$$\Delta_{i+1}=\Delta_i+a_i-b_i.$$
当 \(d\) 个输入位全部处理完后，乘积可以写成
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
第一部分的数位和是 \(\sum_{i=0}^{d-1} b_i\)，而上方未展开的进位尾巴贡献 \(s(c_d)\)。因此
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
另一方面 \(s(n)=\sum_{i=0}^{d-1} a_i\)，所以目标条件 \(s(n)=s(137n)\) 等价于
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$$
也就是
$$\boxed{\Delta_d=s(c_d).}$$
这就是核心简化：根本不需要保存整个乘积，只要保存最终进位和当前数位和差即可。
进位有很强的上界。若 \(c_i\le 136\)，则
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
由于 \(c_0=0\)，归纳可得
$$0\le c_i\le 136\qquad \text{对所有 }i.$$
同时 \(\Delta_i\) 每一步只会变化 \(a_i-b_i\in[-9,9]\)，因此范围也只是线性增长。可达状态数因此远小于 \(10^{18}\)。代码在把 \((carry,diff)\) 打包成整数键时，只是额外预留了一个安全偏移量。
这是最小的非零解：
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
在 DP 里，这对应处理一个数位：
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
于是
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
所以接受条件 \(\Delta_1=s(c_1)\) 被精确满足。
程序先用暴力校验较小规模：
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
然后计算题目需要的结果：
$$\text{solve}(18,137)=20444710234716473.$$
实现中用哈希表保存从打包状态 \((carry,diff)\) 到计数的映射。对 \(18\) 个位置逐层推进；每层尝试 \(10\) 个可能的新数字，算出新的输出位和新的进位，更新差值，再把方案数累加到下一层。最后只累加满足 diff == digit_sum(carry) 的状态。暴力函数只用于小规模 checkpoint 验证。
若可达状态数记为 \(S\)，则总时间为
$$O(d\cdot S\cdot 10),$$
空间为 \(O(S)\)。这里 \(d=18\)，而 \(S\) 很小，因为进位最多只有 \(136\)，差值范围也很窄。这比枚举全部 \(10^{18}\) 个数小了许多个数量级。
Нужно посчитать все десятичные строки длины \(d=18\), то есть все числа \(0 \le n \lt 10^{18}\), для которых
$$s(n)=s(137n),$$
где \(s(x)\) обозначает сумму десятичных цифр. Полный перебор \(10^{18}\) вариантов невозможен, поэтому нужно разобрать умножение поразрядно.
Запишем
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$
При умножении на \(137\) цифра результата в позиции \(i\) зависит только от текущей цифры \(a_i\) и входящего переноса \(c_i\):
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
Так по одной строятся младшие \(d\) цифр числа \(137n\), а всё, что лежит выше позиции \(d-1\), есть ровно финальный перенос \(c_d\).
После обработки первых \(i\) цифр введём
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$
Это разность между уже накопленной суммой цифр числа \(n\) и уже накопленной суммой цифр младшей части числа \(137n\). Как только известны \((c_i,\Delta_i)\), будущее уже не зависит от более ранних цифр по отдельности. Поэтому достаточно состояния
$$\text{state}_i=(c_i,\Delta_i).$$
Если следующая выбранная цифра равна \(a_i\), то порождаемая цифра результата равна \(b_i\), и обновление имеет вид
$$\Delta_{i+1}=\Delta_i+a_i-b_i.$$
После обработки всех \(d\) входных цифр произведение имеет форму
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
Первая часть даёт сумму цифр \(\sum_{i=0}^{d-1} b_i\), а хвост финального переноса даёт \(s(c_d)\). Следовательно,
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
Но \(s(n)=\sum_{i=0}^{d-1} a_i\), поэтому целевое условие \(s(n)=s(137n)\) эквивалентно
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$$
то есть просто
$$\boxed{\Delta_d=s(c_d).}$$
Это и есть ключевое упрощение: хранить всё произведение не нужно, достаточно финального переноса и накопленной разности.
Перенос сильно ограничен сверху. Если \(c_i\le 136\), то
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
Поскольку \(c_0=0\), по индукции получаем
$$0\le c_i\le 136\qquad \text{для всех }i.$$
Разность \(\Delta_i\) тоже растёт лишь линейно, потому что на каждом шаге меняется на \(a_i-b_i\in[-9,9]\). Поэтому число реально достижимых состояний крошечно по сравнению с \(10^{18}\) кандидатами. В коде при упаковке \((carry,diff)\) в ключ просто используется безопасный сдвиг.
Это минимальное ненулевое решение:
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
С точки зрения DP это один обработанный разряд:
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
Отсюда
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
Именно поэтому условие принятия \(\Delta_1=s(c_1)\) выполнено.
Сначала программа сверяет DP с брутфорсом на малых размерах:
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
После этого вычисляется требуемый ответ:
$$\text{solve}(18,137)=20444710234716473.$$
В реализации хранится хеш-таблица из упакованных ключей \((carry,diff)\) в число способов. Для каждой из \(18\) позиций перебираются все \(10\) возможных следующих цифр, вычисляются новая выходная цифра и новый перенос, обновляется разность, и количество добавляется в следующий слой таблицы. В конце суммируются только те состояния, для которых выполняется diff == digit_sum(carry). Отдельная функция полного перебора используется лишь для малых проверок.
Если \(S\) — число достижимых состояний \((carry,diff)\), то время работы равно
$$O(d\cdot S\cdot 10),$$
а память — \(O(S)\). Здесь \(d=18\), и \(S\) мало, потому что перенос ограничен числом \(136\), а диапазон разности тоже узок. Это несравнимо лучше, чем проверять все \(10^{18}\) чисел по отдельности.
نريد عدّ جميع السلاسل العشرية ذات الطول \(d=18\)، أي جميع الأعداد \(0 \le n \lt 10^{18}\)، التي تحقق
$$s(n)=s(137n),$$
حيث \(s(x)\) تمثل مجموع الأرقام العشرية. وبما أن الفحص المباشر لـ \(10^{18}\) حالة غير ممكن، فلا بد من تحليل عملية الضرب خانةً بخانة.
نكتب
$$n=\sum_{i=0}^{d-1} a_i 10^i,\qquad a_i\in\{0,\dots,9\}.$$
عند الضرب في \(137\)، فإن رقم الخرج في الخانة \(i\) يعتمد فقط على الرقم الحالي \(a_i\) والحمل الداخل \(c_i\):
$$t_i=137a_i+c_i,\qquad b_i=t_i\bmod 10,\qquad c_{i+1}=\left\lfloor \frac{t_i}{10}\right\rfloor.$$
وهكذا تتولد الخانات الدنيا من \(137n\) واحدةً بعد أخرى، وما يبقى فوق الخانة \(d-1\) هو تمامًا الحمل النهائي \(c_d\).
بعد معالجة أول \(i\) خانات نعرّف
$$\Delta_i=\sum_{j=0}^{i-1} a_j-\sum_{j=0}^{i-1} b_j.$$
وهذا هو الفرق بين مجموع الأرقام الذي ساهم به \(n\) حتى الآن، ومجموع الأرقام الذي ساهم به الجزء السفلي من \(137n\) حتى الآن. فإذا عرفنا \((c_i,\Delta_i)\)، لم نعد بحاجة إلى تفاصيل الخانات الأقدم على حدة. لذلك يمكن أن تكون حالة البرمجة الديناميكية ببساطة
$$\text{state}_i=(c_i,\Delta_i).$$
وعند اختيار الخانة التالية \(a_i\)، يكون رقم الخرج الناتج هو \(b_i\)، وبالتالي يصبح التحديث
$$\Delta_{i+1}=\Delta_i+a_i-b_i.$$
بعد معالجة جميع خانات الإدخال \(d\)، يكون حاصل الضرب على الصورة
$$137n=\sum_{i=0}^{d-1} b_i10^i+c_d10^d.$$
الجزء الأول يساهم بمجموع أرقام مقداره \(\sum_{i=0}^{d-1} b_i\)، أما ذيل الحمل غير المعالج فيساهم بمقدار \(s(c_d)\). لذلك
$$s(137n)=\sum_{i=0}^{d-1} b_i+s(c_d).$$
وبما أن \(s(n)=\sum_{i=0}^{d-1} a_i\)، فإن الشرط المطلوب \(s(n)=s(137n)\) يكافئ
$$\sum_{i=0}^{d-1} a_i-\sum_{i=0}^{d-1} b_i=s(c_d),$$
أي بالضبط
$$\boxed{\Delta_d=s(c_d).}$$
هذه هي الفكرة الأساسية: لا حاجة لتخزين حاصل الضرب كله، بل يكفي الحمل النهائي مع الفرق المتراكم.
الحمل محدود جدًا. فإذا كان \(c_i\le 136\)، فإن
$$c_{i+1}\le \left\lfloor\frac{137\cdot 9+136}{10}\right\rfloor=136.$$
ومع \(c_0=0\) نحصل بالاستقراء على
$$0\le c_i\le 136\qquad \text{لكل }i.$$
أما \(\Delta_i\) فلا يتغير في كل خطوة إلا بمقدار \(a_i-b_i\in[-9,9]\)، ولذلك يبقى ضمن مجال ضيق نسبيًا. لهذا يكون عدد الحالات القابلة للوصول صغيرًا جدًا مقارنةً بـ \(10^{18}\). ويستعمل الكود إزاحة آمنة عند ضغط الزوج \((carry,diff)\) في مفتاح واحد.
هذا أصغر حل غير صفري:
$$137\cdot 9=1233,\qquad s(9)=9,\qquad s(1233)=1+2+3+3=9.$$
ومن منظور DP فهذا يعني معالجة خانة واحدة:
$$t_0=137\cdot 9+0=1233,\qquad b_0=3,\qquad c_1=123.$$
إذن
$$\Delta_1=9-3=6,\qquad s(c_1)=s(123)=6.$$
وبالتالي يتحقق شرط القبول \(\Delta_1=s(c_1)\) تمامًا.
يقارن الكود أولًا نتيجة DP مع brute force في أحجام صغيرة:
$$\text{solve}(4,137)=306,\qquad \text{solve}(5,137)=2902.$$
ثم يحسب الحالة المطلوبة:
$$\text{solve}(18,137)=20444710234716473.$$
يحافظ التنفيذ على جدول تجزئة يربط المفتاح المضغوط \((carry,diff)\) بعدد الطرق. وفي كل واحدة من الخانات الثماني عشرة، يجرّب الأرقام العشرة الممكنة، ثم يحسب رقم الخرج الجديد والحمل الجديد، ويحدّث الفرق، ويضيف عدد الطرق إلى الطبقة التالية. وفي النهاية يجمع فقط الحالات التي تحقق diff == digit_sum(carry). أما دالة brute-force فهي موجودة فقط للتحقق من الأمثلة الصغيرة.
إذا كان عدد الحالات القابلة للوصول هو \(S\)، فإن الزمن الكلي يساوي
$$O(d\cdot S\cdot 10),$$
والذاكرة \(O(S)\). هنا \(d=18\)، و\(S\) صغير لأن الحمل لا يتجاوز \(136\) ومجال الفرق ضيق كذلك. وهذا أصغر بشكل هائل من فحص جميع \(10^{18}\) عددًا مباشرة.