A decimal number is valid here when one of its digits equals the sum of all the remaining digits. If that distinguished digit is \(s\), then the total digit sum must be \(2s\). The C++, Python, and Java implementations therefore loop over \(s\in\{0,\dots,9\}\), sum every number of length \(1\) through \(n\) whose digit sum is \(2s\) and that contains at least one digit \(s\), and return the grand total modulo \(10^{16}\).
This reformulation is the key simplification. Because \(s\le 9\), every valid number has total digit sum at most \(18\), so the dynamic program only needs a tiny sum dimension instead of a huge search over all \(n\)-digit numbers.
The solution does not enumerate candidate numbers directly. Instead, for each possible witness digit \(s\), it keeps aggregated information about all prefixes with a given length, a given digit sum, and a flag telling us whether the digit \(s\) has appeared yet.
Let the digits of an \(\ell\)-digit number be \(d_1,\dots,d_\ell\). Suppose one digit equals the sum of all the others, and let that digit be \(s\). Then
$$d_1+\cdots+d_\ell=s+s=2s.$$
Conversely, if the total digit sum is \(2s\) and at least one digit is exactly \(s\), then removing one such digit leaves the remaining digits summing to \(s\), so the original condition is satisfied.
Therefore, for a fixed \(s\), the problem becomes: sum all \(\ell\)-digit numbers whose digit sum is \(2s\) and that contain at least one \(s\). There is no double counting, because the witness digit is determined uniquely by half of the total digit sum.
Fix \(s\in\{0,\dots,9\}\) and write \(T=2s\). For each length \(\ell\), digit sum \(u\), and flag \(h\in\{0,1\}\), let \(\mathcal{N}_{\ell,s}(u,h)\) be the set of \(\ell\)-digit decimal numbers with no leading zero, digit sum \(u\), and where \(h=1\) means that digit \(s\) has already appeared.
Define
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$$
The first quantity is a count. The second is the sum of the actual numeric values in that state. For the fixed witness digit \(s\), the valid numbers of length \(\ell\) contribute exactly
$$B_{\ell,s}(T,1).$$
Since all digits are nonnegative, any state with \(u>T\) can never come back down to \(T\), so such states can be ignored immediately.
The first digit cannot be zero, so only \(d\in\{1,\dots,9\}\) are allowed initially. A one-digit state exists only when \(d\le T\), and then
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
All other states start at zero. In particular, when \(s=0\) we have \(T=0\), so there is no legal one-digit initialization. That entire case contributes nothing, which is consistent with the fact that a positive decimal number cannot have digit sum \(0\).
Take any state at length \(\ell\) with digit sum \(u\), witness flag \(h\), count \(A_{\ell,s}(u,h)\), and value sum \(B_{\ell,s}(u,h)\). Appending a new digit \(d\in\{0,\dots,9\}\) creates a number of length \(\ell+1\) with new digit sum
$$u'=u+d,$$
and the new witness flag becomes
$$h'=\begin{cases} 1,& \text{if } h=1 \text{ or } d=s,\\ 0,& \text{otherwise.} \end{cases}$$
The count update is therefore
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$$
For the value sum, every old number \(x\) turns into \(10x+d\). Summing over the whole state gives
$$\sum(10x+d)=10\sum x+d\cdot \#\{\text{numbers in the state}\}.$$
Hence the second recurrence is
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$$
All arithmetic is reduced modulo \(10^{16}\), exactly as in the implementations.
For the fixed digit \(s\), the contribution of lengths \(1\) through \(n\) is
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$$
The final answer is then
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$$
The important structural fact is that \(2s\le 18\), so the DP only needs sums \(0,1,\dots,18\). That is why the whole computation stays tiny even when \(n\) is as large as \(2020\).
Now \(T=4\). For length \(1\), the possible starting digits are \(1,2,3,4\). They produce the states
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
with matching value sums \(1,2,3,4\).
At length \(2\), the only valid number with total digit sum \(4\) and containing a \(2\) is \(22\), so
$$B_{2,2}(4,1)=22.$$
At length \(3\), the valid numbers are
$$112,\ 121,\ 202,\ 211,\ 220,$$
whose sum is
$$112+121+202+211+220=866.$$
Therefore the total contribution of the witness digit \(2\) up to length \(3\) is
$$22+866=888.$$
This is exactly the kind of subtotal the DP computes automatically: it never lists long numbers explicitly, but the recurrence reproduces the same result through aggregated counts and aggregated value sums.
The C++, Python, and Java implementations iterate through the ten possible witness digits. For each one, they maintain two \(19\times 2\) tables for the current length: one table stores how many prefixes belong to each state, and the other stores the sum of the numeric values of those prefixes.
The first layer is seeded with the legal one-digit numbers. Each later layer is built by appending one digit \(0\) through \(9\), updating both tables with the recurrences above. After every length, the implementation adds the state with digit sum \(2s\) and witness flag \(1\) to the global total, then rolls the tables forward to the next length.
No backtracking or large-number enumeration is needed. The only bookkeeping trick is to reduce every update modulo \(10^{16}\), so the running totals remain bounded throughout the computation.
There are only \(10\) witness digits, at most \(19\) possible digit sums, \(2\) flag values, and \(10\) appended digits per transition. For each length, the work is therefore bounded by a small constant, so the overall running time is
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$$
Only the current layer and the next layer are stored, so the extra memory usage is
$$O(19\cdot 2)=O(1)$$
with respect to \(n\).
Eine Dezimalzahl ist hier genau dann gültig, wenn eine ihrer Ziffern gleich der Summe aller übrigen Ziffern ist. Bezeichnet man diese ausgezeichnete Ziffer mit \(s\), dann ist die gesamte Ziffernsumme zwangsläufig \(2s\). Deshalb iterieren die C++-, Python- und Java-Implementierungen über \(s\in\{0,\dots,9\}\), summieren alle Zahlen der Längen \(1\) bis \(n\), deren Ziffernsumme \(2s\) ist und die mindestens eine Ziffer \(s\) enthalten, und geben das Gesamtergebnis modulo \(10^{16}\) aus.
Gerade diese Umformulierung macht das Problem beherrschbar. Da \(s\le 9\) gilt, hat jede gültige Zahl Ziffernsumme höchstens \(18\). Die dynamische Programmierung braucht also nur eine sehr kleine Summendimension.
Die Lösung erzeugt die Kandidaten nicht einzeln. Stattdessen speichert sie für jedes mögliche Zeugenzeichen \(s\) nur zusammengefasste Informationen über alle Präfixe mit fester Länge, fester Ziffernsumme und einem Flag, das angibt, ob die Ziffer \(s\) bereits vorkam.
Seien \(d_1,\dots,d_\ell\) die Ziffern einer \(\ell\)-stelligen Zahl. Wenn eine dieser Ziffern gleich der Summe aller anderen ist und diese Ziffer den Wert \(s\) hat, dann gilt
$$d_1+\cdots+d_\ell=s+s=2s.$$
Umgekehrt gilt: Hat eine Zahl Ziffernsumme \(2s\) und kommt die Ziffer \(s\) mindestens einmal vor, dann bleibt nach dem Entfernen einer solchen Ziffer eine Restsumme von \(s\). Damit ist die ursprüngliche Bedingung erfüllt.
Für festes \(s\) müssen wir also genau die Zahlen mit Ziffernsumme \(2s\) und mindestens einer Ziffer \(s\) aufsummieren. Doppelte Zählung gibt es nicht, weil die Zeugen-Ziffer durch die halbe Gesamtsumme eindeutig bestimmt ist.
Fixiere \(s\in\{0,\dots,9\}\) und setze \(T=2s\). Für jede Länge \(\ell\), jede Ziffernsumme \(u\) und jedes Flag \(h\in\{0,1\}\) sei \(\mathcal{N}_{\ell,s}(u,h)\) die Menge aller \(\ell\)-stelligen Dezimalzahlen ohne führende Null mit Ziffernsumme \(u\), wobei \(h=1\) bedeutet, dass die Ziffer \(s\) bereits aufgetreten ist.
Definiere
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$$
Die erste Größe zählt die Zustände, die zweite summiert ihre tatsächlichen Zahlenwerte. Für das feste \(s\) ist der gesuchte Beitrag der Länge \(\ell\) dann
$$B_{\ell,s}(T,1).$$
Da alle Ziffern nichtnegativ sind, kann ein Zustand mit \(u>T\) nie wieder auf die Zielsumme \(T\) zurückfallen und wird deshalb sofort verworfen.
Die erste Ziffer darf nicht \(0\) sein, also kommen anfänglich nur \(d\in\{1,\dots,9\}\) in Frage. Ein einstelliger Zustand existiert nur für \(d\le T\), und dann gilt
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
Alle anderen Zustände starten mit \(0\). Insbesondere hat man für \(s=0\) auch \(T=0\), also gibt es keine zulässige Initialisierung. Dieser gesamte Fall trägt daher nichts bei, was genau zur Tatsache passt, dass eine positive Dezimalzahl keine Ziffernsumme \(0\) haben kann.
Betrachte einen Zustand der Länge \(\ell\) mit Ziffernsumme \(u\), Flag \(h\), Anzahl \(A_{\ell,s}(u,h)\) und Wertsumme \(B_{\ell,s}(u,h)\). Hängt man eine neue Ziffer \(d\in\{0,\dots,9\}\) an, so erhält man eine Zahl der Länge \(\ell+1\) mit neuer Ziffernsumme
$$u'=u+d,$$
und neuem Flag
$$h'=\begin{cases} 1,& \text{falls } h=1 \text{ oder } d=s,\\ 0,& \text{sonst.} \end{cases}$$
Für die Anzahl folgt also
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$$
Für die Wertsumme wird aus jeder alten Zahl \(x\) die neue Zahl \(10x+d\). Über den ganzen Zustand summiert ergibt das
$$\sum(10x+d)=10\sum x+d\cdot \#\{\text{Zahlen im Zustand}\}.$$
Daher gilt
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$$
Alle Rechnungen werden modulo \(10^{16}\) ausgeführt.
Für das feste \(s\) ist der Gesamtbeitrag der Längen \(1\) bis \(n\)
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$$
Die Endantwort lautet damit
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$$
Der entscheidende Strukturpunkt ist \(2s\le 18\). Deshalb braucht das Verfahren nur die Summen \(0,1,\dots,18\), also eine feste kleine Tabelle statt einer großen kombinatorischen Suche.
Hier ist \(T=4\). Für Länge \(1\) sind die möglichen Startziffern \(1,2,3,4\). Sie erzeugen die Zustände
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
mit den zugehörigen Wertsummen \(1,2,3,4\).
Bei Länge \(2\) gibt es genau eine gültige Zahl mit Ziffernsumme \(4\), die eine \(2\) enthält, nämlich \(22\). Also
$$B_{2,2}(4,1)=22.$$
Bei Länge \(3\) sind die gültigen Zahlen
$$112,\ 121,\ 202,\ 211,\ 220,$$
und ihre Summe ist
$$112+121+202+211+220=866.$$
Damit ist der Gesamtbeitrag der Zeugen-Ziffer \(2\) bis Länge \(3\)
$$22+866=888.$$
Genau solche Zwischensummen liefert die dynamische Programmierung automatisch: Sie listet die längeren Zahlen nicht explizit auf, sondern rekonstruiert denselben Wert über aggregierte Anzahlen und aggregierte Wertsummen.
Die C++-, Python- und Java-Implementierungen laufen über die zehn möglichen Zeugen-Ziffern. Für jede davon halten sie zwei Tabellen der Größe \(19\times 2\) für die aktuelle Länge: eine Tabelle für die Anzahl der Präfixe in jedem Zustand und eine zweite für die Summe ihrer numerischen Werte.
Die erste Schicht wird mit allen zulässigen einstelligen Zahlen initialisiert. Jede spätere Schicht entsteht durch Anhängen einer Ziffer \(0\) bis \(9\), wobei beide Tabellen mit den oben hergeleiteten Rekursionen fortgeschrieben werden. Nach jeder Länge addiert die Implementierung den Zustand mit Ziffernsumme \(2s\) und Flag \(1\) zur globalen Antwort und rollt dann zur nächsten Länge weiter.
Weder Backtracking noch die explizite Erzeugung riesiger Zahlenmengen ist nötig. Die einzige Schutzmaßnahme ist die konsequente Reduktion modulo \(10^{16}\), damit alle laufenden Summen beschränkt bleiben.
Es gibt nur \(10\) mögliche Zeugen-Ziffern, höchstens \(19\) Ziffernsummen, \(2\) Flag-Werte und \(10\) mögliche angehängte Ziffern. Die Arbeit pro Länge ist daher durch eine kleine Konstante beschränkt, und die gesamte Laufzeit ist
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$$
Gespeichert werden nur die aktuelle und die nächste Schicht, also beträgt der zusätzliche Speicher
$$O(19\cdot 2)=O(1)$$
in Bezug auf \(n\).
Bu problemde bir onluk sayı, rakamlarından biri diğer bütün rakamların toplamına eşitse geçerlidir. Bu özel rakamın değeri \(s\) ise toplam rakamlar toplamı zorunlu olarak \(2s\) olur. Bu yüzden C++, Python ve Java uygulamaları \(s\in\{0,\dots,9\}\) için ayrı ayrı dolaşır; uzunluğu \(1\) ile \(n\) arasında olan, rakamlar toplamı \(2s\) olan ve en az bir tane \(s\) içeren tüm sayıları toplar; sonra genel sonucu \(10^{16}\) modunda verir.
Temel sadeleştirme budur. Çünkü \(s\le 9\) olduğundan her geçerli sayının rakamlar toplamı en fazla \(18\) olabilir. Böylece dinamik programlama, devasa bir sayı uzayını taramak yerine sadece çok küçük bir toplam boyutu üzerinde çalışır.
Çözüm aday sayıları tek tek üretmez. Bunun yerine her olası tanık rakam \(s\) için, belli bir uzunlukta, belli bir rakam toplamında ve “\(s\) şimdiye kadar görüldü mü?” bayrağında bulunan tüm öneklerin toplulaştırılmış bilgisini tutar.
\(\ell\) basamaklı bir sayının rakamları \(d_1,\dots,d_\ell\) olsun. Bu rakamlardan biri diğerlerinin toplamına eşitse ve bu rakam \(s\) ise
$$d_1+\cdots+d_\ell=s+s=2s.$$
Ters yönde de aynı mantık geçerlidir: Toplam rakamlar toplamı \(2s\) ise ve rakamlardan en az biri tam olarak \(s\) ise, bu rakamı ayırdığımızda geriye toplamı \(s\) olan diğer rakamlar kalır. Yani özgün tanım sağlanır.
Dolayısıyla sabit bir \(s\) için problem şu hale gelir: rakam toplamı \(2s\) olan ve en az bir \(s\) içeren sayıları topla. Çifte sayım yoktur; çünkü tanık rakam, toplam rakamlar toplamının yarısı olarak tek biçimde belirlenir.
\(s\in\{0,\dots,9\}\) sabit olsun ve \(T=2s\) yazalım. Her uzunluk \(\ell\), her rakam toplamı \(u\) ve her \(h\in\{0,1\}\) bayrağı için \(\mathcal{N}_{\ell,s}(u,h)\), başında sıfır olmayan, rakamlar toplamı \(u\) olan ve \(h=1\) ise içinde en az bir tane \(s\) bulunan \(\ell\) basamaklı onluk sayıların kümesi olsun.
Şimdi
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x$$
tanımlarını yapalım. İlk ifade bu durumdaki sayı adedini, ikinci ifade ise o sayıların gerçek değer toplamını verir. Sabit \(s\) için uzunluğu \(\ell\) olan geçerli sayılar tam olarak
$$B_{\ell,s}(T,1)$$
katkısını yapar. Rakamlar negatif olmadığı için \(u>T\) olan bir durum bir daha hedef toplam \(T\)'ye dönemez; dolayısıyla bu durumlar doğrudan elenir.
İlk rakam sıfır olamayacağından başlangıçta sadece \(d\in\{1,\dots,9\}\) mümkündür. Tek basamaklı bir durum ancak \(d\le T\) ise vardır ve bu durumda
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
Diğer bütün durumlar sıfırdan başlar. Özellikle \(s=0\) için \(T=0\) olur; fakat pozitif bir onluk sayıda ilk rakam sıfır olamayacağı için yasal bir başlangıç oluşmaz. Bu yüzden bu durumda katkı doğal olarak sıfırdır.
Uzunluğu \(\ell\) olan bir durumda rakam toplamı \(u\), bayrak değeri \(h\), sayı adedi \(A_{\ell,s}(u,h)\) ve değer toplamı \(B_{\ell,s}(u,h)\) olsun. Sona \(d\in\{0,\dots,9\}\) rakamı eklenirse yeni uzunluk \(\ell+1\) olur ve yeni rakam toplamı
$$u'=u+d$$
şeklindedir. Yeni bayrak ise
$$h'=\begin{cases} 1,& \text{eğer } h=1 \text{ veya } d=s,\\ 0,& \text{aksi halde.} \end{cases}$$
Bu nedenle adet güncellemesi
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h)$$
olur. Değer toplamı içinse her eski sayı \(x\), \(10x+d\)'ye dönüşür. Bir durumun tamamı üzerinde toplarsak
$$\sum(10x+d)=10\sum x+d\cdot \#\{\text{durumdaki sayılar}\}$$
elde edilir. Dolayısıyla ikinci güncelleme
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h)$$
şeklindedir. Tüm işlemler \(10^{16}\) modunda yapılır.
Sabit bir \(s\) için, \(1\) ile \(n\) arasındaki bütün uzunlukların toplam katkısı
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1)$$
olur. Nihai sonuç da
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}$$
şeklindedir. Kritik gözlem \(2s\le 18\) olmasıdır. Böylece DP yalnızca \(0,1,\dots,18\) toplamlarını taşır; büyük bir kombinatorik yapı kurmaya gerek kalmaz.
Bu durumda \(T=4\) olur. Uzunluk \(1\) için mümkün başlangıç rakamları \(1,2,3,4\)'tür ve şu durumları üretir:
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
karşılık gelen değer toplamları da sırasıyla \(1,2,3,4\)'tür.
Uzunluk \(2\)'de toplam rakamı \(4\) olan ve bir \(2\) içeren tek geçerli sayı \(22\)'dir. Dolayısıyla
$$B_{2,2}(4,1)=22.$$
Uzunluk \(3\)'te geçerli sayılar
$$112,\ 121,\ 202,\ 211,\ 220$$
olur ve bunların toplamı
$$112+121+202+211+220=866$$
eder. Böylece tanık rakam \(2\)'nin uzunluk \(3\)'e kadar toplam katkısı
$$22+866=888$$
olur. DP de tam olarak bu alt toplamı, sayıları tek tek listelemeden, toplulaştırılmış adet ve değer toplamları üzerinden üretir.
C++, Python ve Java uygulamaları on olası tanık rakam üzerinde sırayla dolaşır. Her \(s\) için mevcut uzunluğu temsil eden \(19\times 2\) boyutlu iki tablo tutulur: biri her durumdaki önek sayısını, diğeri ise bu öneklerin sayısal değer toplamını saklar.
İlk katman yasal tek basamaklı sayılarla başlatılır. Daha sonraki her katman, sona \(0\) ile \(9\) arasında bir rakam eklenerek oluşturulur ve iki tablo da yukarıdaki bağıntılara göre güncellenir. Her uzunluğun sonunda, rakam toplamı \(2s\) ve bayrağı \(1\) olan durum genel cevaba eklenir; ardından tablolar bir sonraki uzunluk için devredilir.
Geri izleme, açık listeleme veya dev sayılar üretme yoktur. Tek teknik önlem, ara toplamların sınırlı kalması için her güncellemenin \(10^{16}\) moduna göre indirgenmesidir.
Yalnızca \(10\) farklı tanık rakam, en fazla \(19\) olası rakam toplamı, \(2\) bayrak durumu ve geçiş başına \(10\) eklenecek rakam vardır. Bu yüzden her uzunluk için iş miktarı sabit bir üst sınırla kontrol edilir ve toplam çalışma süresi
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n)$$
olur. Sadece mevcut katman ile bir sonraki katman saklandığı için ek bellek kullanımı
$$O(19\cdot 2)=O(1)$$
seviyesindedir.
En este problema, un número decimal es válido cuando una de sus cifras es igual a la suma de todas las demás. Si esa cifra distinguida vale \(s\), entonces la suma total de cifras debe ser \(2s\). Por eso las implementaciones en C++, Python y Java recorren \(s\in\{0,\dots,9\}\), suman todos los números de longitud entre \(1\) y \(n\) cuya suma de cifras es \(2s\) y que contienen al menos una cifra \(s\), y finalmente devuelven el total módulo \(10^{16}\).
Esa reformulación es la razón de que el problema sea manejable. Como \(s\le 9\), toda solución válida tiene suma de cifras a lo sumo \(18\), de modo que la programación dinámica solo necesita una dimensión de suma muy pequeña.
La idea no es enumerar directamente todos los candidatos. Para cada posible cifra testigo \(s\), el método guarda información agregada sobre todos los prefijos con una longitud fija, una suma de cifras fija y una marca que indica si la cifra \(s\) ya apareció.
Sean \(d_1,\dots,d_\ell\) las cifras de un número de \(\ell\) dígitos. Si una de esas cifras es igual a la suma de todas las demás y esa cifra vale \(s\), entonces
$$d_1+\cdots+d_\ell=s+s=2s.$$
La implicación inversa también vale: si la suma total de cifras es \(2s\) y al menos una cifra es exactamente \(s\), entonces al separar una de esas cifras queda un resto con suma \(s\), y por tanto se cumple la definición original.
Así, para un \(s\) fijo, solo hay que sumar los números cuya suma de cifras es \(2s\) y que contienen \(s\). No hay doble conteo porque la cifra testigo queda determinada de forma única por la mitad de la suma total de cifras.
Fijemos \(s\in\{0,\dots,9\}\) y escribamos \(T=2s\). Para cada longitud \(\ell\), suma de cifras \(u\) y bandera \(h\in\{0,1\}\), sea \(\mathcal{N}_{\ell,s}(u,h)\) el conjunto de números decimales de \(\ell\) dígitos, sin cero inicial, con suma de cifras \(u\), donde \(h=1\) significa que la cifra \(s\) ya apareció.
Definimos
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$$
La primera cantidad cuenta cuántos números hay en ese estado. La segunda suma sus valores numéricos reales. Para el \(s\) fijado, la contribución válida de longitud \(\ell\) es exactamente
$$B_{\ell,s}(T,1).$$
Como todas las cifras son no negativas, cualquier estado con \(u>T\) ya no puede volver a la suma objetivo \(T\), así que puede descartarse enseguida.
La primera cifra no puede ser cero, así que solo son posibles \(d\in\{1,\dots,9\}\). Un estado de un solo dígito existe únicamente cuando \(d\le T\), y en ese caso
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
Todos los demás estados arrancan en cero. En particular, si \(s=0\), entonces \(T=0\) y no existe ninguna inicialización legal; ese caso aporta cero, lo cual coincide con que un número decimal positivo no puede tener suma de cifras igual a \(0\).
Consideremos un estado de longitud \(\ell\) con suma de cifras \(u\), bandera \(h\), cantidad \(A_{\ell,s}(u,h)\) y suma de valores \(B_{\ell,s}(u,h)\). Al añadir una nueva cifra \(d\in\{0,\dots,9\}\), obtenemos una cifra total nueva
$$u'=u+d,$$
y la nueva bandera es
$$h'=\begin{cases} 1,& \text{si } h=1 \text{ o } d=s,\\ 0,& \text{en otro caso.} \end{cases}$$
La recurrencia para las cantidades es
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$$
Para la suma de valores, cada número anterior \(x\) pasa a ser \(10x+d\). Al sumar en bloque se obtiene
$$\sum(10x+d)=10\sum x+d\cdot \#\{\text{números del estado}\}.$$
Por tanto, la segunda recurrencia es
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$$
Todas las operaciones se realizan módulo \(10^{16}\).
Para el \(s\) fijo, la contribución total de las longitudes \(1\) hasta \(n\) es
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$$
La respuesta final es
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$$
El punto estructural decisivo es que \(2s\le 18\). Por eso la programación dinámica solo necesita las sumas \(0,1,\dots,18\), y toda la solución cabe en tablas pequeñas de tamaño fijo.
Aquí \(T=4\). Para longitud \(1\), las cifras iniciales posibles son \(1,2,3,4\). Ellas producen los estados
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
con sumas de valores correspondientes \(1,2,3,4\).
En longitud \(2\), el único número válido con suma de cifras \(4\) que contiene un \(2\) es \(22\), así que
$$B_{2,2}(4,1)=22.$$
En longitud \(3\), los números válidos son
$$112,\ 121,\ 202,\ 211,\ 220,$$
cuya suma es
$$112+121+202+211+220=866.$$
Por tanto, la contribución total del testigo \(2\) hasta longitud \(3\) es
$$22+866=888.$$
Este ejemplo muestra exactamente lo que hace la recurrencia: en lugar de listar todos los números largos, la DP reconstruye la misma suma usando recuentos agregados y sumas agregadas de valores.
Las implementaciones en C++, Python y Java recorren las diez posibles cifras testigo. Para cada una mantienen dos tablas de tamaño \(19\times 2\) para la longitud actual: una tabla guarda cuántos prefijos hay en cada estado y la otra guarda la suma de los valores numéricos de esos prefijos.
La primera capa se inicializa con los números válidos de un solo dígito. Cada capa posterior se construye añadiendo una cifra entre \(0\) y \(9\), actualizando ambas tablas con las recurrencias anteriores. Después de cada longitud, la implementación añade al total global el estado con suma de cifras \(2s\) y bandera \(1\), y luego avanza a la siguiente longitud.
No hace falta ni retroceso ni enumeración explícita de cantidades gigantescas de números. La única precaución aritmética es reducir cada actualización módulo \(10^{16}\), para mantener acotadas las sumas acumuladas.
Solo hay \(10\) cifras testigo, como máximo \(19\) sumas de cifras posibles, \(2\) valores de bandera y \(10\) cifras candidatas por transición. Por tanto, el trabajo por longitud está acotado por una constante pequeña y el tiempo total es
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$$
Como solo se almacenan la capa actual y la siguiente, la memoria extra es
$$O(19\cdot 2)=O(1)$$
respecto de \(n\).
这个问题中的有效十进制数满足这样一个条件：它的某一位数字，恰好等于其余所有数字之和。若这位“见证数字”为 \(s\)，那么整个数字的数位和必然是 \(2s\)。因此，C++、Python 和 Java 实现都会对 \(s\in\{0,\dots,9\}\) 逐个处理，把所有长度从 \(1\) 到 \(n\)、数位和等于 \(2s\)、并且至少出现一次数字 \(s\) 的数全部加起来，最后对 \(10^{16}\) 取模。
这一等价改写是整道题可做的关键。因为 \(s\le 9\)，所以任何有效数字的总数位和都不会超过 \(18\)。这意味着动态规划根本不需要处理庞大的 \(n\) 位数空间，只需要维护一个非常小的“当前数位和”维度。
核心思路不是显式枚举所有候选数，而是对每个可能的见证数字 \(s\)，按“长度”“当前数位和”“是否已经出现过数字 \(s\)”这三个维度，汇总同一类前缀的数量与数值总和。
设一个 \(\ell\) 位数的各位数字为 \(d_1,\dots,d_\ell\)。如果其中某一位恰好等于其余各位数字之和，并且这位数字的值为 \(s\)，那么显然有
$$d_1+\cdots+d_\ell=s+s=2s.$$
反过来，如果某个数的总数位和等于 \(2s\)，并且它至少包含一个数字 \(s\)，那么把其中一个 \(s\) 单独拿出来，剩余数字之和就正好也是 \(s\)。因此原题条件与“总数位和为 \(2s\)，且至少出现一次 \(s\)”完全等价。
所以，对每个固定的 \(s\)，我们只需要统计并求和所有数位和为 \(2s\) 且包含数字 \(s\) 的十进制数。这里也不会发生重复计数，因为见证数字由总数位和的一半唯一决定。
固定 \(s\in\{0,\dots,9\}\)，记 \(T=2s\)。对每个长度 \(\ell\)、当前数位和 \(u\)、以及标志位 \(h\in\{0,1\}\)，定义 \(\mathcal{N}_{\ell,s}(u,h)\) 为所有满足以下条件的 \(\ell\) 位十进制数集合：首位不为零、数位和为 \(u\)、并且当 \(h=1\) 时表示这个数中已经出现过至少一个数字 \(s\)。
进一步定义
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$$
其中 \(A_{\ell,s}(u,h)\) 表示该状态下有多少个数，\(B_{\ell,s}(u,h)\) 表示这些数本身的数值之和。于是，对固定的 \(s\) 来说，长度为 \(\ell\) 的有效数贡献恰好是
$$B_{\ell,s}(T,1).$$
由于每一位数字都非负，一旦某个状态已经满足 \(u>T\)，之后再追加数字只会让和更大，不可能再回到目标和 \(T\)。所以这样的状态可以立刻丢弃。
因为首位不能是零，所以初始时只能选择 \(d\in\{1,\dots,9\}\)。只有当 \(d\le T\) 时，这个一位数才可能属于某个合法状态，并且此时有
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
其余所有状态的初值都为零。特别地，当 \(s=0\) 时有 \(T=0\)，而正整数的一位十进制表示不可能以 \(0\) 开头，因此根本没有合法初始状态。这个分支自然贡献 \(0\)，与“正数的数位和不可能为 \(0\)”完全一致。
设当前长度为 \(\ell\) 的某个状态具有数位和 \(u\)、标志位 \(h\)、数量 \(A_{\ell,s}(u,h)\)、数值总和 \(B_{\ell,s}(u,h)\)。现在在右侧追加一位 \(d\in\{0,\dots,9\}\)，就得到长度为 \(\ell+1\) 的新数，其新的数位和为
$$u'=u+d,$$
新的标志位为
$$h'=\begin{cases} 1,& \text{若 } h=1 \text{ 或 } d=s,\\ 0,& \text{否则。} \end{cases}$$
因此，数量递推式是
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$$
对于数值总和，如果旧状态中的某个数是 \(x\)，追加数字 \(d\) 后变成 \(10x+d\)。把整个状态一起求和，就得到
$$\sum(10x+d)=10\sum x+d\cdot \#\{\text{该状态中的数字}\}.$$
于是第二个递推式为
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$$
所有更新都在模 \(10^{16}\) 下进行。
对固定的 \(s\)，长度从 \(1\) 到 \(n\) 的全部贡献为
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$$
最终答案就是
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$$
最重要的结构性结论是 \(2s\le 18\)。正因为目标数位和永远不超过 \(18\)，实现才可以把 DP 表固定在非常小的范围内，不会随着 \(n\) 的增大而膨胀。
此时 \(T=4\)。当长度为 \(1\) 时，可选的起始数字是 \(1,2,3,4\)，对应的状态为
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
对应的数值总和分别就是 \(1,2,3,4\)。
当长度为 \(2\) 时，数位和为 \(4\) 且至少包含一个数字 \(2\) 的有效数只有 \(22\)，因此
$$B_{2,2}(4,1)=22.$$
当长度为 \(3\) 时，有效数是
$$112,\ 121,\ 202,\ 211,\ 220,$$
它们的和为
$$112+121+202+211+220=866.$$
所以，见证数字 \(2\) 在长度不超过 \(3\) 时的总贡献为
$$22+866=888.$$
这正好体现了递推的作用：程序并不会把所有更长的数字逐个列出来，而是通过“状态数量”和“状态数值和”这两个聚合量，得到同样的结果。
C++、Python 和 Java 实现都会依次处理 \(0\) 到 \(9\) 这十个可能的见证数字。对每个 \(s\)，代码维护两个 \(19\times 2\) 的表：一个记录当前长度下每种状态对应的前缀数量，另一个记录这些前缀数值的总和。
第一层由所有合法的一位数初始化得到。之后每增加一位，就尝试追加数字 \(0\) 到 \(9\)，并用上面的两个递推式同时更新“数量表”和“数值和表”。每处理完一个长度，就把数位和等于 \(2s\) 且标志位为 \(1\) 的状态加入全局答案，然后把新表滚动成下一轮的当前表。
整个过程不需要回溯，也不需要显式保存大规模候选数集合。唯一需要持续注意的是所有更新都要对 \(10^{16}\) 取模，以保证中间结果始终受控。
可能的见证数字只有 \(10\) 个，数位和状态最多 \(19\) 个，标志位只有 \(2\) 种，每次转移最多尝试 \(10\) 个追加数字。因此每一层的工作量都被一个很小的常数控制，总时间复杂度为
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$$
由于只保留当前层和下一层两个表，额外空间复杂度为
$$O(19\cdot 2)=O(1),$$
相对于 \(n\) 来说是常数级。
В этой задаче десятичное число считается подходящим, если одна из его цифр равна сумме всех остальных цифр. Если такую выделенную цифру обозначить через \(s\), то общая сумма цифр обязана быть равной \(2s\). Поэтому реализации на C++, Python и Java перебирают \(s\in\{0,\dots,9\}\), суммируют все числа длины от \(1\) до \(n\), у которых сумма цифр равна \(2s\) и при этом хотя бы одна цифра равна \(s\), а затем берут общий результат по модулю \(10^{16}\).
Именно эта переформулировка делает задачу вычислимо небольшой. Так как \(s\le 9\), сумма цифр любого подходящего числа не превосходит \(18\). Значит, динамическому программированию достаточно хранить очень маленькое измерение по сумме цифр.
Решение не перебирает все кандидаты по одному. Вместо этого для каждого возможного «свидетельствующего» значения \(s\) оно хранит агрегированную информацию обо всех префиксах с фиксированной длиной, фиксированной суммой цифр и флагом, показывающим, встречалась ли уже цифра \(s\).
Пусть цифры \(\ell\)-значного числа равны \(d_1,\dots,d_\ell\). Если одна из цифр равна сумме всех остальных и эта цифра равна \(s\), то
$$d_1+\cdots+d_\ell=s+s=2s.$$
Обратное тоже верно: если общая сумма цифр равна \(2s\) и хотя бы одна цифра равна \(s\), то после удаления одной такой цифры сумма оставшихся цифр будет равна \(s\). Значит, исходное условие выполнено.
Следовательно, для фиксированного \(s\) нужно просто просуммировать все числа с суммой цифр \(2s\), содержащие хотя бы одну цифру \(s\). Двойного счёта нет, потому что свидетельствующая цифра однозначно определяется как половина общей суммы цифр.
Зафиксируем \(s\in\{0,\dots,9\}\) и обозначим \(T=2s\). Для каждой длины \(\ell\), суммы цифр \(u\) и флага \(h\in\{0,1\}\) пусть \(\mathcal{N}_{\ell,s}(u,h)\) обозначает множество всех \(\ell\)-значных десятичных чисел без ведущего нуля с суммой цифр \(u\), где \(h=1\) означает, что цифра \(s\) уже встретилась.
Определим
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$$
Первая величина считает количество чисел в состоянии, а вторая хранит сумму их значений. Тогда для фиксированного \(s\) вклад всех корректных чисел длины \(\ell\) равен
$$B_{\ell,s}(T,1).$$
Поскольку все цифры неотрицательны, состояние с \(u>T\) уже никогда не сможет вернуться к целевой сумме \(T\), поэтому такие состояния можно сразу отбросить.
Первая цифра не может быть нулём, значит изначально возможны только \(d\in\{1,\dots,9\}\). Одноцифровое состояние существует только при \(d\le T\), и тогда
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
Все остальные состояния равны нулю. В частности, для \(s=0\) имеем \(T=0\), но допустимого одноцифрового старта не существует. Поэтому этот случай автоматически даёт нулевой вклад, что согласуется с тем, что положительное десятичное число не может иметь сумму цифр \(0\).
Рассмотрим состояние длины \(\ell\) с суммой цифр \(u\), флагом \(h\), количеством \(A_{\ell,s}(u,h)\) и суммой значений \(B_{\ell,s}(u,h)\). Если приписать справа новую цифру \(d\in\{0,\dots,9\}\), то получится число длины \(\ell+1\) с новой суммой цифр
$$u'=u+d,$$
а новый флаг будет равен
$$h'=\begin{cases} 1,& \text{если } h=1 \text{ или } d=s,\\ 0,& \text{иначе.} \end{cases}$$
Отсюда следует рекуррентное обновление для количества:
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$$
Для суммы значений заметим, что каждое старое число \(x\) превращается в \(10x+d\). Если суммировать по всему состоянию, получим
$$\sum(10x+d)=10\sum x+d\cdot \#\{\text{чисел в состоянии}\}.$$
Следовательно, второе обновление имеет вид
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$$
Все вычисления выполняются по модулю \(10^{16}\).
Для фиксированного \(s\) вклад длин от \(1\) до \(n\) равен
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$$
Итоговый ответ равен
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$$
Главный структурный факт заключается в том, что \(2s\le 18\). Поэтому динамике нужны только суммы \(0,1,\dots,18\), а значит достаточно маленькой таблицы фиксированного размера.
Здесь \(T=4\). Для длины \(1\) возможные стартовые цифры равны \(1,2,3,4\). Они создают состояния
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
с соответствующими суммами значений \(1,2,3,4\).
Для длины \(2\) единственное корректное число с суммой цифр \(4\), содержащее цифру \(2\), это \(22\), поэтому
$$B_{2,2}(4,1)=22.$$
Для длины \(3\) корректные числа таковы:
$$112,\ 121,\ 202,\ 211,\ 220,$$
и их сумма равна
$$112+121+202+211+220=866.$$
Значит, общий вклад свидетеля \(2\) для длин не больше \(3\) равен
$$22+866=888.$$
Именно такой промежуточный результат и восстанавливает динамика: она не перечисляет длинные числа напрямую, а получает ту же сумму через агрегированные количества и агрегированные суммы значений.
Реализации на C++, Python и Java последовательно перебирают десять возможных свидетельствующих цифр. Для каждой из них поддерживаются две таблицы размера \(19\times 2\) для текущей длины: одна хранит количество префиксов в каждом состоянии, другая хранит сумму числовых значений этих префиксов.
Первый слой инициализируется допустимыми одноцифровыми числами. Каждый следующий слой строится приписыванием цифры от \(0\) до \(9\) и обновлением обеих таблиц по приведённым выше формулам. После обработки каждой длины в глобальный ответ добавляется состояние с суммой цифр \(2s\) и флагом \(1\), после чего таблицы переиспользуются для следующей длины.
Ни рекурсии, ни перебора огромных наборов чисел не требуется. Единственное техническое ограничение состоит в том, что все обновления сразу берутся по модулю \(10^{16}\), чтобы промежуточные суммы оставались ограниченными.
Есть только \(10\) возможных свидетельствующих цифр, не более \(19\) значений суммы цифр, \(2\) значения флага и \(10\) вариантов добавляемой цифры. Поэтому работа на каждом уровне длины ограничена небольшой константой, а общее время работы равно
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$$
Поскольку хранятся лишь текущий и следующий слои, дополнительная память составляет
$$O(19\cdot 2)=O(1)$$
по отношению к \(n\).
في هذه المسألة يكون العدد العشري صالحًا إذا كانت إحدى خاناته تساوي مجموع جميع الخانات الأخرى. إذا سمّينا هذه الخانة المميِّزة \(s\)، فإن مجموع الخانات الكلي لا بد أن يساوي \(2s\). لهذا السبب تمرّ تطبيقات C++ وPython وJava على جميع القيم \(s\in\{0,\dots,9\}\)، ثم تجمع كل الأعداد ذات الطول من \(1\) إلى \(n\) التي يساوي مجموع خاناتها \(2s\) وتحتوي على الأقل على خانة واحدة تساوي \(s\)، ثم تعيد المجموع النهائي modulo \(10^{16}\).
هذه الصياغة المكافئة هي لبّ التبسيط. بما أن \(s\le 9\)، فإن أي عدد صالح لا يمكن أن يتجاوز مجموع خاناته \(18\). لذلك لا تحتاج البرمجة الديناميكية إلى فضاء هائل من الأعداد ذات \(n\) خانة، بل إلى بعد صغير جدًا خاص بمجموع الخانات فقط.
الحل لا يعدد جميع الأعداد المرشحة واحدًا واحدًا. بدلًا من ذلك، ولكل رقم شاهد محتمل \(s\)، يحتفظ بمعلومتين مجمعتين عن جميع البوادئ ذات طول ثابت ومجموع خانات ثابت وعَلَم يحدد هل ظهر الرقم \(s\) من قبل أم لا.
لتكن خانات عدد طوله \(\ell\) هي \(d_1,\dots,d_\ell\). إذا كانت إحدى هذه الخانات مساوية لمجموع الخانات الأخرى، وكانت قيمة تلك الخانة هي \(s\)، فلدينا
$$d_1+\cdots+d_\ell=s+s=2s.$$
والعكس صحيح أيضًا: إذا كان مجموع الخانات الكلي يساوي \(2s\) وكان في العدد خانة واحدة على الأقل تساوي \(s\)، فإن حذف إحدى هذه الخانات يترك باقي الخانات بمجموع يساوي \(s\)، وبذلك يتحقق الشرط الأصلي تمامًا.
إذًا، من أجل \(s\) ثابت، يكفي أن نجمع كل الأعداد التي مجموع خاناتها \(2s\) وتحتوي على الخانة \(s\). ولا يوجد عدّ مزدوج، لأن رقم الشاهد يتحدد بصورة وحيدة من نصف مجموع الخانات الكلي.
ثبّت \(s\in\{0,\dots,9\}\) واكتب \(T=2s\). لكل طول \(\ell\)، ولكل مجموع خانات \(u\)، ولكل علم \(h\in\{0,1\}\)، نعرّف \(\mathcal{N}_{\ell,s}(u,h)\) على أنه مجموعة جميع الأعداد العشرية ذات \(\ell\) خانة، من دون صفر بادئ، والتي مجموع خاناتها \(u\)، حيث يعني \(h=1\) أن الخانة \(s\) ظهرت بالفعل.
ثم نعرّف
$$A_{\ell,s}(u,h)=\#\mathcal{N}_{\ell,s}(u,h),\qquad B_{\ell,s}(u,h)=\sum_{x\in\mathcal{N}_{\ell,s}(u,h)} x.$$
الكمية الأولى تعدّ عدد الأعداد داخل الحالة، والكمية الثانية تجمع القيم العددية الفعلية لتلك الأعداد. وبالنسبة إلى \(s\) الثابت، فإن مساهمة الأعداد الصحيحة ذات الطول \(\ell\) تساوي بالضبط
$$B_{\ell,s}(T,1).$$
وبما أن الخانات غير سالبة، فأي حالة تحقق \(u>T\) لا يمكن أن تعود لاحقًا إلى المجموع الهدف \(T\)، ولذلك يمكن تجاهلها فورًا.
لا يجوز أن تكون الخانة الأولى صفرًا، لذا فإن الاختيارات الابتدائية الممكنة هي فقط \(d\in\{1,\dots,9\}\). ولا توجد حالة ذات خانة واحدة إلا إذا كان \(d\le T\)، وعندئذٍ يكون
$$A_{1,s}(d,\mathbf{1}_{d=s})=1,\qquad B_{1,s}(d,\mathbf{1}_{d=s})=d.$$
وجميع الحالات الأخرى تبدأ من الصفر. وعلى وجه الخصوص، عندما \(s=0\) يكون \(T=0\)، ولا توجد تهيئة أولية قانونية لعدد عشري موجب من خانة واحدة. لذلك تكون مساهمة هذا الفرع صفرًا، وهو ما يطابق حقيقة أن العدد العشري الموجب لا يمكن أن يكون مجموع خاناته \(0\).
افترض وجود حالة بطول \(\ell\) لها مجموع خانات \(u\)، وعلم \(h\)، وعدد عناصر \(A_{\ell,s}(u,h)\)، ومجموع قيم \(B_{\ell,s}(u,h)\). عند إلحاق خانة جديدة \(d\in\{0,\dots,9\}\) في النهاية نحصل على عدد بطول \(\ell+1\) ومجموع خانات جديد
$$u'=u+d,$$
أما العلم الجديد فهو
$$h'=\max\!\bigl(h,\mathbf{1}_{d=s}\bigr).$$
ومن ثم يصبح تحديث العدّ
$$A_{\ell+1,s}(u',h')\leftarrow A_{\ell+1,s}(u',h')+A_{\ell,s}(u,h).$$
وبالنسبة إلى مجموع القيم، فإن كل عدد قديم \(x\) يتحول إلى \(10x+d\). وإذا جمعنا ذلك على مستوى الحالة كلها نحصل على
$$\sum(10x+d)=10\sum x+d\,A_{\ell,s}(u,h).$$
لذلك يكون التحديث الثاني
$$B_{\ell+1,s}(u',h')\leftarrow B_{\ell+1,s}(u',h')+10B_{\ell,s}(u,h)+d\,A_{\ell,s}(u,h).$$
وجميع العمليات تجرى modulo \(10^{16}\).
بالنسبة إلى \(s\) الثابت، تكون مساهمة جميع الأطوال من \(1\) إلى \(n\) هي
$$C_s(n)=\sum_{\ell=1}^{n} B_{\ell,s}(2s,1).$$
أما الجواب النهائي فهو
$$S(n)=\sum_{s=0}^{9} C_s(n)\pmod{10^{16}}.$$
الحقيقة البنيوية الحاسمة هي أن \(2s\le 18\). لهذا السبب لا تحتاج البرمجة الديناميكية إلا إلى المجاميع \(0,1,\dots,18\)، أي جدول صغير ثابت الحجم بدل بنية ضخمة تنمو مع \(n\).
في هذه الحالة يكون \(T=4\). عند الطول \(1\)، تكون خانات البداية الممكنة هي \(1,2,3,4\)، وتعطي الحالات
$$A_{1,2}(1,0)=A_{1,2}(2,1)=A_{1,2}(3,0)=A_{1,2}(4,0)=1,$$
ومجاميع القيم المناظرة هي \(1,2,3,4\).
عند الطول \(2\)، العدد الصحيح الوحيد الذي مجموع خاناته \(4\) ويحتوي على الخانة \(2\) هو \(22\)، ومن ثم
$$B_{2,2}(4,1)=22.$$
وعند الطول \(3\)، تكون الأعداد الصحيحة الموافقة هي
$$112,\ 121,\ 202,\ 211,\ 220,$$
ومجموعها
$$112+121+202+211+220=866.$$
إذن فإن المساهمة الكلية لرقم الشاهد \(2\) حتى الطول \(3\) تساوي
$$22+866=888.$$
وهذا المثال يوضح بالضبط ما تفعله البرمجة الديناميكية: فهي لا تسرد كل الأعداد الطويلة صراحة، بل تصل إلى المجموع نفسه عبر عدادات مجمعة ومجاميع قيم مجمعة.
تتعامل تطبيقات C++ وPython وJava مع القيم العشر الممكنة لرقم الشاهد واحدةً بعد أخرى. ولكل قيمة \(s\)، تحتفظ الشيفرة بجدولين من الحجم \(19\times 2\) يمثلان الطول الحالي: الجدول الأول يخزن عدد البوادئ في كل حالة، والجدول الثاني يخزن مجموع القيم العددية لتلك البوادئ.
تبدأ الطبقة الأولى بالأعداد القانونية ذات الخانة الواحدة. ثم تُبنى كل طبقة لاحقة عبر إلحاق خانة من \(0\) إلى \(9\)، مع تحديث جدول العدّ وجدول مجموع القيم وفق العلاقات السابقة. وبعد كل طول، تضيف الشيفرة الحالة ذات مجموع الخانات \(2s\) والعلم \(1\) إلى الجواب العام، ثم تعيد استخدام الجداول للطول التالي.
لا حاجة إلى تتبع رجوعي ولا إلى تعداد صريح لمجموعة ضخمة من الأعداد. الحيلة العملية الوحيدة هي إجراء جميع التحديثات modulo \(10^{16}\) حتى تبقى المجاميع الوسيطة ضمن حدود آمنة.
لدينا فقط \(10\) قيم ممكنة لرقم الشاهد، وبحد أقصى \(19\) قيمة لمجموع الخانات، و\(2\) حالتان للعلم، و\(10\) خانات يمكن إلحاقها في كل انتقال. لذلك فإن العمل في كل طول محدود بثابت صغير، ويكون الزمن الكلي
$$O(10\cdot n\cdot 19\cdot 2\cdot 10)=O(n).$$
وبما أن المخزون يقتصر على الطبقة الحالية والطبقة التالية فقط، فإن الذاكرة الإضافية هي
$$O(19\cdot 2)=O(1)$$
بالنسبة إلى \(n\).