The problem asks for the number of 20-digit decimal numbers with no leading zero such that every block of three consecutive digits has sum at most 9. If the digits are \(d_1,d_2,\dots,d_{20}\), the condition is
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$$
A brute-force search would have to inspect \(9\cdot 10^{19}\) candidates, which is hopeless. The crucial fact is that the legality of the next digit depends only on the previous two digits, so the whole problem collapses to a finite-state dynamic program.
The condition is a sliding window of width 3, so the right viewpoint is to keep track of the last two digits of a valid prefix and forget everything earlier.
Suppose two valid prefixes end in the same ordered pair \((a,b)\). Any future continuation will be legal for one prefix exactly when it is legal for the other, because every new test only inspects the new triple formed with those two final digits. That means the complete history can be compressed to the suffix \((a,b)\).
This gives a directed graph on the 100 ordered digit pairs \((a,b)\) with \(0\le a,b\le 9\). There is an edge
$$(a,b)\to(b,c)$$
exactly when
$$a+b+c\le 9.$$
So a valid 20-digit number is nothing more than a valid 2-digit start, with first digit nonzero, followed by an 18-step walk in this graph.
Let \(A_n(a,b)\) be the number of valid \(n\)-digit prefixes whose last two digits are \(a\) and \(b\). For \(n=2\), nothing has been checked yet except the leading-zero rule, so
$$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{otherwise.} \end{cases}$$
This base layer contains the 90 possible two-digit starts \(10,11,\dots,99\). Some of those pairs will die immediately when we try to append a third digit, but they are still legitimate length-2 prefixes.
From a state \((a,b)\), the next digit \(c\) is allowed exactly when the new triple has acceptable sum, namely \(a+b+c\le 9\). Therefore, for \(n\ge 2\),
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{whenever } b+c\le 9,$$
and \(A_{n+1}(b,c)=0\) if \(b+c>9\).
This formula reveals a useful invariant. Once the number has length at least 3, every reachable suffix \((a,b)\) satisfies \(a+b\le 9\), because it must have appeared inside some valid triple. So the active state space shrinks from 100 table cells to only
$$\sum_{a=0}^{9}(10-a)=55$$
reachable pairs after the first true transition.
The smallest nontrivial case is \(n=3\). For a fixed first digit \(a\) and second digit \(b\), the third digit can be any value in \(\{0,1,\dots,9-a-b\}\), so there are \(10-a-b\) choices whenever \(a+b\le 9\).
Hence
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
where \(N_n\) denotes the total number of valid \(n\)-digit numbers. For example, if a valid prefix currently ends in \((3,1)\), then the next digit can only be \(0,1,2,3,4,5\); choosing 6 or more would make the sum of the last three digits exceed 9. This is exactly the rule applied at every later position as well.
After iterating the recurrence until length 20, every valid 20-digit number appears in exactly one final state. Therefore
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
That is the whole solution. The original question about 20-digit numbers with a local three-digit restriction becomes a repeated update on a fixed \(10\times 10\) table.
The C++, Python, and Java implementations all store a \(10\times 10\) table indexed by the last two digits. The entry in row \(a\), column \(b\) is the number of currently known valid prefixes that end in \((a,b)\).
They initialize that table by assigning one count to every two-digit starting prefix whose first digit is 1 through 9 and whose second digit is 0 through 9. Then they sweep positions 3 through 20. For each populated state \((a,b)\), they test every candidate next digit \(c\in\{0,\dots,9\}\); if \(a+b+c\le 9\), the current count is added to the next-layer entry for \((b,c)\). After finishing one position, the old table is discarded and the new one becomes the current state.
At the end, the implementations sum all entries of the last table. A checkpointed version also verifies the small cases \(N_3=165\) and \(N_4=990\), which are consistent with the same recurrence. The fully general form of the algorithm also has the trivial edge cases \(N_1=9\) and \(N_2=90\).
There are at most 100 pair states and, from each state, at most 10 candidate next digits. For a target length \(L\), the running time is therefore
$$O(L\cdot 100\cdot 10)=O(L).$$
In this problem \(L=20\), so the actual workload is tiny. The memory usage is \(O(100)\), because only the current \(10\times 10\) table and the next one are needed. Mathematically only 55 states remain reachable after the first extension, although the code keeps the full 100-cell grid for simplicity.
Gesucht ist die Anzahl der 20-stelligen Dezimalzahlen ohne führende Null, bei denen jede Gruppe aus drei aufeinanderfolgenden Ziffern eine Summe von höchstens 9 hat. Mit Ziffern \(d_1,d_2,\dots,d_{20}\) lautet die Bedingung
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$$
Eine brute-force-Suche müsste \(9\cdot 10^{19}\) Kandidaten betrachten und ist damit ausgeschlossen. Entscheidend ist, dass die Gültigkeit der nächsten Ziffer nur von den letzten zwei Ziffern abhängt. Dadurch wird die Aufgabe zu einem kleinen dynamischen Programm über endliche Zustände.
Die Nebenbedingung ist ein gleitendes Fenster der Breite 3. Deshalb reicht es aus, bei jedem gültigen Präfix nur die letzten beiden Ziffern zu speichern.
Nehmen wir zwei gültige Präfixe, die beide mit demselben geordneten Paar \((a,b)\) enden. Jede spätere Fortsetzung ist für das eine Präfix genau dann erlaubt, wenn sie auch für das andere erlaubt ist, denn jede neue Prüfung betrachtet nur die neu entstehende Dreiergruppe mit diesen beiden Endziffern. Die gesamte frühere Geschichte kann also auf das Suffix \((a,b)\) komprimiert werden.
Damit entsteht ein gerichteter Graph auf den 100 geordneten Ziffernpaaren \((a,b)\) mit \(0\le a,b\le 9\). Es gibt genau dann eine Kante
$$(a,b)\to(b,c),$$
wenn
$$a+b+c\le 9.$$
Eine gültige 20-stellige Zahl ist also nichts anderes als ein zulässiger Start mit zwei Ziffern, wobei die erste Ziffer nicht 0 sein darf, gefolgt von einem Weg der Länge 18 in diesem Graphen.
Sei \(A_n(a,b)\) die Anzahl gültiger \(n\)-stelliger Präfixe, deren letzte beiden Ziffern \(a\) und \(b\) sind. Für \(n=2\) wurde noch keine Dreierbedingung geprüft; einzig die führende Null ist verboten. Deshalb gilt
$$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{sonst.} \end{cases}$$
Diese Basisschicht enthält genau die 90 möglichen zweistelligen Starts \(10,11,\dots,99\). Einige dieser Paare können nicht zu einer dritten Ziffer erweitert werden, bleiben aber trotzdem gültige Präfixe der Länge 2.
Von einem Zustand \((a,b)\) aus ist die nächste Ziffer \(c\) genau dann erlaubt, wenn die neue Dreiergruppe die Summe 9 nicht überschreitet. Für \(n\ge 2\) erhält man daher
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{für } b+c\le 9,$$
und \(A_{n+1}(b,c)=0\), sobald \(b+c>9\) ist.
Daraus folgt sofort ein nützliches Invariante. Sobald die Zahl Länge 3 oder mehr hat, erfüllt jedes erreichbare Suffix \((a,b)\) automatisch \(a+b\le 9\), denn dieses Paar muss in einer zulässigen Dreiergruppe aufgetreten sein. Deshalb schrumpft der tatsächlich aktive Zustandsraum nach dem ersten echten Übergang auf nur noch
$$\sum_{a=0}^{9}(10-a)=55$$
erreichbare Paare, obwohl die Tabelle formal 100 Felder besitzt.
Der kleinste nichttriviale Fall ist \(n=3\). Für eine feste erste Ziffer \(a\) und zweite Ziffer \(b\) darf die dritte Ziffer jeden Wert aus \(\{0,1,\dots,9-a-b\}\) annehmen, also gibt es \(10-a-b\) Möglichkeiten, sofern \(a+b\le 9\) ist.
Daher gilt
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
wobei \(N_n\) die Gesamtzahl gültiger \(n\)-stelliger Zahlen bezeichnet. Endet ein gültiges Präfix zum Beispiel auf \((3,1)\), dann sind als nächste Ziffer nur \(0,1,2,3,4,5\) erlaubt; ab 6 wäre die Summe der letzten drei Ziffern zu groß. Genau dieselbe lokale Regel wird in der vollen DP an jeder späteren Position verwendet.
Nach der Iteration bis zur Länge 20 erscheint jede gültige 20-stellige Zahl in genau einem Endzustand. Deshalb ist
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
Mehr ist mathematisch nicht nötig. Das ursprüngliche Zählproblem mit einer lokalen Dreierbedingung wird vollständig auf wiederholte Aktualisierungen einer festen \(10\times 10\)-Tabelle reduziert.
Die C++-, Python- und Java-Implementierungen speichern alle Zwischenstände in einer \(10\times 10\)-Tabelle, die durch die letzten beiden Ziffern indiziert ist. Der Eintrag in Zeile \(a\), Spalte \(b\) ist jeweils die Anzahl der bisher bekannten gültigen Präfixe, die auf \((a,b)\) enden.
Zu Beginn erhält jedes zweistellige Startpräfix mit erster Ziffer 1 bis 9 und zweiter Ziffer 0 bis 9 den Wert 1. Danach laufen die Implementierungen die Positionen 3 bis 20 durch. Für jeden belegten Zustand \((a,b)\) werden alle Kandidaten \(c\in\{0,\dots,9\}\) getestet; falls \(a+b+c\le 9\), wird die aktuelle Anzahl auf den Folgezustand \((b,c)\) in der nächsten Tabelle addiert. Nach einer Stelle wird die alte Tabelle verworfen und die neue wird zur aktuellen Schicht.
Am Ende werden alle Einträge der letzten Tabelle aufsummiert. Eine Variante mit Prüfwerten bestätigt zusätzlich die kleinen Fälle \(N_3=165\) und \(N_4=990\); dieselbe Rekursion liefert auch die trivialen Randfälle \(N_1=9\) und \(N_2=90\).
Es gibt höchstens 100 Paarzustände, und von jedem Zustand aus werden höchstens 10 nächste Ziffern betrachtet. Für eine Ziellänge \(L\) ist die Laufzeit daher
$$O(L\cdot 100\cdot 10)=O(L).$$
Hier ist \(L=20\), also ist die tatsächliche Rechenarbeit sehr klein. Der Speicherverbrauch beträgt \(O(100)\), weil nur die aktuelle \(10\times 10\)-Tabelle und die nächste benötigt werden. Mathematisch bleiben nach der ersten Erweiterung sogar nur 55 Zustände erreichbar, auch wenn der Code der Einfachheit halber das volle 100-Felder-Raster beibehält.
İstenen şey, başında 0 bulunmayan 20 basamaklı onluk sayıların kaç tanesinde ardışık her üç basamağın toplamının en fazla 9 olduğunu saymaktır. Basamaklar \(d_1,d_2,\dots,d_{20}\) ise koşul
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20)$$
şeklindedir.
Kaba kuvvetle gitmek \(9\cdot 10^{19}\) adayı incelemek anlamına gelir ve bu pratik değildir. Asıl kilit nokta şudur: yeni eklenecek basamağın geçerli olup olmadığı yalnızca son iki basamağa bağlıdır. Böylece problem sonlu durumlu küçük bir dinamik programlama problemine iner.
Kısıt, genişliği 3 olan kayan bir pencere kısıtıdır. Bu yüzden geçerli bir önekin geçmişini bütünüyle tutmak gerekmez; sadece son iki basamak yeterlidir.
Geçerli iki farklı önek düşünelim ve ikisi de aynı sıralı \((a,b)\) çiftiyle bitsin. Bundan sonra eklenecek herhangi bir devam dizisi, biri için geçerliyse diğeri için de geçerlidir; çünkü her yeni kontrol yalnızca bu iki son basamak ile yeni gelen basamağın oluşturduğu üçlüye bakar. Dolayısıyla daha eski basamakların tamamı unutulabilir.
Böylece \(0\le a,b\le 9\) için 100 adet sıralı basamak çifti üzerinde yönlü bir grafik elde ederiz. Şu durumda bir kenar vardır:
$$(a,b)\to(b,c)$$
ancak ve ancak
$$a+b+c\le 9.$$
Bu bakış açısıyla geçerli bir 20 basamaklı sayı, ilk basamağı sıfır olmayan geçerli bir 2 basamaklı başlangıç ve ardından bu grafikte yapılan 18 adımlık bir yürüyüştür.
\(A_n(a,b)\), son iki basamağı \(a\) ve \(b\) olan geçerli \(n\) basamaklı önek sayısı olsun. \(n=2\) için henüz hiçbir üçlü kontrol edilmediğinden tek kural baştaki sıfır yasağıdır. Bu yüzden
$$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{aksi halde.} \end{cases}$$
Bu temel katman tam olarak 90 farklı iki basamaklı başlangıcı içerir. Bu çiftlerin bir kısmı üçüncü bir basamakla hiç genişleyemez, ama yine de uzunluk 2 için geçerli öneklerdir.
\((a,b)\) durumundan sonra gelecek yeni basamak \(c\), ancak yeni oluşan üçlünün toplamı 9'u aşmıyorsa seçilebilir. Dolayısıyla \(n\ge 2\) için
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{yalnızca } b+c\le 9 \text{ iken},$$
ve \(b+c>9\) ise \(A_{n+1}(b,c)=0\) olur.
Bu formül önemli bir değişmez verir. Sayı uzunluğu en az 3 olduktan sonra, erişilebilen her \((a,b)\) sonluğu otomatik olarak \(a+b\le 9\) koşulunu sağlar; çünkü bu ikili mutlaka geçerli bir üçlünün içinde görünmüş olmalıdır. Bu nedenle ilk gerçek geçişten sonra etkin durum uzayı 100 hücreden
$$\sum_{a=0}^{9}(10-a)=55$$
erişilebilir çifte düşer.
En küçük önemsiz olmayan durum \(n=3\) halidir. İlk basamak \(a\), ikinci basamak \(b\) sabitlenirse, üçüncü basamak \(\{0,1,\dots,9-a-b\}\) kümesinden seçilebilir; yani \(a+b\le 9\) olduğu sürece tam \(10-a-b\) seçenek vardır.
Bu yüzden
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
burada \(N_n\) geçerli \(n\) basamaklı sayıların toplam sayısını gösterir. Örneğin geçerli bir önek \((3,1)\) ile bitiyorsa sıradaki basamak sadece \(0,1,2,3,4,5\) olabilir; 6 veya daha büyük bir değer son üç basamağın toplamını 9'un üstüne taşır. Tam programda her sonraki konumda uygulanan kural da budur.
Bağıntı uzunluk 20'ye kadar yürütüldüğünde, her geçerli 20 basamaklı sayı tam olarak bir son durumda sayılmış olur. Bu nedenle
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
Çözümün tamamı bundan ibarettir. Yerel üçlü kısıtı olan bir sayı sayma problemi, sabit boyutlu bir \(10\times 10\) tablo üzerinde tekrarlı güncellemelere indirgenmiş olur.
C++, Python ve Java uygulamaları, son iki basamakla indekslenen \(10\times 10\) bir tablo tutar. Satır \(a\), sütun \(b\) içindeki değer, \((a,b)\) ile biten geçerli öneklerin o andaki sayısıdır.
Başlangıçta ilk basamağı 1 ile 9 arasında, ikinci basamağı 0 ile 9 arasında olan her iki basamaklı başlangıca 1 değeri atanır. Ardından 3. konumdan 20. konuma kadar ilerlenir. Dolu her \((a,b)\) durumu için, aday yeni basamak \(c\in\{0,\dots,9\}\) tek tek denenir; eğer \(a+b+c\le 9\) ise mevcut sayı, sonraki katmandaki \((b,c)\) hücresine eklenir. Bir konum tamamlanınca eski tablo bırakılır ve yeni tablo aktif hale gelir.
Son adımda son tablodaki bütün hücreler toplanır. Kontrol noktaları kullanan sürüm ayrıca \(N_3=165\) ve \(N_4=990\) değerlerini de doğrular; aynı bağıntının genel hali, trivial kenar durumları olan \(N_1=9\) ve \(N_2=90\) sonuçlarını da verir.
En fazla 100 adet basamak-çifti durumu vardır ve her durumdan en fazla 10 yeni basamak denenir. Hedef uzunluk \(L\) için çalışma süresi bu yüzden
$$O(L\cdot 100\cdot 10)=O(L)$$
olur.
Bu problemde \(L=20\) olduğundan gerçek iş yükü çok küçüktür. Bellek kullanımı \(O(100)\)'dür; çünkü yalnızca mevcut \(10\times 10\) tablo ile bir sonraki tabloyu tutmak yeterlidir. Matematiksel olarak ilk uzatmadan sonra yalnızca 55 durum erişilebilir kalsa da, kod sadelik için bütün 100 hücreli ızgarayı korur.
Se pide contar los números decimales de 20 cifras cuya primera cifra no es cero y para los cuales toda terna de cifras consecutivas tiene suma menor o igual que 9. Si escribimos las cifras como \(d_1,d_2,\dots,d_{20}\), la condición es
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$$
Un barrido directo tendría que inspeccionar \(9\cdot 10^{19}\) candidatos, lo cual es inviable. La observación decisiva es que, al añadir una nueva cifra, solo importan las dos cifras anteriores. Eso convierte el problema en una cuenta por programación dinámica sobre un conjunto finito de estados.
La restricción es una ventana deslizante de anchura 3. Por tanto, al estudiar un prefijo válido basta con recordar sus dos últimas cifras.
Supongamos que dos prefijos válidos terminan en el mismo par ordenado \((a,b)\). Cualquier continuación futura será legal para uno exactamente cuando lo sea para el otro, porque cada nueva comprobación solo mira la terna formada por esas dos cifras finales y la cifra recién añadida. En consecuencia, toda la historia anterior puede comprimirse al sufijo \((a,b)\).
Eso lleva a un grafo dirigido sobre los 100 pares ordenados \((a,b)\) con \(0\le a,b\le 9\). Existe una arista
$$(a,b)\to(b,c)$$
si y solo si
$$a+b+c\le 9.$$
Así, un número válido de 20 cifras no es más que un comienzo válido de 2 cifras, con primera cifra distinta de cero, seguido por un recorrido de 18 pasos en ese grafo.
Sea \(A_n(a,b)\) el número de prefijos válidos de longitud \(n\) cuyas dos últimas cifras son \(a\) y \(b\). Para \(n=2\) todavía no se ha comprobado ninguna terna; la única restricción es que la primera cifra no sea cero. Por eso
$$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{en otro caso.} \end{cases}$$
Esta capa base contiene exactamente los 90 comienzos posibles de dos cifras \(10,11,\dots,99\). Algunos de esos pares no podrán extenderse a una tercera cifra, pero siguen siendo prefijos válidos de longitud 2.
Desde un estado \((a,b)\), la siguiente cifra \(c\) es admisible exactamente cuando la nueva terna no supera la suma 9. Por tanto, para \(n\ge 2\),
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{siempre que } b+c\le 9,$$
y \(A_{n+1}(b,c)=0\) si \(b+c>9\).
De aquí se obtiene un invariante útil. Una vez que la longitud es al menos 3, todo sufijo alcanzable \((a,b)\) satisface automáticamente \(a+b\le 9\), porque ese par tuvo que aparecer dentro de alguna terna válida. Por eso, aunque la tabla completa tenga 100 celdas, después de la primera transición real solo quedan
$$\sum_{a=0}^{9}(10-a)=55$$
pares potencialmente activos.
El primer caso no trivial es \(n=3\). Fijadas la primera cifra \(a\) y la segunda cifra \(b\), la tercera puede tomar cualquier valor de \(\{0,1,\dots,9-a-b\}\), de modo que hay \(10-a-b\) posibilidades cuando \(a+b\le 9\).
Así,
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
donde \(N_n\) denota el número total de números válidos de \(n\) cifras. Por ejemplo, si un prefijo válido termina en \((3,1)\), la siguiente cifra solo puede ser \(0,1,2,3,4,5\); elegir 6 o más haría que la suma de las tres últimas cifras excediera 9. Esa misma regla local es exactamente la que aplica el DP completo en cada posición posterior.
Una vez iterada la recurrencia hasta longitud 20, cada número válido de 20 cifras queda contado en exactamente un estado final. Por tanto,
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
Eso agota la matemática del problema. La cuenta original sobre números de 20 cifras con una restricción local de tamaño 3 se reduce a actualizar repetidamente una tabla fija de \(10\times 10\).
Las implementaciones en C++, Python y Java guardan una tabla de \(10\times 10\) indexada por las dos últimas cifras. La entrada de la fila \(a\) y la columna \(b\) representa cuántos prefijos válidos conocidos en ese momento terminan en \((a,b)\).
La inicialización asigna un conteo 1 a cada comienzo de dos cifras cuya primera cifra va de 1 a 9 y cuya segunda cifra va de 0 a 9. Después, el programa recorre las posiciones 3 hasta 20. Para cada estado no vacío \((a,b)\), prueba todas las cifras candidatas \(c\in\{0,\dots,9\}\); si \(a+b+c\le 9\), añade el conteo actual a la celda \((b,c)\) de la tabla siguiente. Cuando termina una posición, la tabla vieja se descarta y la nueva pasa a ser la capa activa.
Al final se suman todas las entradas de la última tabla. Una versión con comprobaciones también valida los casos pequeños \(N_3=165\) y \(N_4=990\), mientras que la formulación general del algoritmo incluye además los casos inmediatos \(N_1=9\) y \(N_2=90\).
Hay como máximo 100 estados de pares, y desde cada estado se prueban como máximo 10 cifras siguientes. Para una longitud objetivo \(L\), el tiempo de ejecución es entonces
$$O(L\cdot 100\cdot 10)=O(L).$$
Aquí \(L=20\), así que el trabajo real es muy pequeño. La memoria es \(O(100)\), ya que solo se necesitan la tabla actual de \(10\times 10\) y la siguiente. Desde el punto de vista matemático, después de la primera extensión solo 55 estados pueden seguir siendo alcanzables, aunque el código conserva la cuadrícula completa de 100 celdas por simplicidad.
题目要求统计 20 位十进制数的个数，其中首位不能为 0，并且任意连续三位数字之和都不超过 9。如果把这个数写成 \(d_1,d_2,\dots,d_{20}\)，那么约束就是
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$$
如果直接暴力枚举，就要面对 \(9\cdot 10^{19}\) 个候选数，显然完全不可行。真正的突破点在于：当我们准备追加下一位数字时，是否还能保持合法，只取决于前两位数字，而与更早的部分无关。于是原题可以被改写成一个很小的有限状态计数问题。
这道题的限制本质上是一个长度为 3 的滑动窗口条件，因此最自然的做法就是把“最后两位数字”当成状态，把更早的历史全部压缩掉。
设有两个不同的合法前缀，但它们都以同一个有序对 \((a,b)\) 结尾。那么从这一刻起，无论继续接上什么后缀，它们的合法性判断都会完全一致。原因很简单：每次新增一位，只会检查新形成的那组三位数字，而那组三位里真正来自旧前缀的信息只有最后两位，也就是 \(a\) 和 \(b\)。
因此，原问题可以看成一个有向图上的路径计数问题。图的顶点是全部 100 个数字对 \((a,b)\)，其中 \(0\le a,b\le 9\)。当且仅当
$$a+b+c\le 9$$
时，我们在图中连一条边
$$(a,b)\to(b,c).$$
从这个角度看，一个合法的 20 位数就是：先选一个合法的两位起点，首位必须非零，然后在这张图上继续走 18 步。
记 \(A_n(a,b)\) 为“长度为 \(n\) 的合法前缀中，最后两位恰好是 \(a,b\) 的个数”。当 \(n=2\) 时，题目里的“三位和不超过 9”这一条件还根本没有出现，所以唯一需要满足的只是首位不能为 0。于是有
$$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{其他情况。} \end{cases}$$
这说明初始层恰好包含 90 个两位前缀，也就是从 10 到 99 的全部两位数。注意，这里面有些末尾状态虽然本身作为两位前缀是合法的，但一旦尝试接第三位就会立刻失效；这一点并不影响它们作为初始层状态存在。
如果当前状态是 \((a,b)\)，准备追加下一位 \(c\)，那么唯一需要检查的就是新形成的三位和 \(a+b+c\)。只要它不超过 9，这次转移就是合法的，新的末两位状态就变成 \((b,c)\)。因此对于 \(n\ge 2\)，有
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{只要 } b+c\le 9,$$
而当 \(b+c>9\) 时，\(A_{n+1}(b,c)=0\)。
这个公式还给出一个非常有用的不变量。只要长度已经达到 3 或以上，任何真正可达的末两位 \((a,b)\) 都必须满足 \(a+b\le 9\)。因为如果 \(a+b>9\)，那么无论前一位是什么，三位和都不可能不超过 9，所以这种状态永远不可能出现在合法三位窗口里。也就是说，虽然程序表面上维护了一个 \(10\times 10\) 的表，但从第一次真实扩展之后，真正可能非零的状态只有
$$\sum_{a=0}^{9}(10-a)=55$$
个。
最小的非平凡情况是 \(n=3\)。设第一位是 \(a\)，第二位是 \(b\)。如果想让第三位存在，就必须满足 \(a+b\le 9\)，而此时第三位 \(c\) 可以在
$$0,1,\dots,9-a-b$$
之间任取，所以一共有 \(10-a-b\) 种选择。
于是三位合法数的总数就是
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
这里 \(N_n\) 表示合法 \(n\) 位数的总数。举个具体例子，如果当前合法前缀的末两位是 \((3,1)\)，那么下一位只能是 \(0,1,2,3,4,5\)；一旦选到 6、7、8、9，最后三位之和就会超过 9。整个 20 位的动态规划，反复使用的就是这一条局部规则。
把上面的递推一直推进到长度 20 之后，每一个合法的 20 位数都会落在某个唯一的最终状态里。因此最终答案满足
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
这就是完整的数学推导。原题看起来是在庞大的 20 位数空间里做筛选，实际上只是在一张固定大小的状态表上做 18 轮更新。
C++、Python 和 Java 的实现都维护了一张 \(10\times 10\) 的计数表，行列分别对应最后两位数字 \(a,b\)。表格中的值表示：当前已经构造出的合法前缀里，有多少个是以 \((a,b)\) 结尾的。
初始化时，所有首位在 1 到 9、第二位在 0 到 9 的两位前缀都被赋值为 1。接下来，程序从第 3 位一路推进到第 20 位。对于当前每个非零状态 \((a,b)\)，它会枚举候选下一位 \(c\in\{0,\dots,9\}\)。如果 \(a+b+c\le 9\)，就把当前计数累加到下一层的 \((b,c)\) 位置。完成一整层以后，用新表替换旧表，于是始终只保留“当前层”和“下一层”这两份信息。
最后一步就是把终层表中的全部条目相加。带检查点的实现还会额外验证小规模结果 \(N_3=165\) 和 \(N_4=990\)，以确认递推没有写错；同一个递推在一般形式下还自然包含 \(N_1=9\) 与 \(N_2=90\) 这两个边界值。
状态数最多只有 100 个，每个状态最多尝试 10 个下一位数字。因此，对于目标长度 \(L\)，时间复杂度为
$$O(L\cdot 100\cdot 10)=O(L).$$
本题里 \(L=20\)，所以实际工作量非常小。空间复杂度是 \(O(100)\)，因为只需要保存当前 \(10\times 10\) 表和下一张 \(10\times 10\) 表。虽然从数学上说，第一次扩展之后真正可能非零的状态只剩 55 个，但实现为了简洁仍然保留完整的 100 格表。
Нужно посчитать количество 20-значных десятичных чисел без ведущего нуля, у которых сумма любых трех подряд идущих цифр не превосходит 9. Если цифры равны \(d_1,d_2,\dots,d_{20}\), то условие записывается так:
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$$
Перебор всех кандидатов означал бы просмотр \(9\cdot 10^{19}\) чисел, что совершенно нереально. Ключевое наблюдение состоит в том, что допустимость следующей цифры определяется только двумя предыдущими цифрами. Поэтому задача сводится к небольшой динамике по конечному числу состояний.
Ограничение задается скользящим окном длины 3, а значит, для продолжения допустимого префикса достаточно помнить только две последние цифры.
Пусть есть два допустимых префикса, которые заканчиваются одной и той же парой \((a,b)\). Любое дальнейшее продолжение будет допустимым для первого тогда и только тогда, когда оно допустимо для второго, потому что каждый новый тест смотрит только на новую тройку, содержащую эти две последние цифры. Значит, всю более раннюю историю можно забыть и заменить состоянием \((a,b)\).
Так возникает ориентированный граф на 100 упорядоченных парах цифр \((a,b)\), где \(0\le a,b\le 9\). Ребро
$$(a,b)\to(b,c)$$
существует ровно тогда, когда
$$a+b+c\le 9.$$
Следовательно, допустимое 20-значное число можно рассматривать как допустимый старт из двух цифр с ненулевой первой цифрой и затем как путь длины 18 по этому графу.
Обозначим через \(A_n(a,b)\) число допустимых \(n\)-значных префиксов, оканчивающихся цифрами \(a\) и \(b\). При \(n=2\) никакая тройка еще не проверяется, поэтому действует только запрет на ведущий ноль. Отсюда
$$A_2(a,b)= \begin{cases} 1,&1\le a\le 9,\ 0\le b\le 9,\\ 0,&\text{иначе.} \end{cases}$$
Этот базовый слой содержит ровно 90 возможных двузначных стартов \(10,11,\dots,99\). Некоторые из них нельзя продолжить до третьей цифры, но как префиксы длины 2 они все равно допустимы.
Если текущее состояние равно \((a,b)\), то следующая цифра \(c\) разрешена тогда и только тогда, когда новая тройка имеет сумму не больше 9. Поэтому для \(n\ge 2\) получаем рекуррентную формулу
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad \text{при } b+c\le 9,$$
а если \(b+c>9\), то \(A_{n+1}(b,c)=0\).
Из этого немедленно следует полезный инвариант. Как только длина становится хотя бы 3, любая достижимая пара \((a,b)\) обязана удовлетворять неравенству \(a+b\le 9\), потому что она должна встречаться внутри некоторой допустимой тройки. Поэтому после первого настоящего перехода реально активное пространство состояний сжимается до
$$\sum_{a=0}^{9}(10-a)=55$$
достижимых пар, хотя формально таблица по-прежнему имеет 100 ячеек.
Первый нетривиальный случай - это \(n=3\). Если первая цифра равна \(a\), а вторая цифра равна \(b\), то третья цифра может принимать любое значение из множества \(\{0,1,\dots,9-a-b\}\). Значит, при условии \(a+b\le 9\) имеется ровно \(10-a-b\) вариантов.
Следовательно,
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
где \(N_n\) обозначает общее число допустимых \(n\)-значных чисел. Например, если допустимый префикс заканчивается на \((3,1)\), то следующей цифрой может быть только \(0,1,2,3,4,5\); при выборе 6, 7, 8 или 9 сумма последних трех цифр стала бы слишком большой. Именно это локальное правило и повторяется в полной динамике на каждом следующем разряде.
После того как рекурсия доведена до длины 20, каждое допустимое 20-значное число учтено ровно в одном конечном состоянии. Поэтому итоговая формула имеет вид
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
На этом математическая часть полностью заканчивается. Большая задача о 20-значных числах с локальным ограничением на каждое окно длины 3 оказывается обычным обновлением фиксированной таблицы \(10\times 10\).
Реализации на C++, Python и Java хранят таблицу \(10\times 10\), индексируемую двумя последними цифрами. Значение в ячейке \((a,b)\) равно числу уже построенных допустимых префиксов, оканчивающихся на эту пару.
Инициализация присваивает значение 1 всем двузначным стартам, у которых первая цифра лежит от 1 до 9, а вторая - от 0 до 9. Затем программа проходит позиции с 3-й по 20-ю. Для каждого непустого состояния \((a,b)\) она перебирает все кандидаты \(c\in\{0,\dots,9\}\); если выполняется условие \(a+b+c\le 9\), текущий счет добавляется в состояние \((b,c)\) следующего слоя. После завершения слоя старая таблица заменяется новой.
В конце суммируются все значения последней таблицы. Версия с контрольными проверками дополнительно подтверждает малые результаты \(N_3=165\) и \(N_4=990\), а общий вид того же алгоритма также естественно покрывает базовые случаи \(N_1=9\) и \(N_2=90\).
Максимум имеется 100 состояний-пар, и из каждого состояния пробуется не более 10 следующих цифр. Поэтому для целевой длины \(L\) время работы равно
$$O(L\cdot 100\cdot 10)=O(L).$$
Здесь \(L=20\), так что фактический объем вычислений очень мал. Память составляет \(O(100)\), поскольку нужны только текущая и следующая таблицы \(10\times 10\). Хотя после первого расширения с математической точки зрения остаются достижимыми лишь 55 состояний, код ради простоты продолжает хранить полную сетку из 100 ячеек.
المطلوب هو عدّ الأعداد العشرية ذات 20 خانة التي لا تبدأ بصفر، والتي يكون فيها مجموع أي ثلاث خانات متتالية أقل من أو يساوي 9. إذا كتبنا العدد على الصورة \(d_1,d_2,\dots,d_{20}\)، فإن الشرط هو
$$d_{i-2}+d_{i-1}+d_i\le 9 \qquad (3\le i\le 20).$$
العدّ المباشر يعني فحص \(9\cdot 10^{19}\) احتمالًا، وهذا غير عملي تمامًا. الفكرة الحاسمة هي أن صلاحية الخانة التالية لا تعتمد إلا على آخر خانتين سابقتين، لا على جميع الخانات السابقة. لهذا تتحول المسألة إلى برمجة ديناميكية على عدد صغير جدًا من الحالات.
القيد هنا هو قيد نافذة منزلقة بطول 3، ولذلك فإن الذاكرة الوحيدة التي نحتاج إليها أثناء البناء هي آخر خانتين من البادئة الصحيحة.
لنفترض أن لدينا بادئتين صحيحتين مختلفتين، لكن كلتيهما تنتهيان بالزوج المرتب \((a,b)\). عندها فإن أي تتمة مستقبلية ستكون صالحة للأولى إذا وفقط إذا كانت صالحة للثانية، لأن كل اختبار جديد ينظر فقط إلى الثلاثية الجديدة المكوَّنة من هاتين الخانتين والخانة التي ستُضاف الآن. وهذا يعني أن كامل التاريخ السابق يمكن ضغطه في الزوج \((a,b)\).
بهذا نحصل على رسم موجَّه على 100 زوج مرتب من الأرقام \((a,b)\)، حيث \(0\le a,b\le 9\). توجد حافة
$$(a,b)\to(b,c)$$
بالضبط عندما
$$a+b+c\le 9.$$
إذن فالعدد الصحيح ذو 20 خانة يمكن فهمه على أنه بداية صحيحة من خانتين، مع منع الصفر في الخانة الأولى، ثم مسار طوله 18 خطوة على هذا الرسم.
لنرمز بـ \(A_n(a,b)\) إلى عدد البادئات الصحيحة ذات الطول \(n\) التي تنتهي بالخانتين \(a\) و\(b\). عندما يكون \(n=2\)، لم يظهر بعد أي قيد يتعلق بثلاث خانات متتالية، ولذلك لا يوجد إلا شرط واحد وهو ألا تكون الخانة الأولى صفرًا. ومن ثم
$$A_2(a,b)=1 \qquad (1\le a\le 9,\ 0\le b\le 9),$$
$$A_2(a,b)=0 \qquad \text{otherwise.}$$
هذه الطبقة الأساسية تحتوي بالضبط على 90 بداية ممكنة من خانتين، أي جميع الأعداد من 10 إلى 99. بعض هذه الأزواج لا يمكن تمديده إلى خانة ثالثة، لكنه مع ذلك يبقى بادئة صحيحة بطول 2.
إذا كانت الحالة الحالية هي \((a,b)\)، فإن الخانة التالية \(c\) تكون مسموحة إذا وفقط إذا كان مجموع الثلاثية الجديدة لا يتجاوز 9. لذلك نحصل، لكل \(n\ge 2\)، على العلاقة
$$A_{n+1}(b,c)=\sum_{a=0}^{9-b-c} A_n(a,b) \qquad (b+c\le 9),$$
أما إذا كان \(b+c>9\) فإن \(A_{n+1}(b,c)=0\).
هذه الصيغة تكشف أيضًا ثابتًا مهمًا. فبمجرد أن يصبح الطول 3 أو أكثر، فإن كل زوج نهائي قابل للوصول \((a,b)\) يجب أن يحقق \(a+b\le 9\)، لأنه لا بد أن يكون قد ظهر داخل ثلاثية صالحة. لذلك، وعلى الرغم من أن الجدول الكامل يملك 100 خلية، فإن عدد الحالات التي يمكن أن تبقى فعليًا بعد أول انتقال حقيقي يساوي فقط
$$\sum_{a=0}^{9}(10-a)=55.$$
أصغر حالة غير تافهة هي \(n=3\). إذا ثبتنا الخانة الأولى \(a\) والخانة الثانية \(b\)، فإن الخانة الثالثة يمكن أن تكون أي قيمة من المجموعة \(\{0,1,\dots,9-a-b\}\)، ولذلك يوجد \(10-a-b\) اختيارًا متى تحقق \(a+b\le 9\).
ومن هنا نحصل على
$$N_3=\sum_{a=1}^{9}\sum_{b=0}^{9-a}(10-a-b)=165,$$
حيث يرمز \(N_n\) إلى العدد الكلي للأعداد الصحيحة ذات \(n\) خانات. فعلى سبيل المثال، إذا كانت البادئة الصحيحة تنتهي بالزوج \((3,1)\)، فإن الخانة التالية لا يمكن أن تكون إلا واحدة من \(0,1,2,3,4,5\)؛ أما اختيار 6 أو أكثر فيجعل مجموع آخر ثلاث خانات أكبر من 9. وهذه القاعدة المحلية نفسها هي التي تُطبَّق في كل خطوة لاحقة من البرمجة الديناميكية الكاملة.
بعد تكرار العلاقة حتى الطول 20، يكون كل عدد صحيح صحيح بطول 20 قد عُدَّ مرة واحدة بالضبط داخل حالة نهائية واحدة. لذلك فإن الجواب النهائي هو
$$N_{20}=\sum_{a=0}^{9}\sum_{b=0}^{9} A_{20}(a,b).$$
وهذا يكمل الاشتقاق الرياضي كله. فالمسألة الأصلية، التي تبدو وكأنها تتطلب البحث داخل فضاء ضخم من الأعداد ذات 20 خانة، تتحول في الحقيقة إلى تحديث متكرر لجدول ثابت حجمه \(10\times 10\).
تحتفظ تطبيقات C++ وPython وJava بجدول \(10\times 10\) مفهرس بآخر خانتين. القيمة الموجودة في الموضع \((a,b)\) تمثل عدد البادئات الصحيحة المعروفة حاليًا التي تنتهي بهاتين الخانتين.
في البداية تُعطى القيمة 1 لكل بداية من خانتين تكون فيها الخانة الأولى بين 1 و9 والخانة الثانية بين 0 و9. بعد ذلك تمر الشيفرة على المواضع من 3 إلى 20. لكل حالة غير صفرية \((a,b)\)، تُجرَّب جميع الخانات المرشحة \(c\in\{0,\dots,9\}\). فإذا تحقق الشرط \(a+b+c\le 9\)، أُضيف العداد الحالي إلى الحالة \((b,c)\) في جدول الطبقة التالية. وبعد إنهاء موضع كامل يُستبدل الجدول القديم بالجديد.
في النهاية تُجمع جميع خلايا الجدول الأخير. وتتحقق النسخة التي تحتوي على نقاط فحص أيضًا من القيمتين الصغيرتين \(N_3=165\) و\(N_4=990\)، بينما تعطي الصياغة العامة نفسها الحالتين الحدّيتين المباشرتين \(N_1=9\) و\(N_2=90\).
يوجد في أقصى الأحوال 100 حالة للزوج الأخير، ومن كل حالة تُفحَص على الأكثر 10 خانات تالية. لذلك، إذا كان الطول الهدف هو \(L\)، فإن الزمن يساوي
$$O(L\cdot 100\cdot 10)=O(L).$$
وفي هذه المسألة لدينا \(L=20\)، لذا فإن حجم العمل الفعلي صغير جدًا. أما الذاكرة فهي \(O(100)\)، لأننا لا نحتاج إلا إلى الجدول الحالي \(10\times 10\) والجدول التالي. ومن الناحية الرياضية تبقى 55 حالة فقط قابلة للوصول بعد أول تمديد، لكن الشيفرة تحتفظ بالشبكة الكاملة ذات 100 خلية من أجل البساطة.