For each integer \(0 \le n < 10^{20}\), write its 20-digit decimal expansion \(d_{19}d_{18}\dots d_0\), allowing leading zeros. Define
$$f(n)=\sum_{i=0}^{19} d_i^2.$$
The task is to add all numbers \(n\) for which \(f(n)\) is a perfect square and keep only the last nine digits of that total. Direct enumeration is impossible because there are \(10^{20}\) candidates. The useful observation is that the condition depends only on the accumulated square-digit-sum, while the requested output is itself a sum over the actual decimal values.
Let \(L=20\) and \(M=10^9\). Since each digit contributes at most \(9^2=81\), the largest possible value of \(f(n)\) is \(20\cdot 81=1620\). That means the entire state space for the square-digit-sum has only 1621 possibilities, which is small enough for a complete dynamic program.
For each \(\ell\in\{0,1,\dots,20\}\) and each \(t\in\{0,1,\dots,1620\}\), let \(A_{\ell,t}\) be the set of integers \(x\) with \(0 \le x < 10^\ell\) whose \(\ell\)-digit expansion, padded with leading zeros if necessary, has square-digit-sum \(t\). Thinking in fixed length is exactly what the problem needs: every number below \(10^{20}\) is represented once as a 20-digit string, and the all-zero string contributes value 0 anyway.
The implementations store two pieces of information for every state:
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
The first table counts how many \(\ell\)-digit strings reach square-digit-sum \(t\). The second table is more important for the final goal: it already accumulates the sum of their numeric values. The base state is
$$C_0(0)=1,\qquad V_0(0)=0,$$
with every other state at length 0 equal to 0. Because the final answer is needed only modulo \(10^9\), both tables can be reduced modulo \(M\) throughout; every later use of the tables is linear in these values, so modular reduction preserves correctness.
Build length \(\ell\) from length \(\ell-1\) by choosing a new most significant digit \(d\in\{0,\dots,9\}\). If the old \((\ell-1)\)-digit part had square-digit-sum \(t-d^2\), then the new \(\ell\)-digit number has square-digit-sum \(t\). Therefore
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$$
where terms with negative arguments are omitted.
Now take the value sum. If \(x\in A_{\ell-1,t-d^2}\), then after adding digit \(d\) on the left, the new number is
$$x+d\cdot 10^{\ell-1}.$$
Summing this over all old states gives the second recurrence:
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$$
The second term is the key invariant of the whole solution: when the new leading digit is fixed, its place-value contribution must be added once for every shorter string counted by \(C_{\ell-1}(t-d^2)\).
The 2-digit strings whose square-digit-sum is 9 are exactly \(03\) and \(30\). Hence we expect
$$C_2(9)=2,\qquad V_2(9)=3+30=33.$$
The recurrence reproduces this cleanly. The count is
$$C_2(9)=C_1(9)+C_1(0)=1+1=2,$$
because the only possibilities are prepending 0 to the 1-digit string \(3\), or prepending 3 to the 1-digit string \(0\). For the value sum,
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$$
This small case shows why a count table alone is not enough: the problem asks for the sum of the qualifying numbers, not just their number.
A perfect square state can only be \(r^2\) with \(1 \le r \le 40\), because \(40^2=1600 \le 1620\) while \(41^2=1681\) is already too large. So the desired result is
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$$
The omitted state \(r=0\) corresponds only to the number 0, whose contribution is 0, so including or excluding it makes no difference.
The C++, Python, and Java implementations follow the recurrence directly. They first precompute the powers \(10^0,10^1,\dots,10^{19}\) modulo \(10^9\), because each transition needs the place value of the newly added digit. Next they allocate two tables indexed by digit length and square-digit-sum, initialize the empty-string base state, and iterate through all lengths from 1 to 20.
For every length, every digit \(0,\dots,9\), and every reachable square-digit-sum, the implementation updates the count table and the value table together. The count update records how many shorter strings can be extended, and the value update adds both the previous suffix sum and the new decimal-place contribution. After the tables for length 20 are complete, the implementation scans only the square targets \(1,4,9,\dots,1600\) and accumulates their stored value sums. The C++ implementation also includes short brute-force checkpoints for small lengths to verify that the DP matches exhaustive enumeration before solving the full 20-digit case.
The loops run over \(L=20\) digit lengths, 10 possible digits, and at most \(81L+1=1621\) square-digit-sum states. This gives time complexity
$$O(L\cdot 10\cdot 81L)=O(L^2).$$
The implementations keep the full two-dimensional tables for all lengths, so the memory usage is
$$O(L\cdot 81L).$$
Even without rolling arrays, this is tiny compared with brute force over \(10^{20}\) numbers.
Für jede ganze Zahl \(0 \le n < 10^{20}\) betrachten wir ihre 20-stellige Dezimaldarstellung \(d_{19}d_{18}\dots d_0\), wobei führende Nullen erlaubt sind. Definiert ist
$$f(n)=\sum_{i=0}^{19} d_i^2.$$
Gesucht ist die Summe aller Zahlen \(n\), für die \(f(n)\) eine Quadratzahl ist, und zwar nur mit ihren letzten neun Dezimalstellen. Eine direkte Suche über \(10^{20}\) Kandidaten ist ausgeschlossen. Entscheidend ist, dass die Bedingung nur von der aufsummierten Ziffernquadratsumme abhängt, während die Ausgabe selbst eine Summe der zugehörigen Zahlenwerte ist.
Setze \(L=20\) und \(M=10^9\). Da jede Ziffer höchstens \(9^2=81\) beiträgt, ist der maximale Wert von \(f(n)\) gleich \(20\cdot 81=1620\). Es gibt also nur 1621 mögliche Zustände für die Ziffernquadratsumme, und genau darauf baut die dynamische Programmierung auf.
Für jedes \(\ell\in\{0,1,\dots,20\}\) und jedes \(t\in\{0,1,\dots,1620\}\) sei \(A_{\ell,t}\) die Menge aller Zahlen \(x\) mit \(0 \le x < 10^\ell\), deren \(\ell\)-stellige Darstellung mit nötigen führenden Nullen Ziffernquadratsumme \(t\) besitzt. Genau so muss man die Aufgabe lesen: Jede Zahl unter \(10^{20}\) erscheint genau einmal als 20-stellige Folge, und die Folge aus lauter Nullen trägt ohnehin nur den Wert 0 bei.
Die Implementierungen speichern für jeden Zustand zwei Größen:
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
\(C_\ell(t)\) zählt, wie viele \(\ell\)-stellige Folgen die Quadratsumme \(t\) erreichen. \(V_\ell(t)\) summiert bereits die eigentlichen Zahlenwerte dieser Folgen. Der Anfangszustand ist
$$C_0(0)=1,\qquad V_0(0)=0,$$
während alle anderen Zustände bei Länge 0 gleich 0 sind. Weil nur die letzten neun Stellen des Endergebnisses verlangt werden, dürfen beide Tabellen während der gesamten Rechnung modulo \(M\) geführt werden. Alle späteren Verwendungen bestehen nur aus Additionen und Multiplikationen, also ist diese Reduktion verträglich mit der Herleitung.
Man erzeugt Länge \(\ell\) aus Länge \(\ell-1\), indem man eine neue führende Ziffer \(d\in\{0,\dots,9\}\) wählt. Hatte der alte \((\ell-1)\)-stellige Teil Quadratsumme \(t-d^2\), dann hat die neue \(\ell\)-stellige Zahl Quadratsumme \(t\). Also gilt
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$$
wobei Terme mit negativem Argument wegfallen.
Für die Wertsumme betrachtet man, dass aus einem alten Wert \(x\) durch Voranstellen von \(d\) die Zahl
$$x+d\cdot 10^{\ell-1}$$
wird. Summiert über alle alten Zustände erhält man
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$$
Gerade der zweite Summand ist der zentrale Punkt: Der neue Stellenwertbeitrag muss einmal für jede kürzere Zahl addiert werden, die in \(C_{\ell-1}(t-d^2)\) gezählt wird.
Die einzigen 2-stelligen Folgen mit Ziffernquadratsumme 9 sind \(03\) und \(30\). Deshalb erwarten wir
$$C_2(9)=2,\qquad V_2(9)=3+30=33.$$
Die Rekurrenz liefert genau dasselbe. Für die Anzahl gilt
$$C_2(9)=C_1(9)+C_1(0)=1+1=2,$$
denn entweder stellt man 0 vor die 1-stellige Folge \(3\), oder 3 vor die 1-stellige Folge \(0\). Für die Wertsumme ergibt sich
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$$
Dieses kleine Beispiel zeigt sehr klar, warum eine reine Zähltabelle nicht genügt: Die Aufgabe verlangt die Summe der passenden Zahlen, nicht nur ihre Anzahl.
Ein quadratischer Zustand kann nur \(r^2\) mit \(1 \le r \le 40\) sein, denn \(40^2=1600 \le 1620\), aber \(41^2=1681\) ist schon zu groß. Deshalb ist das gesuchte Ergebnis
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$$
Der ausgelassene Fall \(r=0\) entspräche nur der Zahl 0 und ändert die Summe daher nicht.
Die C++-, Python- und Java-Implementierungen setzen diese Rekurrenz unmittelbar um. Zuerst werden die Potenzen \(10^0,10^1,\dots,10^{19}\) modulo \(10^9\) vorbereitet, weil jeder Übergang den Stellenwert der neu hinzugefügten Ziffer braucht. Danach werden zwei Tabellen über Ziffernlänge und Ziffernquadratsumme angelegt, der leere Anfangszustand wird eingetragen, und die Längen 1 bis 20 werden nacheinander aufgebaut.
Für jede Länge, jede Ziffer \(0,\dots,9\) und jede erreichbare Quadratsumme werden beide Tabellen gleichzeitig aktualisiert. Die Zähltabelle übernimmt die alte Multiplizität, und die Werttabelle erhält sowohl die bereits vorhandene Suffixsumme als auch den neuen Stellenwertbeitrag. Wenn die Tabellen für Länge 20 fertig sind, werden nur noch die Quadratziele \(1,4,9,\dots,1600\) durchlaufen und ihre gespeicherten Wertsummen addiert. Die C++-Variante enthält zusätzlich kleine exhaustive Tests für kurze Längen, um die DP-Idee vor dem eigentlichen 20-stelligen Lauf gegen vollständige Enumeration zu prüfen.
Die Schleifen laufen über \(L=20\) Längen, 10 mögliche Ziffern und höchstens \(81L+1=1621\) Zustände der Ziffernquadratsumme. Daraus folgt die Laufzeit
$$O(L\cdot 10\cdot 81L)=O(L^2).$$
Die Implementierungen speichern die vollständigen zweidimensionalen Tabellen für alle Längen, also ist der Speicherbedarf
$$O(L\cdot 81L).$$
Selbst ohne Speicherkompression ist das verschwindend klein im Vergleich zu einem direkten Durchlauf über \(10^{20}\) Zahlen.
Her \(0 \le n < 10^{20}\) tamsayısını, baştaki sıfırlara izin vererek \(d_{19}d_{18}\dots d_0\) biçiminde 20 basamaklı olarak yazalım. Tanım
$$f(n)=\sum_{i=0}^{19} d_i^2$$
olsun. Amaç, \(f(n)\) değeri tam kare olan tüm \(n\) sayılarının toplamını bulup bu toplamın sadece son dokuz basamağını almaktır. \(10^{20}\) olası aday olduğu için doğrudan tarama yapılamaz. Asıl fikir şudur: koşul yalnızca biriken basamak kareleri toplamına bağlıdır, ama istenen çıktı bu koşulu sağlayan sayıların değer toplamıdır.
\(L=20\) ve \(M=10^9\) yazalım. Her basamak en fazla \(9^2=81\) katkı yapacağı için \(f(n)\) en çok \(20\cdot 81=1620\) olabilir. Dolayısıyla DP durum uzayı yalnızca 1621 farklı kareler-toplamı değerinden oluşur; çözümün verimli olmasının nedeni tam olarak budur.
Her \(\ell\in\{0,1,\dots,20\}\) ve her \(t\in\{0,1,\dots,1620\}\) için, \(A_{\ell,t}\) kümesi \(0 \le x < 10^\ell\) koşulunu sağlayan ve gerekirse başına sıfır eklenmiş \(\ell\) basamaklı yazımının basamak kareleri toplamı \(t\) olan tüm \(x\) sayılarından oluşsun. Soruyu bu biçimde okumak doğrudur; çünkü \(10^{20}\)'den küçük her sayı tek bir 20 basamaklı gösterime sahiptir ve bütün basamakları 0 olan tek durum zaten toplamda 0 katkı verir.
Uygulamalar her durum için iki bilgi tutar:
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
\(C_\ell(t)\), kareler toplamı \(t\) olan \(\ell\) basamaklı gösterimlerin sayısıdır. \(V_\ell(t)\) ise bu gösterimlerin gerçek sayı değerlerinin toplamıdır. Başlangıç durumu
$$C_0(0)=1,\qquad V_0(0)=0$$
şeklindedir; uzunluk 0 için diğer tüm durumlar 0'dır. Sonuç sadece \(10^9\) modunda istendiği için iki tablo da baştan sona mod \(M\) altında tutulabilir. Bunun güvenli olmasının nedeni, sonraki tüm geçişlerin bu tablolara yalnızca toplama ve çarpma ile başvurmasıdır.
Uzunluğu \(\ell\) olan bir sayıyı, uzunluğu \(\ell-1\) olan bir sayının soluna yeni bir basamak \(d\in\{0,\dots,9\}\) ekleyerek kuruyoruz. Eski \((\ell-1)\) basamaklı parça \(t-d^2\) kareler-toplamına sahipse yeni sayı \(t\) durumuna geçer. Bu yüzden
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2)$$
olur; negatif argümanlı terimler doğal olarak yok sayılır.
Değer toplamı için de eski sayı \(x\) ise yeni sayı
$$x+d\cdot 10^{\ell-1}$$
şeklindedir. Bunu tüm uygun eski durumlar üzerinde toplarsak
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}$$
bağıntısını elde ederiz. Çözümün kalbi bu ikinci terimdir: yeni sol basamağın basamak değeri, o geçişi mümkün kılan her kısa sayı için bir kez eklenmelidir.
Basamak kareleri toplamı 9 olan 2 basamaklı diziler yalnızca \(03\) ve \(30\)'dur. Dolayısıyla
$$C_2(9)=2,\qquad V_2(9)=3+30=33$$
bekleriz. Rekürans tam bunu verir. Önce adet:
$$C_2(9)=C_1(9)+C_1(0)=1+1=2.$$
Burada bir seçenek 1 basamaklı \(3\)'ün soluna 0 eklemek, diğeri 1 basamaklı \(0\)'ın soluna 3 eklemektir. Değer toplamı ise
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33$$
olur. Bu küçük örnek, neden yalnızca sayım tablosunun yetmediğini açıkça gösterir.
Tam kare durumları yalnızca \(1 \le r \le 40\) için \(r^2\) olabilir; çünkü \(40^2=1600 \le 1620\) ama \(41^2=1681\) üst sınırı aşar. Bu nedenle aranan değer
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}$$
şeklindedir. \(r=0\) hali sadece 0 sayısını verdiği için toplamı değiştirmez.
C++, Python ve Java uygulamaları bu matematiği doğrudan uygular. Önce \(10^0,10^1,\dots,10^{19}\) kuvvetleri \(10^9\) modunda önceden hesaplanır; çünkü her geçişte yeni eklenen basamağın hangi onluk kuvvetiyle çarpılacağı gerekir. Ardından uzunluk ve kareler-toplamı ile indekslenen iki tablo oluşturulur, boş dizi başlangıç durumu yazılır ve uzunluklar 1'den 20'ye kadar sırayla işlenir.
Her uzunlukta, her basamak \(0,\dots,9\) için ve erişilebilen her kareler-toplamı durumunda iki tablo birlikte güncellenir. Sayım tablosu eski çokluğu taşır; değer tablosu ise hem eski kısa sayıların toplamını hem de yeni basamağın uygun basamak değeri katkısını ekler. Uzunluk 20 tamamlandığında yalnızca kare hedefler \(1,4,9,\dots,1600\) taranır ve bu durumların değer toplamları biriktirilir. C++ sürümü ayrıca küçük uzunluklarda DP sonucunu tam taramayla karşılaştıran kısa doğrulama kontrolleri de içerir.
Döngüler \(L=20\) uzunluk katmanı, 10 olası basamak ve en fazla \(81L+1=1621\) kareler-toplamı durumu üzerinde çalışır. Zaman karmaşıklığı bu yüzden
$$O(L\cdot 10\cdot 81L)=O(L^2)$$
olur. Uygulamalar bütün uzunluklar için tam iki boyutlu tabloları tuttuğundan bellek kullanımı da
$$O(L\cdot 81L)$$
düzeyindedir. Bu maliyet, \(10^{20}\) sayıyı tek tek denemeye kıyasla ihmal edilecek kadar küçüktür.
Para cada entero \(0 \le n < 10^{20}\), escribimos su expansión decimal de 20 cifras \(d_{19}d_{18}\dots d_0\), permitiendo ceros a la izquierda. Definimos
$$f(n)=\sum_{i=0}^{19} d_i^2.$$
Hay que sumar todos los números \(n\) para los cuales \(f(n)\) es un cuadrado perfecto y conservar solo las últimas nueve cifras de esa suma. Un barrido directo es imposible porque existirían \(10^{20}\) candidatos. La observación clave es que la condición depende únicamente de la suma acumulada de cuadrados de dígitos, mientras que la salida pedida es la suma de los propios valores decimales.
Tomemos \(L=20\) y \(M=10^9\). Como cada dígito aporta a lo sumo \(9^2=81\), el valor máximo posible de \(f(n)\) es \(20\cdot 81=1620\). Por tanto, el espacio de estados para la suma de cuadrados tiene solo 1621 posibilidades, lo cual permite una programación dinámica completa.
Para cada \(\ell\in\{0,1,\dots,20\}\) y cada \(t\in\{0,1,\dots,1620\}\), sea \(A_{\ell,t}\) el conjunto de enteros \(x\) con \(0 \le x < 10^\ell\) cuya representación decimal de longitud \(\ell\), rellenada con ceros a la izquierda si hace falta, tiene suma de cuadrados de dígitos igual a \(t\). Esta es exactamente la interpretación correcta del problema: cada número menor que \(10^{20}\) aparece una sola vez como cadena de 20 cifras, y la cadena completamente nula aporta valor 0.
Las implementaciones guardan dos datos por estado:
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
\(C_\ell(t)\) cuenta cuántas cadenas de longitud \(\ell\) alcanzan la suma \(t\). \(V_\ell(t)\) acumula la suma de sus valores numéricos, que es justamente la magnitud que al final queremos agregar sobre los estados cuadrados. El estado base es
$$C_0(0)=1,\qquad V_0(0)=0,$$
y todos los demás estados con \(\ell=0\) valen 0. Como el problema solo pide las últimas nueve cifras, ambas tablas pueden mantenerse módulo \(M\) en todo momento. Eso es correcto porque después solo se combinan mediante sumas y productos.
Construimos longitud \(\ell\) a partir de longitud \(\ell-1\) eligiendo un nuevo dígito más significativo \(d\in\{0,\dots,9\}\). Si la parte antigua tenía suma de cuadrados \(t-d^2\), la nueva tiene suma \(t\). Por ello
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$$
omitiendo los términos con argumento negativo.
Para la suma de valores, si \(x\in A_{\ell-1,t-d^2}\), al colocar \(d\) a la izquierda obtenemos
$$x+d\cdot 10^{\ell-1}.$$
Al sumar sobre todos los estados previos aparece la segunda recurrencia:
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$$
Ese segundo término es la parte esencial de la derivación: el nuevo dígito fijo contribuye con el mismo valor posicional una vez por cada sufijo contado en \(C_{\ell-1}(t-d^2)\).
Las únicas cadenas de 2 cifras cuya suma de cuadrados es 9 son \(03\) y \(30\). Luego
$$C_2(9)=2,\qquad V_2(9)=3+30=33.$$
La recurrencia da exactamente eso. Para la cantidad,
$$C_2(9)=C_1(9)+C_1(0)=1+1=2,$$
porque solo podemos anteponer 0 a la cadena \(3\) o anteponer 3 a la cadena \(0\). Para la suma de valores,
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$$
Este ejemplo pequeño deja claro por qué contar no basta: el problema pide la suma de todos los números válidos.
Un estado cuadrado perfecto solo puede ser \(r^2\) con \(1 \le r \le 40\), ya que \(40^2=1600 \le 1620\) y \(41^2=1681\) ya rebasa el máximo. Por tanto, el resultado buscado es
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$$
El caso \(r=0\) corresponde únicamente al número 0 y no altera la suma.
Las implementaciones en C++, Python y Java siguen esta derivación casi línea por línea. Primero precalculan \(10^0,10^1,\dots,10^{19}\) módulo \(10^9\), porque cada transición necesita el valor posicional del nuevo dígito añadido. Después reservan dos tablas indexadas por longitud y por suma de cuadrados de dígitos, fijan el estado base de la cadena vacía y recorren las longitudes desde 1 hasta 20.
Para cada longitud, para cada dígito \(0,\dots,9\) y para cada suma alcanzable, la implementación actualiza ambas tablas a la vez. La tabla de conteos recibe la multiplicidad del estado previo, y la tabla de sumas recibe tanto la suma previa de sufijos como la contribución decimal del nuevo dígito. Una vez completada la longitud 20, solo se recorren los objetivos cuadrados \(1,4,9,\dots,1600\) y se suman sus valores almacenados. La versión en C++ añade además pequeñas comprobaciones exhaustivas en longitudes cortas para verificar la DP antes del cálculo principal.
Los bucles recorren \(L=20\) longitudes, 10 posibles dígitos y a lo sumo \(81L+1=1621\) estados de suma de cuadrados. Por eso el coste temporal es
$$O(L\cdot 10\cdot 81L)=O(L^2).$$
Las implementaciones guardan las tablas bidimensionales completas para todas las longitudes, así que el consumo de memoria es
$$O(L\cdot 81L).$$
Incluso sin comprimir memoria, este coste es minúsculo frente a enumerar explícitamente \(10^{20}\) números.
对每个满足 \(0 \le n < 10^{20}\) 的整数，都把它写成允许前导零的 20 位十进制表示 \(d_{19}d_{18}\dots d_0\)。定义
$$f(n)=\sum_{i=0}^{19} d_i^2.$$
题目要求把所有满足 \(f(n)\) 为完全平方数的 \(n\) 加起来，并且只保留这个总和的最后九位。显然不可能直接枚举 \(10^{20}\) 个候选数。真正可用的观察是：判定条件只依赖于“各位数字平方和”这个聚合量，而目标输出却是所有满足条件的十进制数值之和，因此动态规划必须同时跟踪“有多少个数”和“这些数本身加起来是多少”。
记 \(L=20\)，\(M=10^9\)。每一位数字对 \(f(n)\) 的最大贡献是 \(9^2=81\)，所以 \(f(n)\) 的上界为 \(20\cdot 81=1620\)。这意味着关于平方和的状态总数只有 1621 个，规模非常小，足以做完整的数位动态规划。
对每个 \(\ell\in\{0,1,\dots,20\}\) 和每个 \(t\in\{0,1,\dots,1620\}\)，定义 \(A_{\ell,t}\) 为所有满足 \(0 \le x < 10^\ell\) 的整数集合，并要求 \(x\) 的 \(\ell\) 位十进制表示在必要时左侧补零后，其各位数字平方和恰好等于 \(t\)。这样建模与原题完全一致：每个小于 \(10^{20}\) 的整数都唯一对应一个 20 位串，而全零串本身的数值是 0，即使算进去也不会影响最后的和。
实现并不是只维护一个计数表，而是对每个状态同时维护下面两个量：
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
其中 \(C_\ell(t)\) 表示长度为 \(\ell\) 的数字串中，有多少个会落到平方和状态 \(t\)；\(V_\ell(t)\) 表示这些数字串对应的十进制整数之和。初始条件是
$$C_0(0)=1,\qquad V_0(0)=0,$$
长度为 0 的其他状态全部为 0。由于题目只需要最后九位，整个过程中都可以把这两个表按模 \(M\) 存储。这种做法是安全的，因为后续对这些表的使用只有加法和乘法，也就是模运算下保持线性的操作。
把长度为 \(\ell\) 的数看成：在一个长度为 \(\ell-1\) 的数左边再加上一位新数字 \(d\in\{0,\dots,9\}\)。如果原来较短部分的平方和是 \(t-d^2\)，那么加上这一位之后，新的平方和就是 \(t\)。因此计数满足
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$$
其中参数为负数的项直接视为不存在。
接下来考虑数值和。若旧状态中的一个数是 \(x\)，在左边添上数字 \(d\) 后，新数变成
$$x+d\cdot 10^{\ell-1}.$$
把这件事对所有旧状态求和，就得到第二个递推式：
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$$
这里最关键的是第二项。对于固定的新最高位 \(d\)，它带来的十进制位权贡献 \(d\cdot 10^{\ell-1}\) 需要按可接上的所有旧串数量重复累加一次，而这个数量恰好就是 \(C_{\ell-1}(t-d^2)\)。
平方和等于 9 的 2 位串只有 \(03\) 和 \(30\)。因此我们应当得到
$$C_2(9)=2,\qquad V_2(9)=3+30=33.$$
递推确实给出完全相同的结果。计数部分为
$$C_2(9)=C_1(9)+C_1(0)=1+1=2,$$
因为唯一两种构造方式分别是：把 0 添到数字 3 的左边，或者把 3 添到数字 0 的左边。数值和部分则是
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$$
这个小例子清楚说明了为什么单独维护计数是不够的：题目不是问有多少个满足条件的数，而是问这些数加起来等于多少。
最终只关心完全平方数状态。由于 \(40^2=1600 \le 1620\)，而 \(41^2=1681 > 1620\)，所以可能的平方状态只有 \(r^2\)（其中 \(1 \le r \le 40\)）。因此答案就是
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$$
之所以没有写 \(r=0\)，只是因为那个状态只对应数字 0，而它对总和的贡献本来就是 0。
C++、Python 和 Java 三个实现都几乎逐字照着这个推导来写。它们先预计算 \(10^0,10^1,\dots,10^{19}\) 在模 \(10^9\) 下的值，因为每次转移都要知道新加入数字所在的十进制位权。随后分配两个按“长度”和“平方和”索引的表，写入空串对应的初始状态，再把长度从 1 一直推进到 20。
在每一层长度上，实现都会枚举新加入的数字 \(0,\dots,9\)，再枚举所有可达的平方和状态，同时更新计数表与数值和表。计数表吸收前一层的可行方案数，数值和表则额外加上新最高位带来的十进制贡献。20 位全部处理完之后，只需扫描平方目标 \(1,4,9,\dots,1600\)，把这些状态中存下来的数值和累加起来即可。C++ 版本还附带了几个短长度的暴力核对步骤，用来确认动态规划结果与完全枚举一致。
总共要枚举 \(L=20\) 个长度层、10 个可能数字，以及最多 \(81L+1=1621\) 个平方和状态，所以时间复杂度为
$$O(L\cdot 10\cdot 81L)=O(L^2).$$
实现保留了所有长度层的完整二维表，因此空间复杂度为
$$O(L\cdot 81L).$$
即使不做滚动数组压缩，这个代价与直接枚举 \(10^{20}\) 个整数相比也几乎可以忽略不计。
Для каждого целого числа \(0 \le n < 10^{20}\) рассмотрим его 20-значную десятичную запись \(d_{19}d_{18}\dots d_0\), разрешая ведущие нули. Определим
$$f(n)=\sum_{i=0}^{19} d_i^2.$$
Нужно просуммировать все числа \(n\), для которых \(f(n)\) является полным квадратом, и оставить только последние девять цифр этой суммы. Перебирать \(10^{20}\) кандидатов напрямую невозможно. Ключевое наблюдение состоит в том, что условие зависит только от накопленной суммы квадратов цифр, а искомая величина сама является суммой десятичных значений подходящих чисел.
Положим \(L=20\) и \(M=10^9\). Каждая цифра даёт вклад не больше \(9^2=81\), поэтому максимум для \(f(n)\) равен \(20\cdot 81=1620\). Значит, пространство состояний по сумме квадратов цифр содержит всего 1621 вариант, и этого достаточно для полного digit-DP.
Для каждого \(\ell\in\{0,1,\dots,20\}\) и каждого \(t\in\{0,1,\dots,1620\}\) обозначим через \(A_{\ell,t}\) множество всех чисел \(x\) таких, что \(0 \le x < 10^\ell\), а \(\ell\)-значная запись \(x\) с добавленными слева нулями при необходимости имеет сумму квадратов цифр, равную \(t\). Именно так и нужно понимать исходную задачу: каждое число меньше \(10^{20}\) единственным образом представляется 20-значной строкой, а строка из одних нулей всё равно вносит в итоговую сумму только 0.
В реализациях для каждого состояния хранятся две величины:
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
\(C_\ell(t)\) считает, сколько \(\ell\)-значных строк приводит к сумме \(t\). \(V_\ell(t)\) суммирует уже сами числовые значения этих строк. Начальное условие имеет вид
$$C_0(0)=1,\qquad V_0(0)=0,$$
а все прочие состояния при \(\ell=0\) равны 0. Поскольку в задаче нужны только последние девять цифр, обе таблицы можно всё время хранить по модулю \(M\). Это корректно, потому что дальше они используются только в линейных комбинациях через сложение и умножение.
Число длины \(\ell\) строится из числа длины \(\ell-1\) добавлением новой старшей цифры \(d\in\{0,\dots,9\}\). Если у старой части сумма квадратов цифр была \(t-d^2\), то у новой она становится равной \(t\). Поэтому
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$$
где слагаемые с отрицательным аргументом просто отсутствуют.
Теперь рассмотрим сумму значений. Если прежнее число равно \(x\), то после добавления цифры \(d\) слева получается
$$x+d\cdot 10^{\ell-1}.$$
Суммируя это по всем допустимым более коротким состояниям, получаем
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$$
Второе слагаемое здесь принципиально важно: вклад новой старшей цифры должен быть добавлен по одному разу для каждого короткого числа, которое учитывается в \(C_{\ell-1}(t-d^2)\).
Единственные 2-значные строки с суммой квадратов цифр 9 - это \(03\) и \(30\). Следовательно, должно получиться
$$C_2(9)=2,\qquad V_2(9)=3+30=33.$$
Рекурсия даёт ровно это. Для количества имеем
$$C_2(9)=C_1(9)+C_1(0)=1+1=2,$$
поскольку есть только два варианта: дописать слева 0 к строке \(3\) или дописать слева 3 к строке \(0\). Для суммы значений получаем
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$$
Этот маленький пример наглядно показывает, почему одной таблицы подсчётов недостаточно: задача спрашивает сумму подходящих чисел, а не только их количество.
Квадратное состояние может быть только \(r^2\) при \(1 \le r \le 40\), потому что \(40^2=1600 \le 1620\), а \(41^2=1681\) уже превышает максимум. Поэтому искомый результат равен
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$$
Состояние \(r=0\) соответствует только числу 0 и потому не влияет на итоговую сумму.
Реализации на C++, Python и Java буквально следуют этой схеме. Сначала они предвычисляют \(10^0,10^1,\dots,10^{19}\) по модулю \(10^9\), поскольку в каждом переходе нужен десятичный вес новой добавленной цифры. Затем выделяются две таблицы, индексируемые длиной и суммой квадратов цифр, записывается базовое состояние пустой строки, и длины последовательно наращиваются от 1 до 20.
Для каждой длины, каждой цифры \(0,\dots,9\) и каждого достижимого значения суммы квадратов код обновляет обе таблицы одновременно. Таблица количеств получает вклад от более короткого состояния, а таблица сумм значений добавляет как старую сумму суффиксов, так и новый вклад по разряду. После завершения слоя длины 20 код просматривает только квадратные цели \(1,4,9,\dots,1600\) и складывает соответствующие сохранённые суммы значений. В C++-версии дополнительно есть короткие проверки полным перебором для малых длин, подтверждающие правильность DP перед основным запуском.
Циклы проходят по \(L=20\) длинам, 10 возможным цифрам и не более чем \(81L+1=1621\) состояниям суммы квадратов. Отсюда время работы равно
$$O(L\cdot 10\cdot 81L)=O(L^2).$$
Поскольку реализации хранят полные двумерные таблицы для всех длин, потребление памяти составляет
$$O(L\cdot 81L).$$
Даже без сжатия по слоям это ничтожно мало по сравнению с прямым перебором \(10^{20}\) чисел.
لكل عدد صحيح \(0 \le n < 10^{20}\) نكتب تمثيله العشري بطول 20 رقمًا على الصورة \(d_{19}d_{18}\dots d_0\) مع السماح بالأصفار البادئة. نعرّف
$$f(n)=\sum_{i=0}^{19} d_i^2.$$
المطلوب هو جمع جميع الأعداد \(n\) التي تكون فيها \(f(n)\) مربعًا كاملًا، ثم الاحتفاظ فقط بآخر تسعة أرقام من هذا المجموع. من المستحيل فحص \(10^{20}\) احتمالًا مباشرة. الفكرة الحاسمة هي أن شرط القبول يعتمد فقط على مجموع مربعات الأرقام، بينما الكمية المطلوبة في النهاية هي مجموع القيم العشرية للأعداد المقبولة نفسها.
لنكتب \(L=20\) و\(M=10^9\). بما أن أقصى مساهمة لأي رقم هي \(9^2=81\)، فإن أكبر قيمة ممكنة لـ \(f(n)\) هي \(20\cdot 81=1620\). إذن فضاء الحالات الخاص بمجموع مربعات الأرقام لا يحتوي إلا على 1621 حالة ممكنة، وهذا ما يجعل البرمجة الديناميكية مناسبة جدًا هنا.
لكل \(\ell\in\{0,1,\dots,20\}\) ولكل \(t\in\{0,1,\dots,1620\}\)، نرمز بـ \(A_{\ell,t}\) إلى مجموعة الأعداد \(x\) التي تحقق \(0 \le x < 10^\ell\) ويكون مجموع مربعات أرقام تمثيلها العشري بطول \(\ell\)، بعد إضافة أصفار بادئة عند الحاجة، مساويًا لـ \(t\). هذا التمثيل يطابق نص المسألة تمامًا: كل عدد أصغر من \(10^{20}\) يظهر مرة واحدة على هيئة سلسلة من 20 رقمًا، والحالة التي كلها أصفار لا تضيف شيئًا لأن قيمتها العددية تساوي 0.
التنفيذ لا يحتفظ بعدد الحالات فقط، بل يحتفظ بكمّيتين لكل حالة:
$$C_\ell(t)=|A_{\ell,t}|,$$
$$V_\ell(t)=\sum_{x\in A_{\ell,t}} x \pmod{M}.$$
القيمة \(C_\ell(t)\) تعدّ كم سلسلة بطول \(\ell\) تصل إلى مجموع المربعات \(t\). أما \(V_\ell(t)\) فهي مجموع القيم العددية لهذه السلاسل نفسها، وهي بالضبط الكمية التي نحتاجها عند النهاية. حالة البداية هي
$$C_0(0)=1,\qquad V_0(0)=0,$$
وجميع الحالات الأخرى عند الطول 0 تساوي 0. وبما أن المسألة تطلب فقط آخر تسعة أرقام، فمن الآمن إجراء كل الحسابات داخل الجدولين بترديد \(M\). سبب ذلك أن الاستخدامات اللاحقة لهذين الجدولين تعتمد فقط على الجمع والضرب، أي على عمليات خطية تبقى صحيحة تحت الترديد.
نبني عددًا بطول \(\ell\) انطلاقًا من عدد بطول \(\ell-1\) ثم نضيف في يساره رقمًا جديدًا \(d\in\{0,\dots,9\}\). إذا كان مجموع مربعات الجزء القديم يساوي \(t-d^2\)، فإن العدد الجديد ينتقل إلى الحالة \(t\). لذلك نحصل على
$$C_\ell(t)=\sum_{d=0}^{9} C_{\ell-1}(t-d^2),$$
مع تجاهل الحدود التي يظهر فيها وسيط سالب.
أما بالنسبة إلى مجموع القيم، فإذا كان العدد القديم هو \(x\)، فإن العدد الجديد بعد إضافة الرقم \(d\) في اليسار يصبح
$$x+d\cdot 10^{\ell-1}.$$
وبجمع هذا على جميع الحالات السابقة نحصل على العلاقة الثانية:
$$V_\ell(t)=\sum_{d=0}^{9}\left(V_{\ell-1}(t-d^2)+d\cdot 10^{\ell-1}\cdot C_{\ell-1}(t-d^2)\right)\pmod{M}.$$
الحد الثاني هو جوهر الحل كله: عندما نثبت الرقم الجديد \(d\)، فإن إسهامه في القيمة العشرية يجب أن يضاف مرة واحدة لكل عدد أقصر يعدّه \(C_{\ell-1}(t-d^2)\).
السلاسل الوحيدة بطول 2 التي يكون مجموع مربعات أرقامها 9 هي \(03\) و\(30\). إذن ينبغي أن يكون
$$C_2(9)=2,\qquad V_2(9)=3+30=33.$$
العلاقة العودية تعطي النتيجة نفسها تمامًا. بالنسبة إلى العد نحصل على
$$C_2(9)=C_1(9)+C_1(0)=1+1=2,$$
لأن الطريقتين الوحيدتين هما وضع 0 إلى يسار العدد \(3\)، أو وضع 3 إلى يسار العدد \(0\). أما مجموع القيم فيصبح
$$V_2(9)=V_1(9)+0\cdot 10\cdot C_1(9)+V_1(0)+3\cdot 10\cdot C_1(0)=3+0+0+30=33.$$
هذا المثال الصغير يوضح بجلاء لماذا لا يكفي جدول العد وحده: المسألة لا تسأل عن عدد الأعداد المقبولة فقط، بل عن مجموعها أيضًا.
الحالات التي تمثل مربعًا كاملًا لا يمكن أن تكون إلا \(r^2\) حيث \(1 \le r \le 40\)، لأن \(40^2=1600 \le 1620\) بينما \(41^2=1681\) تتجاوز الحد الأقصى. لذلك تكون النتيجة المطلوبة
$$\sum_{r=1}^{40} V_{20}(r^2)\pmod{10^9}.$$
أما حالة \(r=0\) فلا تمثل إلا العدد 0، ولذلك لا تغيّر المجموع النهائي.
تنفيذات C++ وPython وJava تتبع هذا الاشتقاق مباشرة. تبدأ أولًا بحساب القيم \(10^0,10^1,\dots,10^{19}\) بترديد \(10^9\)، لأن كل انتقال يحتاج إلى وزن الخانة العشرية للرقم الجديد. بعد ذلك تُنشأ جدولان مفهرسان بالطول ومجموع مربعات الأرقام، وتُسجَّل حالة البداية الخاصة بالسلسلة الفارغة، ثم تُبنى الأطوال من 1 حتى 20 بالتتابع.
عند كل طول، ومع كل رقم \(0,\dots,9\)، ولكل حالة قابلة للوصول، يحدّث التنفيذ جدول العد وجدول مجموع القيم معًا. جدول العد يستقبل عدد الطرق القادمة من الحالة الأقصر، وجدول القيم يضيف مجموع القيم السابق بالإضافة إلى مساهمة الرقم الجديد في موضعه العشري. وبعد اكتمال طبقة الطول 20، لا يبقى إلا المرور على الأهداف المربعة \(1,4,9,\dots,1600\) وجمع القيم المخزنة لها. نسخة C++ تتضمن كذلك اختبارات صغيرة بالمقارنة مع العد الشامل لأطوال قصيرة، للتأكد من صحة البرمجة الديناميكية قبل تشغيل الحالة الكاملة.
الحلقات تمر على \(L=20\) طبقات طول، وعلى 10 أرقام ممكنة، وعلى ما لا يزيد عن \(81L+1=1621\) حالة لمجموع مربعات الأرقام. لذا فإن التعقيد الزمني يساوي
$$O(L\cdot 10\cdot 81L)=O(L^2).$$
ولأن التنفيذات تحتفظ بالجداول الثنائية الكاملة لجميع الأطوال، فإن استهلاك الذاكرة يساوي
$$O(L\cdot 81L).$$
وحتى من دون ضغط الذاكرة إلى صفين فقط، يبقى هذا صغيرًا جدًا مقارنة بمحاولة تعداد \(10^{20}\) عددًا واحدًا واحدًا.