A decimal string \(d_1d_2\dots d_\ell\) with \(d_1\ne 0\) is valid if every position belongs to at least one contiguous substring whose digit sum is \(10\). Let \(a_\ell\) be the number of valid strings of length \(\ell\), and define
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}.$$
The target input is enormous, so the implementation cannot iterate lengths up to \(n\) directly. The solution turns the coverage condition into a finite automaton, extracts a linear recurrence for \(T(n)\), and evaluates that recurrence at very large indices.
Write the prefix sums of the digits as \(P_0=0\) and \(P_t=d_1+\cdots+d_t\). A substring \(d_i\dots d_j\) has digit sum \(10\) exactly when
$$P_j-P_{i-1}=10.$$
The whole method is built around scanning the string from left to right while tracking only the information that can still matter for future sum-\(10\) substrings.
Suppose we have processed digits up to position \(j\), and let \(c\) be the first position that is not yet guaranteed to be covered by a sum-\(10\) substring. Then the unresolved window is \(d_c\dots d_j\), whose total digit sum is
$$\Delta=P_j-P_{c-1}.$$
All digits are nonnegative, so \(\Delta\) can only increase as we append more digits. Therefore, if \(\Delta>10\), no future extension can create a sum-\(10\) substring containing position \(c\), and that branch is impossible. This gives the crucial bound
$$0\le \Delta \le 10.$$
Inside the current unresolved window we keep the set of partial sums
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
These values describe every internal boundary of the unresolved window. We also keep a second set
$$H\subseteq\{0,1,\dots,10\},$$
whose elements are offsets from earlier prefix positions that can still serve as left boundaries of a future sum-\(10\) substring. When a new digit \(x\) is appended, the unresolved total becomes
$$\Delta'=\Delta+x.$$
If \(\Delta'>10\), the transition is rejected. Otherwise we enlarge the partial-sum set to
$$S'=S\cup\{\Delta'\}.$$
The new right endpoint closes the whole unresolved window exactly when there is a complementary historical offset:
$$10-\Delta' \in H.$$
In that case some earlier prefix position \(u\) satisfies \(P_{c-1}-P_u=10-\Delta'\), so
$$P_{j+1}-P_u=10.$$
Hence the substring from \(u+1\) to \(j+1\) has digit sum \(10\) and covers every position from \(c\) through \(j+1\). After this closure, the unresolved window becomes empty again, so the window data resets to
$$S_{\text{new}}=\{0\}.$$
The historical offsets relative to the new boundary are updated by translation and by every internal cut of the closed window:
$$H_{\text{new}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
Because both \(H\) and \(S\) live inside \(\{0,1,\dots,10\}\), only finitely many states can ever occur. Each appended digit gives a deterministic state transition. A state is accepting exactly when no unresolved window remains, which in this encoding means
$$S=\{0\}.$$
So counting valid strings of length \(\ell\) becomes counting length-\(\ell\) paths in a deterministic finite automaton. The first digit uses the alphabet \(\{1,\dots,9\}\), while all later digits use \(\{0,\dots,9\}\).
Let \(a_\ell\) be the number of accepting paths of length \(\ell\). Dynamic programming on the minimized automaton gives the initial values of \(a_\ell\) and therefore of
$$T(n)=\sum_{\ell=1}^{n} a_\ell.$$
Any fixed finite automaton induces repeated matrix multiplication modulo \(10^9+7\), so the cumulative sequence \(T(0),T(1),T(2),\dots\) satisfies a linear recurrence. The implementation samples enough initial terms, recovers the shortest recurrence with Berlekamp-Massey, and then evaluates the \(n\)-th term with polynomial binary exponentiation.
Consider the string \(352\). Its prefix sums are \(0,3,8,10\). While reading it, the unresolved total moves from \(0\) to \(3\), then to \(8\), then to \(10\), never exceeding the allowed bound. At the last digit we have \(10-\Delta'=0\), and the initial historical set already contains \(0\), so the whole string closes as one sum-\(10\) block. Therefore \(352\) is valid.
As a small counting check, no length-\(1\) string can be valid, so \(a_1=0\). For length \(2\), the only valid strings are \(19,28,37,46,55,64,73,82,91\), giving
$$a_2=9,\qquad T(2)=9.$$
The C++, Python, and Java implementations use the same mathematical pipeline. The compiled solver first enumerates every reachable automaton state from the start configuration by repeatedly applying the digit-transition rule described above. After that, it minimizes the raw automaton by partition refinement so that equivalent states are merged without changing the accepted language.
Next, the implementation runs dynamic programming on the minimized automaton. The first step allows digits \(1\) through \(9\); each later step allows \(0\) through \(9\). Summing the counts in accepting states yields \(a_\ell\), and cumulative sums yield \(T(\ell)\). The code generates \(2s+5\) initial values when the minimized automaton has \(s\) states, which is enough to recover the recurrence used in practice.
Finally, Berlekamp-Massey extracts the shortest linear recurrence for the cumulative sequence modulo \(10^9+7\). The solver then evaluates that recurrence at index \(n\) using Kitamasa-style polynomial reduction with binary exponentiation. The Python entry point delegates to the compiled solver, so its numerical behavior matches the compiled versions.
Let \(s_{\text{raw}}\) be the number of reachable raw states, \(s\) the number of minimized states, and \(r\) the recovered recurrence order. Building the reachable raw automaton requires \(O(10s_{\text{raw}})\) transitions. Minimization is near-linear in the transition graph, typically written as \(O(10s_{\text{raw}}\log s_{\text{raw}})\).
The initial dynamic programming phase computes \(2s+5\) terms, so it costs \(O(10s(2s+5))=O(s^2)\) time. Once the recurrence is known, the large-index evaluation costs
$$O(r^2\log n)$$
time and \(O(r)\) extra memory, on top of the automaton tables.
Eine Dezimalfolge \(d_1d_2\dots d_\ell\) mit \(d_1\ne 0\) heißt gültig, wenn jede Position zu mindestens einem zusammenhängenden Teilstring gehört, dessen Ziffernsumme \(10\) ist. Sei \(a_\ell\) die Anzahl gültiger Folgen der Länge \(\ell\), und definiere
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}.$$
Das Ziel-\(n\) ist extrem groß, daher kann die Implementierung die Längen nicht direkt bis \(n\) durchzählen. Die Lösung übersetzt die Überdeckungsbedingung in einen endlichen Automaten, gewinnt daraus eine lineare Rekurrenz für \(T(n)\) und wertet diese Rekurrenz an sehr großen Indizes aus.
Schreibe die Präfixsummen der Ziffern als \(P_0=0\) und \(P_t=d_1+\cdots+d_t\). Ein Teilstring \(d_i\dots d_j\) hat genau dann Ziffernsumme \(10\), wenn
$$P_j-P_{i-1}=10.$$
Die gesamte Methode scannt die Zahl von links nach rechts und speichert nur die Information, die für zukünftige Summe-\(10\)-Teilstrings noch relevant sein kann.
Angenommen, wir haben die Ziffern bis Position \(j\) verarbeitet, und \(c\) sei die erste Position, von der noch nicht sicher ist, dass sie von einem Summe-\(10\)-Teilstring überdeckt wird. Dann ist das offene Fenster \(d_c\dots d_j\), und seine gesamte Ziffernsumme ist
$$\Delta=P_j-P_{c-1}.$$
Alle Ziffern sind nichtnegativ, also kann \(\Delta\) beim Anhängen weiterer Ziffern nur wachsen. Falls \(\Delta>10\) wird, kann keine spätere Erweiterung mehr einen Summe-\(10\)-Teilstring erzeugen, der Position \(c\) enthält; dieser Zweig ist also unmöglich. Damit erhält man die entscheidende Schranke
$$0\le \Delta \le 10.$$
Innerhalb des aktuellen offenen Fensters speichern wir die Menge der Teilsummen
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
Diese Werte beschreiben alle inneren Schnittstellen des offenen Fensters. Zusätzlich speichern wir eine zweite Menge
$$H\subseteq\{0,1,\dots,10\},$$
deren Elemente Offsets zu früheren Präfixpositionen sind, die noch als linke Grenzen eines zukünftigen Summe-\(10\)-Teilstrings dienen können. Wird eine neue Ziffer \(x\) angehängt, dann wird die offene Gesamtsumme zu
$$\Delta'=\Delta+x.$$
Ist \(\Delta'>10\), wird der Übergang verworfen. Andernfalls vergrößert sich die Menge der Teilsummen zu
$$S'=S\cup\{\Delta'\}.$$
Der neue rechte Endpunkt schließt das gesamte offene Fenster genau dann, wenn es einen komplementären historischen Offset gibt:
$$10-\Delta' \in H.$$
Dann existiert eine frühere Präfixposition \(u\) mit \(P_{c-1}-P_u=10-\Delta'\), also gilt
$$P_{j+1}-P_u=10.$$
Folglich hat der Teilstring von \(u+1\) bis \(j+1\) Ziffernsumme \(10\) und überdeckt jede Position von \(c\) bis \(j+1\). Nach diesem Abschluss ist das offene Fenster wieder leer, daher wird die Fensterinformation zu
$$S_{\text{neu}}=\{0\}$$
zurückgesetzt. Die historischen Offsets relativ zur neuen Grenze werden durch Verschiebung und durch alle inneren Schnitte des gerade geschlossenen Fensters aktualisiert:
$$H_{\text{neu}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
Da sowohl \(H\) als auch \(S\) in \(\{0,1,\dots,10\}\) liegen, können nur endlich viele Zustände auftreten. Jede angehängte Ziffer erzeugt einen deterministischen Zustandsübergang. Ein Zustand ist genau dann akzeptierend, wenn kein offenes Fenster mehr übrig ist; in dieser Kodierung bedeutet das
$$S=\{0\}.$$
Das Zählen gültiger Folgen der Länge \(\ell\) wird damit zu einem Zählen von Pfaden der Länge \(\ell\) in einem deterministischen endlichen Automaten. Die erste Ziffer benutzt das Alphabet \(\{1,\dots,9\}\), alle späteren Ziffern \(\{0,\dots,9\}\).
Sei \(a_\ell\) die Anzahl akzeptierender Pfade der Länge \(\ell\). Dynamische Programmierung auf dem minimierten Automaten liefert die Anfangswerte von \(a_\ell\) und damit auch von
$$T(n)=\sum_{\ell=1}^{n} a_\ell.$$
Jeder feste endliche Automat induziert wiederholte Matrixmultiplikation modulo \(10^9+7\), also erfüllt die kumulative Folge \(T(0),T(1),T(2),\dots\) eine lineare Rekurrenz. Die Implementierung erzeugt genügend Anfangsterme, rekonstruiert mit Berlekamp-Massey die kürzeste Rekurrenz und wertet anschließend den \(n\)-ten Term per binärer Polynomexponentiation aus.
Betrachte die Folge \(352\). Ihre Präfixsummen sind \(0,3,8,10\). Beim Einlesen wandert die offene Summe von \(0\) nach \(3\), dann nach \(8\), dann nach \(10\), ohne je die Schranke zu überschreiten. Bei der letzten Ziffer ist \(10-\Delta'=0\), und die anfängliche historische Menge enthält bereits \(0\). Daher schließt sich die gesamte Folge zu einem einzigen Summe-\(10\)-Block, also ist \(352\) gültig.
Als kleine Zählkontrolle gilt: Keine Folge der Länge \(1\) kann gültig sein, also ist \(a_1=0\). Für Länge \(2\) sind die einzigen gültigen Folgen \(19,28,37,46,55,64,73,82,91\), also
$$a_2=9,\qquad T(2)=9.$$
Die C++-, Python- und Java-Implementierungen benutzen dieselbe mathematische Pipeline. Der kompilierte Solver erzeugt zunächst jeden erreichbaren Automatenzustand aus der Startkonfiguration, indem er die oben beschriebene Ziffernübergangsregel wiederholt anwendet. Anschließend minimiert er den Rohautomaten per Partitionsverfeinerung, sodass äquivalente Zustände zusammengelegt werden, ohne die akzeptierte Sprache zu verändern.
Danach läuft eine dynamische Programmierung auf dem minimierten Automaten. Im ersten Schritt sind nur die Ziffern \(1\) bis \(9\) erlaubt, danach jeweils \(0\) bis \(9\). Die Summe über alle akzeptierenden Zustände liefert \(a_\ell\), und kumulative Summen liefern \(T(\ell)\). Wenn der minimierte Automat \(s\) Zustände hat, erzeugt der Code \(2s+5\) Anfangswerte; das genügt in der Praxis für die verwendete Rekonstruktionsphase.
Zum Schluss extrahiert Berlekamp-Massey die kürzeste lineare Rekurrenz der kumulativen Folge modulo \(10^9+7\). Danach wertet der Solver diese Rekurrenz am Index \(n\) mit Kitamasa-artiger Polynomreduktion und binärer Exponentiation aus. Der Python-Einstieg delegiert an den kompilierten Solver, daher stimmt sein numerisches Verhalten mit den kompilierten Versionen überein.
Seien \(s_{\text{raw}}\) die Anzahl erreichbarer Rohzustände, \(s\) die Anzahl minimierter Zustände und \(r\) die Ordnung der rekonstruierten Rekurrenz. Der Aufbau des erreichbaren Rohautomaten benötigt \(O(10s_{\text{raw}})\) Übergänge. Die Minimierung ist nahezu linear im Übergangsgraphen und wird typischerweise als \(O(10s_{\text{raw}}\log s_{\text{raw}})\) angegeben.
Die anfängliche dynamische Programmierung berechnet \(2s+5\) Terme und kostet damit \(O(10s(2s+5))=O(s^2)\) Zeit. Ist die Rekurrenz bekannt, kostet die Auswertung für großen Index
$$O(r^2\log n)$$
Zeit und \(O(r)\) zusätzlichen Speicher, zusätzlich zu den Automatentabellen.
\(d_1\ne 0\) olan bir onluk dizi \(d_1d_2\dots d_\ell\), eğer her konum rakam toplamı \(10\) olan en az bir ardışık alt dizinin içinde kalıyorsa geçerlidir. Uzunluğu \(\ell\) olan geçerli dizilerin sayısına \(a_\ell\) diyelim ve
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}$$
tanımını yapalım. Hedef \(n\) çok büyük olduğu için uygulama uzunlukları tek tek sayamaz. Çözüm, kapsama koşulunu sonlu durumlu bir otomataya dönüştürür, sonra \(T(n)\) için lineer bir bağıntı çıkarır ve bu bağıntıyı çok büyük indislerde değerlendirir.
Rakamların prefix toplamlarını \(P_0=0\) ve \(P_t=d_1+\cdots+d_t\) olarak yazalım. \(d_i\dots d_j\) alt dizisinin rakam toplamı tam olarak \(10\) ise ve ancak ise
$$P_j-P_{i-1}=10$$
olur. Yöntemin tamamı, diziyi soldan sağa tararken yalnızca gelecekteki toplamı \(10\) olan alt diziler için hâlâ önemli olabilecek bilgiyi tutmaya dayanır.
Diyelim ki \(j\). konuma kadar okuduk ve \(c\), henüz toplamı \(10\) olan bir alt diziyle kapsandığı kesinleşmemiş ilk konum olsun. O zaman çözülmemiş pencere \(d_c\dots d_j\) olur ve bu pencerenin toplamı
$$\Delta=P_j-P_{c-1}$$
şeklindedir. Tüm rakamlar negatif olmadığından, yeni rakam ekledikçe \(\Delta\) ancak büyür. Bu yüzden \(\Delta>10\) olursa, gelecekte hiçbir uzatma \(c\) konumunu içeren toplamı \(10\) olan bir alt dizi oluşturamaz; bu dal artık imkansızdır. Böylece temel sınır
$$0\le \Delta \le 10$$
elde edilir.
Geçerli çözülmemiş pencerenin içinde şu kısmi toplam kümesini tutarız:
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
Bu değerler, pencerenin içindeki tüm olası sınırları temsil eder. Buna ek olarak ikinci bir küme daha tutulur:
$$H\subseteq\{0,1,\dots,10\}.$$
Bu kümedeki elemanlar, ileride oluşabilecek toplamı \(10\) olan bir alt dizi için sol sınır olarak hâlâ işe yarayabilecek eski prefix konumlarının ofsetleridir. Yeni bir \(x\) rakamı eklendiğinde çözülmemiş toplam
$$\Delta'=\Delta+x$$
olur. Eğer \(\Delta'>10\) ise geçiş reddedilir. Aksi halde kısmi toplam kümesi
$$S'=S\cup\{\Delta'\}$$
şeklinde genişler.
Yeni sağ uç, çözülmemiş pencerenin tamamını ancak tamamlayıcı bir tarihsel ofset varsa kapatır:
$$10-\Delta' \in H.$$
Bu durumda \(P_{c-1}-P_u=10-\Delta'\) sağlayan daha eski bir \(u\) prefix konumu vardır ve dolayısıyla
$$P_{j+1}-P_u=10$$
olur. Yani \(u+1\) ile \(j+1\) arasındaki alt dizinin toplamı \(10\)'dur ve \(c\) ile \(j+1\) arasındaki tüm konumları kapsar. Bu kapanıştan sonra çözülmemiş pencere tekrar boşalır; pencere verisi
$$S_{\text{yeni}}=\{0\}$$
olarak sıfırlanır. Yeni sınıra göre tarihsel ofsetler hem kaydırma ile hem de yeni kapanan pencerenin tüm iç kesimlerinden türetilerek güncellenir:
$$H_{\text{yeni}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
Hem \(H\) hem de \(S\) yalnızca \(\{0,1,\dots,10\}\) içinde yaşadığı için ortaya çıkabilecek durum sayısı sonludur. Eklenen her rakam deterministik bir durum geçişi üretir. Bir durum ancak çözülmemiş pencere kalmadığında kabul edilir; bu kodlamada bu
$$S=\{0\}$$
demektir. Böylece uzunluğu \(\ell\) olan geçerli dizileri saymak, deterministik sonlu otomat üzerinde uzunluğu \(\ell\) olan kabul edici yolları saymaya dönüşür. İlk rakam için alfabe \(\{1,\dots,9\}\), sonraki rakamlar için \(\{0,\dots,9\}\) kullanılır.
Uzunluğu \(\ell\) olan kabul edici yol sayısı \(a_\ell\) olsun. Minimize edilmiş otomat üzerindeki dinamik programlama, \(a_\ell\)'nin ilk değerlerini ve dolayısıyla
$$T(n)=\sum_{\ell=1}^{n} a_\ell$$
değerlerini üretir. Sabit bir sonlu otomat mod \(10^9+7\) altında tekrarlı matris çarpımına karşılık gelir; bu yüzden kümülatif dizi \(T(0),T(1),T(2),\dots\) lineer bir bağıntı sağlar. Uygulama yeterli sayıda başlangıç terimi örnekler, Berlekamp-Massey ile en kısa bağıntıyı bulur ve sonra polinomların ikili üslenmesi ile \(n\). terimi hesaplar.
\(352\) dizisini ele alalım. Prefix toplamları \(0,3,8,10\)'dur. Okuma sırasında çözülmemiş toplam sırasıyla \(0\), \(3\), \(8\) ve \(10\) olur; sınır hiçbir zaman aşılmaz. Son rakamda \(10-\Delta'=0\) elde edilir ve başlangıç tarihsel kümesi zaten \(0\) içerir. Bu yüzden bütün dizi tek bir toplamı \(10\) olan blok olarak kapanır. Dolayısıyla \(352\) geçerlidir.
Küçük bir sayım kontrolü olarak, uzunluğu \(1\) olan hiçbir dizi geçerli olamaz; yani \(a_1=0\). Uzunluk \(2\) için geçerli diziler yalnızca \(19,28,37,46,55,64,73,82,91\) olduğundan
$$a_2=9,\qquad T(2)=9$$
elde edilir.
C++, Python ve Java uygulamaları aynı matematiksel hattı kullanır. Derlenmiş çözücü önce başlangıç durumundan erişilebilen tüm otomat durumlarını, yukarıdaki rakam geçiş kuralını tekrar tekrar uygulayarak üretir. Ardından ham otomatı bölüm iyileştirme yöntemiyle minimize eder; böylece kabul edilen dili değiştirmeden eşdeğer durumlar birleştirilir.
Daha sonra minimize edilmiş otomat üzerinde dinamik programlama çalıştırılır. İlk adımda yalnızca \(1\) ile \(9\) arasındaki rakamlar, sonraki adımlarda ise \(0\) ile \(9\) arasındaki rakamlar kullanılabilir. Kabul eden durumlardaki sayıları toplamak \(a_\ell\)'yi, kümülatif toplam almak ise \(T(\ell)\)'yi verir. Minimize edilmiş otomatın \(s\) durumu varsa kod \(2s+5\) başlangıç değeri üretir; bu, pratikte kullanılan bağıntıyı çıkarmak için yeterlidir.
Son aşamada Berlekamp-Massey, mod \(10^9+7\) altında kümülatif dizi için en kısa lineer bağıntıyı çıkarır. Çözücü daha sonra bu bağıntıyı \(n\) indisinde, Kitamasa tarzı polinom indirgeme ve ikili üsleme ile değerlendirir. Python girişi derlenmiş çözücüye delege ettiği için sayısal davranışı derlenmiş sürümlerle aynıdır.
\(s_{\text{raw}}\) erişilebilir ham durum sayısı, \(s\) minimize edilmiş durum sayısı ve \(r\) elde edilen lineer bağıntının derecesi olsun. Ham otomatın kurulması \(O(10s_{\text{raw}})\) geçiş gerektirir. Minimizasyon, geçiş grafiğinde yaklaşık doğrusal davranır ve tipik olarak \(O(10s_{\text{raw}}\log s_{\text{raw}})\) şeklinde yazılır.
İlk dinamik programlama aşaması \(2s+5\) terim ürettiği için maliyeti \(O(10s(2s+5))=O(s^2)\) zamandır. Bağıntı bilindikten sonra büyük indis hesabı
$$O(r^2\log n)$$
zaman ve otomat tablolarına ek olarak \(O(r)\) ek bellek kullanır.
Una cadena decimal \(d_1d_2\dots d_\ell\) con \(d_1\ne 0\) es válida si cada posición pertenece al menos a un subsegmento contiguo cuya suma de dígitos es \(10\). Sea \(a_\ell\) el número de cadenas válidas de longitud \(\ell\), y definamos
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}.$$
El valor objetivo de \(n\) es enorme, así que la implementación no puede contar longitudes una por una hasta \(n\). La solución convierte la condición de cobertura en un autómata finito, extrae una recurrencia lineal para \(T(n)\) y evalúa esa recurrencia en índices muy grandes.
Escribamos las sumas prefijo de los dígitos como \(P_0=0\) y \(P_t=d_1+\cdots+d_t\). Un subsegmento \(d_i\dots d_j\) tiene suma de dígitos igual a \(10\) exactamente cuando
$$P_j-P_{i-1}=10.$$
Todo el método consiste en recorrer la cadena de izquierda a derecha y guardar solo la información que todavía puede importar para futuros subsegmentos de suma \(10\).
Supongamos que ya hemos procesado los dígitos hasta la posición \(j\), y que \(c\) es la primera posición que todavía no está garantizada como cubierta por algún subsegmento de suma \(10\). Entonces la ventana no resuelta es \(d_c\dots d_j\), y su suma total es
$$\Delta=P_j-P_{c-1}.$$
Como todos los dígitos son no negativos, \(\Delta\) solo puede crecer cuando añadimos más dígitos. Por tanto, si \(\Delta>10\), ninguna extensión futura podrá crear un subsegmento de suma \(10\) que contenga la posición \(c\), y esa rama es imposible. Así obtenemos la cota fundamental
$$0\le \Delta \le 10.$$
Dentro de la ventana actual no resuelta mantenemos el conjunto de sumas parciales
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
Estos valores describen todos los cortes internos de la ventana no resuelta. También mantenemos un segundo conjunto
$$H\subseteq\{0,1,\dots,10\},$$
cuyos elementos son desplazamientos desde posiciones prefijo anteriores que todavía pueden servir como fronteras izquierdas de un futuro bloque de suma \(10\). Cuando se añade un nuevo dígito \(x\), la suma no resuelta pasa a ser
$$\Delta'=\Delta+x.$$
Si \(\Delta'>10\), la transición se rechaza. En caso contrario, ampliamos el conjunto de sumas parciales a
$$S'=S\cup\{\Delta'\}.$$
El nuevo extremo derecho cierra toda la ventana no resuelta exactamente cuando existe un desplazamiento histórico complementario:
$$10-\Delta' \in H.$$
En ese caso, existe una posición prefijo anterior \(u\) tal que \(P_{c-1}-P_u=10-\Delta'\), y por tanto
$$P_{j+1}-P_u=10.$$
Así, el subsegmento desde \(u+1\) hasta \(j+1\) tiene suma de dígitos \(10\) y cubre todas las posiciones desde \(c\) hasta \(j+1\). Después de este cierre, la ventana no resuelta vuelve a quedar vacía, de modo que la información de ventana se reinicia a
$$S_{\text{nuevo}}=\{0\}.$$
Los desplazamientos históricos relativos a la nueva frontera se actualizan mediante una traslación y mediante todos los cortes internos de la ventana que acaba de cerrarse:
$$H_{\text{nuevo}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
Como tanto \(H\) como \(S\) viven dentro de \(\{0,1,\dots,10\}\), solo puede aparecer un número finito de estados. Cada dígito añadido produce una transición determinista. Un estado es aceptante exactamente cuando ya no queda ventana no resuelta; en esta codificación eso significa
$$S=\{0\}.$$
Por tanto, contar cadenas válidas de longitud \(\ell\) equivale a contar caminos aceptantes de longitud \(\ell\) en un autómata finito determinista. El primer dígito usa el alfabeto \(\{1,\dots,9\}\), mientras que los demás usan \(\{0,\dots,9\}\).
Sea \(a_\ell\) el número de caminos aceptantes de longitud \(\ell\). La programación dinámica sobre el autómata minimizado proporciona los valores iniciales de \(a_\ell\) y, por tanto, de
$$T(n)=\sum_{\ell=1}^{n} a_\ell.$$
Cualquier autómata finito fijo induce multiplicaciones repetidas por una matriz módulo \(10^9+7\), así que la sucesión acumulada \(T(0),T(1),T(2),\dots\) satisface una recurrencia lineal. La implementación toma suficientes términos iniciales, recupera la recurrencia más corta con Berlekamp-Massey y luego evalúa el término \(n\)-ésimo mediante exponenciación binaria de polinomios.
Consideremos la cadena \(352\). Sus sumas prefijo son \(0,3,8,10\). Mientras la leemos, la suma no resuelta pasa de \(0\) a \(3\), luego a \(8\) y finalmente a \(10\), sin superar nunca la cota permitida. En el último dígito se cumple \(10-\Delta'=0\), y el conjunto histórico inicial ya contiene \(0\), así que toda la cadena se cierra como un único bloque de suma \(10\). Por lo tanto, \(352\) es válida.
Como pequeña comprobación de conteo, ninguna cadena de longitud \(1\) puede ser válida, luego \(a_1=0\). Para longitud \(2\), las únicas cadenas válidas son \(19,28,37,46,55,64,73,82,91\), de modo que
$$a_2=9,\qquad T(2)=9.$$
Las implementaciones en C++, Python y Java siguen la misma cadena matemática. El solucionador compilado enumera primero todos los estados alcanzables del autómata a partir de la configuración inicial, aplicando repetidamente la regla de transición por dígitos descrita arriba. Después minimiza el autómata bruto mediante refinamiento de particiones, fusionando estados equivalentes sin cambiar el lenguaje aceptado.
Luego, la implementación ejecuta programación dinámica sobre el autómata minimizado. El primer paso permite dígitos \(1\) a \(9\); cada paso posterior permite \(0\) a \(9\). Sumando los conteos en los estados aceptantes se obtiene \(a_\ell\), y las sumas acumuladas producen \(T(\ell)\). Cuando el autómata minimizado tiene \(s\) estados, el código genera \(2s+5\) valores iniciales, suficientes en la práctica para recuperar la recurrencia utilizada.
Por último, Berlekamp-Massey extrae la recurrencia lineal más corta de la sucesión acumulada módulo \(10^9+7\). Después el solucionador evalúa esa recurrencia en el índice \(n\) mediante reducción de polinomios al estilo de Kitamasa y exponenciación binaria. La entrada de Python delega en el solucionador compilado, de modo que su comportamiento numérico coincide con el de las versiones compiladas.
Sean \(s_{\text{raw}}\) el número de estados brutos alcanzables, \(s\) el número de estados minimizados y \(r\) el orden de la recurrencia recuperada. Construir el autómata bruto alcanzable requiere \(O(10s_{\text{raw}})\) transiciones. La minimización es casi lineal en el grafo de transiciones y suele expresarse como \(O(10s_{\text{raw}}\log s_{\text{raw}})\).
La fase inicial de programación dinámica calcula \(2s+5\) términos, así que cuesta \(O(10s(2s+5))=O(s^2)\) tiempo. Una vez conocida la recurrencia, la evaluación en un índice grande cuesta
$$O(r^2\log n)$$
de tiempo y \(O(r)\) memoria adicional, además de las tablas del autómata.
设十进制串 \(d_1d_2\dots d_\ell\) 的首位满足 \(d_1\ne 0\)。如果串中的每一个位置都至少属于一个数位和为 \(10\) 的连续子串，就称它为有效串。记长度为 \(\ell\) 的有效串个数为 \(a_\ell\)，定义
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}.$$
题目的目标 \(n\) 极大，因此实现不可能按长度一直枚举到 \(n\)。核心思路是先把“每个位置都被某个和为 \(10\) 的子串覆盖”这一条件改写成有限状态自动机，再从自动机导出 \(T(n)\) 的线性递推，最后在极大下标处快速求值。
把数位前缀和记为 \(P_0=0\)，\(P_t=d_1+\cdots+d_t\)。区间 \(d_i\dots d_j\) 的数位和等于 \(10\) 当且仅当
$$P_j-P_{i-1}=10.$$
整个方法都围绕着一个扫描过程展开：从左到右读入数字，但只保存那些对未来仍可能有用的信息，而不是保存完整历史。
设我们已经处理到位置 \(j\)，并令 \(c\) 表示第一个还不能确认已经被某个和为 \(10\) 的子串覆盖的位置。那么当前“未解决窗口”就是 \(d_c\dots d_j\)，它的总和为
$$\Delta=P_j-P_{c-1}.$$
由于十进制数字都非负，随着新数字继续加入，\(\Delta\) 只会增大，不会减小。因此一旦 \(\Delta>10\)，以后无论再追加什么数字，都不可能再出现一个包含位置 \(c\) 的和为 \(10\) 的子串，这条分支就必然失败。于是得到关键有界性
$$0\le \Delta \le 10.$$
在当前未解决窗口内部，维护一个部分和集合
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
这个集合记录了窗口内部所有可能的切分位置。除此之外，还维护第二个集合
$$H\subseteq\{0,1,\dots,10\},$$
其中的元素是相对于更早前缀位置的偏移量，这些更早位置仍然有可能成为未来某个和为 \(10\) 子串的左端点。若追加一个新数字 \(x\)，则未解决窗口的总和变为
$$\Delta'=\Delta+x.$$
如果 \(\Delta'>10\)，这个转移立即被丢弃；否则部分和集合扩展为
$$S'=S\cup\{\Delta'\}.$$
新的右端点能够把整个未解决窗口一次性“关闭”，当且仅当历史集合中存在一个互补偏移：
$$10-\Delta' \in H.$$
这意味着存在某个更早的前缀位置 \(u\)，满足 \(P_{c-1}-P_u=10-\Delta'\)，于是有
$$P_{j+1}-P_u=10.$$
因此，从 \(u+1\) 到 \(j+1\) 的这个连续子串数位和正好为 \(10\)，并且它覆盖了从 \(c\) 到 \(j+1\) 的所有位置。窗口一旦被关闭，新的未解决窗口重新变为空，所以窗口数据重置为
$$S_{\text{new}}=\{0\}.$$
同时，相对于新边界的历史偏移要重新计算。它们由两部分组成：一部分来自旧历史整体平移，另一部分来自刚刚闭合窗口内部的所有切分点：
$$H_{\text{new}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
因为 \(H\) 和 \(S\) 都只取自 \(\{0,1,\dots,10\}\)，所以可能出现的状态总数是有限的。每读入一个数字，状态就做一次确定性的转移。一个状态恰好在“当前已经没有未解决窗口”时为接受态；在这里，这个条件等价于
$$S=\{0\}.$$
于是，长度为 \(\ell\) 的有效串计数，转化为确定性有限自动机上长度为 \(\ell\) 的接受路径计数。首位数字只能从 \(\{1,\dots,9\}\) 中选择，后面的数字则来自 \(\{0,\dots,9\}\)。
记长度为 \(\ell\) 的接受路径数为 \(a_\ell\)。在最小化后的自动机上做动态规划，就能得到若干初始的 \(a_\ell\)，从而得到
$$T(n)=\sum_{\ell=1}^{n} a_\ell.$$
对于固定的有限自动机，反复走一步转移本质上就是模 \(10^9+7\) 下不断乘同一个矩阵，因此累积序列 \(T(0),T(1),T(2),\dots\) 必然满足某个线性递推。实现先生成足够多的初值，再用 Berlekamp-Massey 恢复最短递推，最后通过多项式的二进制快速幂来求第 \(n\) 项。
考虑字符串 \(352\)。它的前缀和是 \(0,3,8,10\)。读入过程中，未解决窗口的总和依次从 \(0\) 变成 \(3\)、\(8\)、\(10\)，始终没有超过允许上界。读到最后一个数字时，满足 \(10-\Delta'=0\)，而初始历史集合中本来就包含 \(0\)，所以整个字符串会被识别为一个完整的和为 \(10\) 的块，因而 \(352\) 是有效串。
再看一个小的计数检验：长度为 \(1\) 的串不可能有效，所以 \(a_1=0\)。长度为 \(2\) 时，唯一有效的串是 \(19,28,37,46,55,64,73,82,91\)，因此
$$a_2=9,\qquad T(2)=9.$$
C++、Python 和 Java 实现遵循同一条数学路线。编译后的求解器首先从起始状态出发，反复应用上面描述的数字转移规则，枚举出所有可达的自动机原始状态。随后，它通过划分细化的方式对原始自动机做最小化，把未来行为完全相同的状态合并起来，同时不改变被接受的字符串集合。
接下来，在最小化后的自动机上进行动态规划。第一步只允许数字 \(1\) 到 \(9\)，之后每一步允许数字 \(0\) 到 \(9\)。把所有接受态上的方案数相加，就得到 \(a_\ell\)；再做前缀累加，就得到 \(T(\ell)\)。若最小化自动机共有 \(s\) 个状态，代码会生成 \(2s+5\) 个初始值，这足以支持后续实际使用的递推恢复阶段。
最后，Berlekamp-Massey 在模 \(10^9+7\) 下恢复累积序列的最短线性递推，求解器再使用 Kitamasa 风格的多项式约化和二进制快速幂，在超大下标 \(n\) 处求出答案。Python 入口只是把计算委托给编译后的求解器，因此它的数值结果与编译型实现保持一致。
记 \(s_{\text{raw}}\) 为可达原始状态数，\(s\) 为最小化后的状态数，\(r\) 为恢复出的递推阶数。构造可达原始自动机需要 \(O(10s_{\text{raw}})\) 次转移。最小化在转移图上接近线性，通常写作 \(O(10s_{\text{raw}}\log s_{\text{raw}})\)。
初始动态规划阶段要生成 \(2s+5\) 项，因此耗时为 \(O(10s(2s+5))=O(s^2)\)。递推确定之后，大下标求值的主成本是
$$O(r^2\log n)$$
时间，额外空间为 \(O(r)\)，另加自动机转移表本身所占的存储。
Десятичная строка \(d_1d_2\dots d_\ell\) с \(d_1\ne 0\) считается корректной, если каждая её позиция принадлежит хотя бы одной непрерывной подстроке, сумма цифр которой равна \(10\). Пусть \(a_\ell\) обозначает число корректных строк длины \(\ell\), и определим
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}.$$
Параметр \(n\) в задаче огромен, поэтому реализация не может просто перебирать длины до \(n\). Решение переводит условие покрытия в конечный автомат, затем извлекает линейную рекуррентность для \(T(n)\) и вычисляет её на очень больших индексах.
Обозначим префиксные суммы цифр через \(P_0=0\) и \(P_t=d_1+\cdots+d_t\). Подстрока \(d_i\dots d_j\) имеет сумму цифр \(10\) тогда и только тогда, когда
$$P_j-P_{i-1}=10.$$
Весь метод строится на проходе слева направо, при котором хранится только та информация, которая ещё может повлиять на будущие подстроки с суммой \(10\).
Предположим, что мы уже обработали цифры до позиции \(j\), а \(c\) — первая позиция, про которую ещё не доказано, что она покрыта некоторой подстрокой с суммой \(10\). Тогда неразрешённое окно равно \(d_c\dots d_j\), а его полная сумма есть
$$\Delta=P_j-P_{c-1}.$$
Все цифры неотрицательны, поэтому при добавлении новых цифр величина \(\Delta\) может только расти. Следовательно, если \(\Delta>10\), то никакое будущее продолжение уже не сможет создать подстроку суммы \(10\), содержащую позицию \(c\), и такая ветвь невозможна. Отсюда получаем ключевую границу
$$0\le \Delta \le 10.$$
Внутри текущего неразрешённого окна мы поддерживаем множество частичных сумм
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
Эти значения описывают все внутренние разрезы неразрешённого окна. Кроме того, хранится второе множество
$$H\subseteq\{0,1,\dots,10\},$$
элементы которого представляют собой смещения от более ранних префиксных позиций, которые ещё могут стать левыми границами некоторой будущей подстроки суммы \(10\). Если дописать новую цифру \(x\), то неразрешённая сумма станет равной
$$\Delta'=\Delta+x.$$
Если \(\Delta'>10\), переход отбрасывается. Иначе множество частичных сумм расширяется до
$$S'=S\cup\{\Delta'\}.$$
Новый правый конец закрывает всё неразрешённое окно ровно тогда, когда существует дополняющее историческое смещение:
$$10-\Delta' \in H.$$
Тогда найдётся более ранняя префиксная позиция \(u\) такая, что \(P_{c-1}-P_u=10-\Delta'\), а значит
$$P_{j+1}-P_u=10.$$
Следовательно, подстрока от \(u+1\) до \(j+1\) имеет сумму цифр \(10\) и покрывает все позиции от \(c\) до \(j+1\). После такого закрытия неразрешённое окно снова становится пустым, поэтому оконные данные сбрасываются к виду
$$S_{\text{new}}=\{0\}.$$
Исторические смещения относительно новой границы обновляются с помощью сдвига и с помощью всех внутренних разрезов только что закрытого окна:
$$H_{\text{new}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
Поскольку и \(H\), и \(S\) лежат внутри \(\{0,1,\dots,10\}\), возможных состояний лишь конечное число. Каждая дописанная цифра задаёт детерминированный переход. Состояние является принимающим тогда и только тогда, когда неразрешённого окна больше нет; в этой кодировке это означает
$$S=\{0\}.$$
Тем самым подсчёт корректных строк длины \(\ell\) сводится к подсчёту принимающих путей длины \(\ell\) в детерминированном конечном автомате. Для первого шага используется алфавит \(\{1,\dots,9\}\), а для всех следующих — \(\{0,\dots,9\}\).
Пусть \(a_\ell\) — число принимающих путей длины \(\ell\). Динамическое программирование на минимизированном автомате даёт начальные значения \(a_\ell\), а значит и
$$T(n)=\sum_{\ell=1}^{n} a_\ell.$$
Любой фиксированный конечный автомат порождает повторяющееся умножение на одну и ту же матрицу по модулю \(10^9+7\), поэтому накопленная последовательность \(T(0),T(1),T(2),\dots\) удовлетворяет линейной рекуррентности. Реализация вычисляет достаточно много начальных членов, восстанавливает кратчайшую рекуррентность методом Берлекэмпа-Мэсси, а затем находит \(n\)-й член с помощью двоичного возведения полиномов.
Рассмотрим строку \(352\). Её префиксные суммы равны \(0,3,8,10\). Во время чтения неразрешённая сумма проходит значения \(0\), затем \(3\), затем \(8\), затем \(10\), ни разу не выходя за допустимую границу. На последней цифре выполняется \(10-\Delta'=0\), а начальное историческое множество уже содержит \(0\), поэтому вся строка закрывается как один блок с суммой \(10\). Значит, \(352\) корректна.
Для маленькой проверки подсчёта заметим: ни одна строка длины \(1\) не может быть корректной, поэтому \(a_1=0\). Для длины \(2\) единственные корректные строки — это \(19,28,37,46,55,64,73,82,91\), следовательно
$$a_2=9,\qquad T(2)=9.$$
Реализации на C++, Python и Java используют одну и ту же математическую схему. Скомпилированный решатель сначала перечисляет все достижимые состояния автомата, начиная со стартовой конфигурации и многократно применяя описанное выше правило перехода по цифре. После этого он минимизирует исходный автомат методом уточнения разбиения, объединяя эквивалентные состояния без изменения принимаемого языка.
Затем на минимизированном автомате выполняется динамическое программирование. На первом шаге разрешены только цифры от \(1\) до \(9\), а на всех последующих — от \(0\) до \(9\). Сумма количеств в принимающих состояниях даёт \(a_\ell\), а накопленные суммы дают \(T(\ell)\). Если в минимизированном автомате \(s\) состояний, код генерирует \(2s+5\) начальных значений; этого хватает для последующего восстановления используемой рекуррентности.
На финальном этапе метод Берлекэмпа-Мэсси извлекает кратчайшую линейную рекуррентность для накопленной последовательности по модулю \(10^9+7\). Затем решатель вычисляет её в точке \(n\) с помощью редукции полиномов в стиле Китамасы и двоичного возведения. Python-вход лишь делегирует расчёт скомпилированному решателю, поэтому его численные результаты совпадают с результатами компилируемых версий.
Пусть \(s_{\text{raw}}\) — число достижимых исходных состояний, \(s\) — число минимизированных состояний, а \(r\) — порядок восстановленной рекуррентности. Построение достижимого исходного автомата требует \(O(10s_{\text{raw}})\) переходов. Минимизация почти линейна по графу переходов и обычно записывается как \(O(10s_{\text{raw}}\log s_{\text{raw}})\).
Начальная фаза динамического программирования вычисляет \(2s+5\) членов, поэтому занимает \(O(10s(2s+5))=O(s^2)\) времени. После восстановления рекуррентности вычисление для большого индекса стоит
$$O(r^2\log n)$$
времени и \(O(r)\) дополнительной памяти, не считая таблиц автомата.
نعتبر سلسلة عشرية \(d_1d_2\dots d_\ell\) بحيث \(d_1\ne 0\). تكون السلسلة صالحة إذا كان كل موضع فيها ينتمي إلى مقطع متصل واحد على الأقل مجموع أرقامه \(10\). إذا رمزنا بعدد السلاسل الصالحة ذات الطول \(\ell\) بالرمز \(a_\ell\)، فإننا نعرف
$$T(n)=\sum_{\ell=1}^{n} a_\ell \pmod{10^9+7}.$$
القيمة المطلوبة لـ \(n\) ضخمة جداً، لذلك لا يمكن للتنفيذ أن يعد الأطوال واحداً بعد واحد حتى \(n\). الفكرة هي تحويل شرط التغطية إلى أوتوماتا منتهية، ثم استخراج علاقة تكرارية خطية لـ \(T(n)\)، ثم تقييم هذه العلاقة عند فهارس كبيرة جداً.
لنكتب المجاميع البادئة للأرقام على الصورة \(P_0=0\) و\(P_t=d_1+\cdots+d_t\). يكون مجموع المقطع \(d_i\dots d_j\) مساوياً لـ \(10\) إذا وفقط إذا
$$P_j-P_{i-1}=10.$$
تعتمد الطريقة كلها على المرور من اليسار إلى اليمين مع الاحتفاظ فقط بالمعلومات التي قد تبقى مؤثرة على المقاطع المستقبلية ذات المجموع \(10\).
افترض أننا عالجنا الأرقام حتى الموضع \(j\)، ولتكن \(c\) أول موضع لم يثبت بعد أنه مغطى بمقطع مجموعه \(10\). عندئذ تكون النافذة غير المحسومة هي \(d_c\dots d_j\)، ومجموعها الكلي يساوي
$$\Delta=P_j-P_{c-1}.$$
وبما أن جميع الأرقام غير سالبة، فإن \(\Delta\) لا يمكن إلا أن يزداد عندما نضيف أرقاماً جديدة. لذلك إذا أصبح \(\Delta>10\)، فلن يستطيع أي امتداد لاحق تكوين مقطع مجموعه \(10\) ويحتوي الموضع \(c\)، وعندها تصبح هذه الحالة مستحيلة. ومن هنا نحصل على القيد الحاسم
$$0\le \Delta \le 10.$$
داخل النافذة غير المحسومة الحالية نحتفظ بمجموعة المجاميع الجزئية
$$S=\{P_t-P_{c-1}: c-1\le t\le j\}\subseteq\{0,1,\dots,\Delta\}.$$
وهذه القيم تصف جميع نقاط القطع الداخلية داخل النافذة غير المحسومة. كما نحتفظ بمجموعة ثانية
$$H\subseteq\{0,1,\dots,10\},$$
وعناصرها هي إزاحات بالنسبة إلى مواضع بادئة أقدم لا تزال صالحة لأن تكون حدوداً يسارية لمقطع مستقبلي مجموعه \(10\). عند إضافة رقم جديد \(x\)، يصبح مجموع النافذة غير المحسومة
$$\Delta'=\Delta+x.$$
إذا كان \(\Delta'>10\) يُرفض الانتقال مباشرة. وإلا فإن مجموعة المجاميع الجزئية تتسع إلى
$$S'=S\cup\{\Delta'\}.$$
يغلق الطرف الأيمن الجديد النافذة غير المحسومة كلها إذا وفقط إذا وُجدت إزاحة تاريخية متممة:
$$10-\Delta' \in H.$$
وهذا يعني وجود موضع بادئ أقدم \(u\) يحقق \(P_{c-1}-P_u=10-\Delta'\)، وبالتالي
$$P_{j+1}-P_u=10.$$
إذن فالمقطع من \(u+1\) إلى \(j+1\) مجموع أرقامه \(10\)، وهو يغطي كل المواضع من \(c\) حتى \(j+1\). بعد هذا الإغلاق تصبح النافذة غير المحسومة فارغة من جديد، ولذلك تُعاد بيانات النافذة إلى
$$S_{\text{new}}=\{0\}.$$
أما الإزاحات التاريخية بالنسبة إلى الحد الجديد فتُحدَّث بترجمة الإزاحات القديمة وباستخدام جميع نقاط القطع الداخلية في النافذة التي أُغلقت للتو:
$$H_{\text{new}}=\{h+\Delta' : h\in H,\ h+\Delta'\le 10\}\cup\{\Delta'-s : s\in S'\}.$$
لأن كلا من \(H\) و\(S\) يقعان داخل \(\{0,1,\dots,10\}\)، فإن عدد الحالات الممكنة منتهٍ. وكل رقم مضاف يولد انتقالاً حتمياً بين الحالات. وتكون الحالة مقبولة إذا وفقط إذا لم تعد هناك نافذة غير محسومة، وهذا يعني في هذا الترميز أن
$$S=\{0\}.$$
وهكذا يصبح عد السلاسل الصالحة ذات الطول \(\ell\) مساوياً لعد المسارات المقبولة بطول \(\ell\) داخل أوتوماتا منتهية حتمية. في الخطوة الأولى يُستخدم الأبجدية \(\{1,\dots,9\}\)، ثم تُستخدم \(\{0,\dots,9\}\) في جميع الخطوات التالية.
ليكن \(a_\ell\) عدد المسارات المقبولة ذات الطول \(\ell\). إن البرمجة الديناميكية على الأوتوماتا المصغرة تعطي القيم الابتدائية لـ \(a_\ell\)، وبالتالي تعطي أيضاً
$$T(n)=\sum_{\ell=1}^{n} a_\ell.$$
أي أوتوماتا منتهية ثابتة تقابل تكرار ضرب مصفوفة ثابتة modulo \(10^9+7\)، ولذلك فإن المتتالية التراكمية \(T(0),T(1),T(2),\dots\) تحقق علاقة تكرارية خطية. تقوم المنفَّذة بتوليد عدد كافٍ من الحدود الابتدائية، ثم تستخرج أقصر علاقة بواسطة Berlekamp-Massey، ثم تحسب الحد رقم \(n\) باستخدام الرفع الثنائي للمتعددات.
لننظر إلى السلسلة \(352\). مجاميعها البادئة هي \(0,3,8,10\). أثناء القراءة ينتقل مجموع النافذة غير المحسومة من \(0\) إلى \(3\)، ثم إلى \(8\)، ثم إلى \(10\)، من غير أن يتجاوز الحد المسموح. عند الرقم الأخير نحصل على \(10-\Delta'=0\)، والمجموعة التاريخية الابتدائية تحتوي بالفعل على \(0\)، ولذلك تُغلق السلسلة كلها على أنها كتلة واحدة مجموعها \(10\). إذن السلسلة \(352\) صالحة.
وكفحص عددي صغير، لا توجد أي سلسلة بطول \(1\) تكون صالحة، ولذلك \(a_1=0\). أما للطول \(2\)، فالسلاسل الصالحة الوحيدة هي \(19,28,37,46,55,64,73,82,91\)، ومن ثم
$$a_2=9,\qquad T(2)=9.$$
تتبع تطبيقات C++ وPython وJava المسار الرياضي نفسه. يبدأ المحلل المترجَم بتعداد جميع حالات الأوتوماتا الممكن الوصول إليها انطلاقاً من الحالة الابتدائية، وذلك بتطبيق قاعدة الانتقال الخاصة بالأرقام مراراً كما ورد أعلاه. بعد ذلك تُصغَّر الأوتوماتا الخام بواسطة تنقيح التقسيمات حتى تُدمج الحالات المتكافئة من دون تغيير اللغة المقبولة.
ثم تُشغَّل برمجة ديناميكية على الأوتوماتا المصغرة. في الخطوة الأولى تُسمح الأرقام من \(1\) إلى \(9\)، وبعدها تُسمح الأرقام من \(0\) إلى \(9\). مجموع القيم على الحالات المقبولة يعطي \(a_\ell\)، والمجاميع التراكمية تعطي \(T(\ell)\). إذا كان عدد حالات الأوتوماتا المصغرة هو \(s\)، فإن الكود يولد \(2s+5\) قيماً ابتدائية، وهو عدد كافٍ عملياً لمرحلة استرجاع العلاقة التكرارية.
في المرحلة الأخيرة تستخرج Berlekamp-Massey أقصر علاقة تكرارية خطية للمتتالية التراكمية modulo \(10^9+7\). ثم يقيّم المحلل هذه العلاقة عند الفهرس \(n\) باستخدام اختزال متعددات بأسلوب Kitamasa مع رفع ثنائي. أما مدخل Python فيفوّض الحساب إلى المحلل المترجَم، ولذلك يطابق سلوكه العددي سلوك النسخ المترجمة.
لنرمز بـ \(s_{\text{raw}}\) إلى عدد الحالات الخام القابلة للوصول، وبـ \(s\) إلى عدد الحالات بعد التصغير، وبـ \(r\) إلى رتبة العلاقة التكرارية المستخرجة. بناء الأوتوماتا الخام القابلة للوصول يحتاج إلى \(O(10s_{\text{raw}})\) انتقالات. أما التصغير فهو شبه خطي في مخطط الانتقالات، ويُكتب عادة على الصورة \(O(10s_{\text{raw}}\log s_{\text{raw}})\).
تحسب مرحلة البرمجة الديناميكية الابتدائية \(2s+5\) حدود، ولذلك تكلفتها \(O(10s(2s+5))=O(s^2)\) زمناً. وبعد معرفة العلاقة التكرارية تصبح كلفة التقييم عند فهرس كبير
$$O(r^2\log n)$$
زمناً و\(O(r)\) مساحة إضافية، فوق جداول الأوتوماتا نفسها.