For each decimal length \(n\), we consider all \(n\)-digit numbers \(x=d_1d_2\dots d_n\) with \(d_1\neq 0\). Every contiguous substring \(d_i d_{i+1}\dots d_j\) is interpreted as a decimal integer. The number is called a one-child number when exactly one of those substrings is divisible by \(n\). Let \(g(n)\) denote the number of such \(n\)-digit numbers. The required total up to \(10^{19}\) is therefore
$$F(10^{19})=\sum_{n=1}^{19} g(n).$$
Fix a length \(n\). For each position \(k\in\{1,\dots,n\}\), define \(v_{i,k}\) as the decimal value of the substring ending at \(k\):
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$$
Now define, for each remainder \(r\in\{0,1,\dots,n-1\}\),
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$$
This counts how many substrings ending at position \(k\) fall into each residue class modulo \(n\). Since every substring has a unique ending position, the total number of divisible substrings in the whole number is
$$\sum_{k=1}^{n} A_k(0).$$
Therefore the one-child condition is exactly
$$\sum_{k=1}^{n} A_k(0)=1.$$
Suppose we already know the remainder of a substring ending at position \(k\). Appending a new digit \(d\) to its right multiplies the old value by 10 and adds \(d\), so the remainder update is
$$\phi_d(r)=(10r+d)\bmod n.$$
Hence, when we move from position \(k\) to \(k+1\), every old substring ending at \(k\) is extended by the new digit, and there is also one brand-new substring consisting only of that new digit. This gives the recurrence
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r),$$
where \(\mathbf{1}\) is the indicator function. This formula is the heart of the digit DP: it updates all suffix-substring remainders without enumerating substrings explicitly.
The implementation never needs the exact value of \(A_k(r)\) once it exceeds \(1\). For the final decision, every relevant test is of the form “is the number of divisible substrings ending here equal to 0, equal to 1, or at least 2?” Therefore it is safe to replace each exact count by the saturated value
$$c_k(r)=\min(2, A_k(r)).$$
This loses no information, because future transitions only perform additions, and
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b))$$
for all nonnegative integers \(a,b\). So capping at 2 after every update produces exactly the same future saturated states as carrying the full counts and capping later.
With this convention, the transition becomes
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$$
For fixed \(n\), the full saturated remainder profile at position \(k\) is the vector
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$$
Because each component has three possible values, the vector can be packed into one integer using base 3:
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
This gives a compact hash-map key for the DP and avoids storing large nested structures.
Let \(z_k=c_k(0)\), the saturated number of substrings ending at position \(k\) that are divisible by \(n\). Because every divisible substring is counted at the position where it ends, we only need to remember whether the unique successful event has already happened.
The DP therefore uses two layers:
$$L_0:\text{ no divisible substring has appeared yet},\qquad L_1:\text{ exactly one has appeared so far}.$$
After appending a digit and computing the new saturated vector, the transitions are:
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{reject},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{reject},& z_{k+1}\ge 1. \end{cases}$$
So the only accepted terminal states after \(n\) digits are those in layer \(L_1\).
The first digit may be any value in \(\{1,\dots,9\}\). For a one-digit prefix, there is only one substring, namely the digit itself, so the initial saturated vector has a single 1 in residue class \(d\bmod n\) and 0 everywhere else. If that residue is 0, the state starts in layer \(L_1\); otherwise it starts in layer \(L_0\).
For a two-digit number \(ab\), the substrings are \(a\), \(b\), and \(ab\). Divisibility by 2 depends only on the last digit, so:
$$a \equiv 0 \pmod 2 \iff a \text{ is even},$$
$$b \equiv 0 \pmod 2 \iff b \text{ is even},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ is even}.$$
If \(b\) is even, then both \(b\) and \(ab\) are divisible by 2, so the number already has at least two valid substrings. Therefore we must have \(b\) odd. Then \(b\) and \(ab\) are both non-divisible, so the unique divisible substring must be \(a\), which forces \(a\) to be even. Thus
$$g(2)=4\cdot 5=20,$$
because \(a\in\{2,4,6,8\}\) and \(b\in\{1,3,5,7,9\}\). This matches the DP count.
The C++, Python, and Java implementations all realize this same structure. For each length \(n\), they precompute digit-to-remainder transitions \(r\mapsto (10r+d)\bmod n\), store reachable ternary-encoded states in hash maps for the two layers, and extend those states digit by digit. Every transition updates the saturated remainder profile, checks the new zero-remainder count, and keeps only the states that can still lead to exactly one divisible substring overall. Summing the counts in the second layer after \(n\) digits gives \(g(n)\), and summing \(g(1),g(2),\dots,g(19)\) gives the requested total.
Let \(S_n(k)\) be the number of reachable encoded states after \(k\) digits, and let \(S_n=\max_k S_n(k)\). Updating one state for one appended digit touches an \(n\)-component remainder vector, so the total work for fixed \(n\) is
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$$
The memory usage is \(O(S_n)\), since only the current and next DP layers are stored. In practice \(S_n\) is much smaller than the crude upper bound \(3^n\), which is why the method is fast enough for all \(n\le 19\).
Für jede Dezimallänge \(n\) betrachten wir alle \(n\)-stelligen Zahlen \(x=d_1d_2\dots d_n\) mit \(d_1\neq 0\). Jeder zusammenhängende Teilblock \(d_i d_{i+1}\dots d_j\) wird als Dezimalzahl gelesen. Eine Zahl heißt one-child, wenn genau einer dieser Teilblöcke durch \(n\) teilbar ist. Sei \(g(n)\) die Anzahl solcher \(n\)-stelligen Zahlen. Gesucht ist also
$$F(10^{19})=\sum_{n=1}^{19} g(n).$$
Für festes \(n\) sei \(v_{i,k}\) der Wert des Teilstrings, der an Position \(k\) endet:
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$$
Für jeden Rest \(r\in\{0,1,\dots,n-1\}\) definieren wir
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$$
Damit zählt \(A_k(r)\), wie viele Teilstrings mit Endposition \(k\) den Rest \(r\) modulo \(n\) besitzen. Jeder Teilstring hat genau eine Endposition, daher ist die Gesamtzahl der durch \(n\) teilbaren Teilstrings gleich
$$\sum_{k=1}^{n} A_k(0).$$
Die one-child-Bedingung lautet also exakt
$$\sum_{k=1}^{n} A_k(0)=1.$$
Ist der Rest eines Teilstrings bekannt und man hängt rechts eine neue Ziffer \(d\) an, dann wird der alte Wert mit 10 multipliziert und \(d\) addiert. Der neue Rest ist daher
$$\phi_d(r)=(10r+d)\bmod n.$$
Beim Übergang von Position \(k\) zu \(k+1\) werden alle alten Teilstrings verlängert, zusätzlich entsteht der neue einstellige Teilstring aus der Ziffer \(d\). Somit gilt
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r).$$
Diese Rekursion ersetzt die explizite Aufzählung aller Teilstrings durch eine Zustandsdynamik über Restklassen.
Für die Korrektheit reicht es, nur zu unterscheiden, ob eine Anzahl 0, 1 oder mindestens 2 ist. Deshalb ersetzt die Implementierung die exakten Werte durch
$$c_k(r)=\min(2, A_k(r)).$$
Das ist verlustfrei, weil spätere Übergänge nur Summen bilden und anschließend wieder mit 2 abgeschnitten werden. Für nichtnegative ganze Zahlen gilt nämlich
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b)).$$
Daher erhält man genau dieselben zukünftigen gesättigten Zustände, wenn man schon unterwegs kappt. Die Übergangsformel lautet dann
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$$
Das vollständige gesättigte Restprofil an Position \(k\) ist der Vektor
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$$
Da jede Komponente drei mögliche Werte hat, kann man den Vektor als Zahl zur Basis 3 speichern:
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
So entsteht ein kompakter Hash-Schlüssel für den DP-Zustand.
Sei \(z_k=c_k(0)\) die gesättigte Anzahl durch \(n\) teilbarer Teilstrings mit Endposition \(k\). Da jeder gültige Teilstring genau an seiner Endposition gezählt wird, genügt es, zu merken, ob das einzige erlaubte Ereignis bereits verbraucht wurde.
Dafür genügen zwei Ebenen:
$$L_0:\text{ bisher kein teilbarer Teilstring},\qquad L_1:\text{ bisher genau ein teilbarer Teilstring}.$$
Nach dem Anhängen der nächsten Ziffer gelten die Übergänge
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{verwerfen},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{verwerfen},& z_{k+1}\ge 1. \end{cases}$$
Akzeptiert werden am Ende also genau die Zustände der Ebene \(L_1\).
Die erste Ziffer liegt in \(\{1,\dots,9\}\). Für ein Präfix der Länge 1 existiert nur ein Teilstring, nämlich diese Ziffer selbst. Der Anfangszustand enthält daher genau eine 1 in der Restklasse \(d\bmod n\). Ist dieser Rest 0, startet der Zustand in \(L_1\), sonst in \(L_0\).
Für eine zweistellige Zahl \(ab\) sind die Teilstrings \(a\), \(b\) und \(ab\). Teilbarkeit durch 2 hängt nur von der letzten Ziffer ab. Also gilt
$$a \equiv 0 \pmod 2 \iff a \text{ gerade},$$
$$b \equiv 0 \pmod 2 \iff b \text{ gerade},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ gerade}.$$
Ist \(b\) gerade, dann sind sowohl \(b\) als auch \(ab\) durch 2 teilbar, also gibt es schon mindestens zwei Treffer. Folglich muss \(b\) ungerade sein. Dann sind \(b\) und \(ab\) beide nicht teilbar, und der einzige teilbare Teilstring muss \(a\) sein. Also muss \(a\) gerade sein. Damit folgt
$$g(2)=4\cdot 5=20,$$
denn \(a\in\{2,4,6,8\}\) und \(b\in\{1,3,5,7,9\}\). Genau diesen Wert liefert auch das DP.
Die C++-, Python- und Java-Implementierungen setzen genau diese Herleitung um. Für jedes \(n\) werden zunächst die Restübergänge \(r\mapsto (10r+d)\bmod n\) vorab berechnet. Danach verwalten zwei Hash-Maps die erreichbaren ternär kodierten Zustände der Ebenen \(L_0\) und \(L_1\). Bei jeder neuen Ziffer wird das gesättigte Restprofil aktualisiert, die neue Anzahl \(z_k\) für Rest 0 geprüft und nur die weiterhin zulässigen Zustände werden übernommen. Die Summe aller Endzustände in \(L_1\) ist \(g(n)\); die Summe über \(n=1,\dots,19\) ergibt das gesuchte Gesamtergebnis.
Sei \(S_n(k)\) die Anzahl erreichbarer Zustände nach \(k\) Ziffern und \(S_n=\max_k S_n(k)\). Die Aktualisierung eines Zustands für eine neue Ziffer verarbeitet einen Restvektor der Länge \(n\). Daher beträgt die Laufzeit für festes \(n\)
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$$
Der Speicherbedarf ist \(O(S_n)\), weil nur aktuelle und nächste DP-Ebene gehalten werden. In der Praxis ist \(S_n\) deutlich kleiner als die grobe Schranke \(3^n\).
Her \(n\) basamaklı uzunluk için \(x=d_1d_2\dots d_n\) biçimindeki ve \(d_1\neq 0\) olan tüm sayıları ele alıyoruz. Her bitişik alt parça \(d_i d_{i+1}\dots d_j\) onluk sistemde bir tamsayı olarak yorumlanır. Bu alt parçalardan tam olarak biri \(n\)'ye bölünüyorsa sayı bir one-child sayıdır. Böyle \(n\) basamaklı sayıların sayısını \(g(n)\) ile gösterirsek istenen toplam
$$F(10^{19})=\sum_{n=1}^{19} g(n)$$
olur.
Sabit bir \(n\) için, \(k\) konumunda biten alt dizinin değerini
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k$$
olarak tanımlayalım. Her \(r\in\{0,1,\dots,n-1\}\) için
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}$$
olsun. Bu, \(k\) konumunda biten alt dizilerden kaç tanesinin \(n\) modunda \(r\) kalanı verdiğini söyler. Her alt dizi yalnızca kendi bitiş konumunda sayıldığı için, tüm sayıdaki bölünebilir alt dizi sayısı
$$\sum_{k=1}^{n} A_k(0)$$
şeklindedir. Dolayısıyla one-child koşulu tam olarak
$$\sum_{k=1}^{n} A_k(0)=1$$
eşitliğidir.
Bir alt dizinin kalanı biliniyorsa ve sağına yeni bir \(d\) basamağı ekleniyorsa eski değer 10 ile çarpılır ve \(d\) eklenir. Yeni kalan
$$\phi_d(r)=(10r+d)\bmod n$$
olur. Böylece \(k\) konumundan \(k+1\)'e geçerken tüm eski alt diziler uzatılır ve ayrıca yalnızca yeni basamaktan oluşan yeni bir alt dizi doğar. Bu yüzden
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r)$$
bağıntısı elde edilir. Bu formül, alt dizileri tek tek üretmek yerine kalan sınıfları üzerinden ilerleyen bir DP verir.
Karar vermek için bir sayının 0 mı, 1 mi, yoksa en az 2 mi olduğunu bilmek yeterlidir. Bu nedenle tam sayaçlar yerine
$$c_k(r)=\min(2, A_k(r))$$
kullanılır. Bu bilgi kaybı yaratmaz; çünkü sonraki adımlarda yapılan işlem toplama ve ardından yeniden 2'de doyurmadan ibarettir. Gerçekten
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b))$$
her negatif olmayan tamsayı \(a,b\) için geçerlidir. Bu yüzden hesaplamayı her adımda doygun hâle getirsek de gelecekteki doygun durumlar değişmez.
Bu notasyonla geçiş formülü
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right)$$
olur.
\(k\) konumundaki doygun kalan profili
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n$$
vektörüdür. Her bileşenin üç olası değeri olduğundan bu vektör taban 3 ile tek bir sayıya sıkıştırılabilir:
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
Böylece hash tabanlı DP için kompakt bir anahtar elde edilir.
\(z_k=c_k(0)\), yani \(k\) konumunda biten ve \(n\)'ye bölünebilen alt dizilerin doygun sayısı olsun. Her bölünebilir alt dizi yalnızca bittiği konumda sayıldığı için, tek yapmamız gereken benzersiz olayın daha önce kullanılıp kullanılmadığını izlemektir.
Bunun için iki katman yeterlidir:
$$L_0:\text{ henüz hiç bölünebilir alt dizi görülmedi},\qquad L_1:\text{ şimdiye kadar tam bir tane görüldü}.$$
Yeni basamaktan sonra geçişler şöyledir:
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{reddet},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{reddet},& z_{k+1}\ge 1. \end{cases}$$
Sonunda yalnızca \(L_1\) katmanındaki durumlar kabul edilir.
İlk basamak \(\{1,\dots,9\}\) kümesinden gelir. Uzunluğu 1 olan bir önek için yalnızca tek bir alt dizi vardır: o da basamağın kendisidir. Dolayısıyla başlangıç vektöründe \(d\bmod n\) kalan sınıfında 1, diğer tüm sınıflarda 0 bulunur. Bu kalan 0 ise durum \(L_1\)'de, değilse \(L_0\)'da başlar.
İki basamaklı \(ab\) sayısı için alt diziler \(a\), \(b\) ve \(ab\)'dir. 2'ye bölünebilirlik yalnızca son basamağa bağlıdır:
$$a \equiv 0 \pmod 2 \iff a \text{ çifttir},$$
$$b \equiv 0 \pmod 2 \iff b \text{ çifttir},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ çifttir}.$$
Eğer \(b\) çiftse hem \(b\) hem de \(ab\) 2'ye bölünür; yani en az iki uygun alt dizi vardır. O hâlde \(b\) tek olmalıdır. Bu durumda \(b\) ve \(ab\) bölünmez, tek bölünebilir alt dizi ancak \(a\) olabilir; bu da \(a\)'nın çift olmasını zorunlu kılar. Sonuç olarak
$$g(2)=4\cdot 5=20,$$
çünkü \(a\in\{2,4,6,8\}\) ve \(b\in\{1,3,5,7,9\}\). DP de tam olarak bu sayıyı verir.
C++, Python ve Java uygulamaları aynı matematiksel yapıyı izler. Her \(n\) için önce \(r\mapsto (10r+d)\bmod n\) geçiş tablosu hazırlanır. Ardından iki hash tablosu, \(L_0\) ve \(L_1\) katmanlarındaki erişilebilir ternary kodlu durumları tutar. Her yeni basamakta doygun kalan profili güncellenir, yeni sıfır-kalan sayısı kontrol edilir ve yalnızca gelecekte “tam bir kez” koşulunu sağlayabilecek durumlar korunur. \(n\) basamak sonunda \(L_1\)'deki tüm yolların toplamı \(g(n)\)'yi verir; \(g(1)\) ile \(g(19)\) arasındaki toplam da istenen değerdir.
\(S_n(k)\), \(k\) basamaktan sonra ulaşılabilen durum sayısı ve \(S_n=\max_k S_n(k)\) olsun. Tek bir durumun tek basamakla güncellenmesi \(n\) bileşenli bir kalan vektörüne dokunur. Bu nedenle sabit \(n\) için toplam zaman
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n)$$
olur. Bellek kullanımı \(O(S_n)\)'dir; çünkü yalnızca mevcut ve sonraki katman tutulur. Pratikte \(S_n\), kaba üst sınır olan \(3^n\)'den çok daha küçüktür.
Para cada longitud decimal \(n\), consideramos todos los números de \(n\) cifras \(x=d_1d_2\dots d_n\) con \(d_1\neq 0\). Cada subcadena contigua \(d_i d_{i+1}\dots d_j\) se interpreta como un entero decimal. El número se llama one-child si exactamente una de esas subcadenas es divisible por \(n\). Si \(g(n)\) es la cantidad de tales números de \(n\) cifras, el total pedido hasta \(10^{19}\) es
$$F(10^{19})=\sum_{n=1}^{19} g(n).$$
Fijado \(n\), definimos \(v_{i,k}\) como el valor decimal de la subcadena que termina en la posición \(k\):
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$$
Para cada resto \(r\in\{0,1,\dots,n-1\}\), definimos
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$$
Así, \(A_k(r)\) cuenta cuántas subcadenas que terminan en \(k\) pertenecen a la clase residual \(r\) módulo \(n\). Como cada subcadena tiene una única posición final, el número total de subcadenas divisibles por \(n\) es
$$\sum_{k=1}^{n} A_k(0).$$
Por tanto, la condición one-child es exactamente
$$\sum_{k=1}^{n} A_k(0)=1.$$
Si una subcadena tiene resto \(r\) y se le añade a la derecha una nueva cifra \(d\), el valor anterior se multiplica por 10 y luego se suma \(d\). El nuevo resto es
$$\phi_d(r)=(10r+d)\bmod n.$$
Al pasar de la posición \(k\) a \(k+1\), todas las subcadenas anteriores se prolongan y además aparece una nueva subcadena de una sola cifra. Por ello se obtiene
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r).$$
Esta recurrencia permite actualizar todas las subcadenas relevantes mediante sus restos, sin enumerarlas de forma explícita.
Para decidir si una construcción sigue siendo válida solo importa distinguir entre 0, 1 y “al menos 2”. Por eso se reemplazan los recuentos exactos por
$$c_k(r)=\min(2, A_k(r)).$$
Esto no pierde información útil, porque las transiciones futuras solo hacen sumas y luego vuelven a truncar en 2. En efecto, para enteros no negativos \(a,b\) se cumple
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b)).$$
Así, saturar en cada paso produce exactamente los mismos estados saturados futuros que trabajar siempre con las cuentas exactas.
La transición queda entonces
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$$
El perfil saturado completo de restos en la posición \(k\) es
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$$
Como cada componente tiene tres posibilidades, el vector puede codificarse en una sola clave entera usando base 3:
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
Esto permite guardar los estados alcanzables en tablas hash compactas.
Sea \(z_k=c_k(0)\), es decir, el número saturado de subcadenas que terminan en \(k\) y son divisibles por \(n\). Como cada subcadena divisible se cuenta una sola vez, basta recordar si el único éxito permitido ya apareció o no.
La DP usa por tanto dos capas:
$$L_0:\text{ todavía no apareció ninguna subcadena divisible},\qquad L_1:\text{ ya apareció exactamente una}.$$
Después de añadir una cifra nueva, las transiciones son
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{descartar},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{descartar},& z_{k+1}\ge 1. \end{cases}$$
Por lo tanto, al final solo se aceptan los estados que quedan en \(L_1\).
La primera cifra puede ser cualquier valor de \(\{1,\dots,9\}\). Para un prefijo de longitud 1 existe una única subcadena, la propia cifra. El estado inicial tiene entonces un único 1 en la clase residual \(d\bmod n\). Si ese resto es 0, el estado inicial pertenece a \(L_1\); si no, pertenece a \(L_0\).
Para un número de dos cifras \(ab\), las subcadenas son \(a\), \(b\) y \(ab\). La divisibilidad por 2 depende solo de la última cifra, así que
$$a \equiv 0 \pmod 2 \iff a \text{ es par},$$
$$b \equiv 0 \pmod 2 \iff b \text{ es par},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ es par}.$$
Si \(b\) es par, entonces \(b\) y \(ab\) ya son divisibles por 2, de modo que hay al menos dos subcadenas válidas. Así que necesariamente \(b\) debe ser impar. En ese caso ni \(b\) ni \(ab\) son divisibles, y la única subcadena divisible debe ser \(a\), lo que obliga a que \(a\) sea par. En consecuencia
$$g(2)=4\cdot 5=20,$$
porque \(a\in\{2,4,6,8\}\) y \(b\in\{1,3,5,7,9\}\). Ese mismo valor es el que devuelve la DP.
Las implementaciones en C++, Python y Java siguen exactamente esta estructura. Para cada longitud \(n\), primero precalculan la transición \(r\mapsto (10r+d)\bmod n\) para cada cifra. Luego mantienen, en dos tablas hash, los estados alcanzables codificados en base 3 para las capas \(L_0\) y \(L_1\). Cada expansión actualiza el perfil saturado de restos, examina cuántas subcadenas divisibles terminan en la nueva posición y conserva solo los estados compatibles con la condición de tener exactamente una subcadena divisible en total. La suma de los estados finales en \(L_1\) da \(g(n)\), y la suma de \(g(1),\dots,g(19)\) da el resultado buscado.
Sea \(S_n(k)\) el número de estados alcanzables tras \(k\) cifras y \(S_n=\max_k S_n(k)\). Actualizar un estado para una cifra nueva recorre un vector de restos de longitud \(n\). Por tanto, el coste total para un \(n\) fijo es
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$$
La memoria es \(O(S_n)\), ya que solo se almacenan la capa actual y la siguiente. En la práctica, \(S_n\) es mucho menor que la cota grosera \(3^n\).
对每个十进制长度 \(n\)，考虑所有 \(n\) 位数 \(x=d_1d_2\dots d_n\)，其中 \(d_1\neq 0\)。任意连续子串 \(d_i d_{i+1}\dots d_j\) 都按十进制整数解释。如果这些子串中恰好有一个能被 \(n\) 整除，那么这个数就是 one-child 数。记这样的 \(n\) 位数个数为 \(g(n)\)，则要求的总量是
$$F(10^{19})=\sum_{n=1}^{19} g(n).$$
固定长度 \(n\)。定义 \(v_{i,k}\) 为以第 \(k\) 位结束的子串的十进制值：
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$$
对每个余数 \(r\in\{0,1,\dots,n-1\}\)，定义
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$$
它表示所有“结束于位置 \(k\)”的子串中，有多少个在模 \(n\) 意义下余 \(r\)。由于每个子串只有唯一的结束位置，整个数字中能被 \(n\) 整除的子串总数就是
$$\sum_{k=1}^{n} A_k(0).$$
因此 one-child 条件恰好等价于
$$\sum_{k=1}^{n} A_k(0)=1.$$
如果某个子串当前余数为 \(r\)，在右边追加一位数字 \(d\) 后，原值先乘 10 再加 \(d\)，所以新余数为
$$\phi_d(r)=(10r+d)\bmod n.$$
从位置 \(k\) 推到 \(k+1\) 时，所有旧子串都会被新数字延长，同时还会新增一个只包含数字 \(d\) 的长度为 1 的子串。因此有递推式
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r).$$
这就是核心的数字 DP 结构：不直接枚举子串，而是按模 \(n\) 的余数类推进。
对判定而言，我们只需要知道某个数量是 0、1，还是至少 2。因此可以把精确计数替换为饱和值
$$c_k(r)=\min(2, A_k(r)).$$
这样不会丢失有用信息，因为后续转移只涉及求和，然后再次截断到 2。对任意非负整数 \(a,b\) 都有
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b)).$$
所以每一步都做截断，与最后再统一截断得到的未来饱和状态完全一致。
于是转移式可写成
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$$
位置 \(k\) 处完整的饱和余数分布向量为
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$$
由于每个分量只有三种可能，可以把整个向量编码成一个三进制整数：
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
这样就能用紧凑的哈希键来保存 DP 状态。
记 \(z_k=c_k(0)\)，即“结束于位置 \(k\) 且能被 \(n\) 整除”的子串数量的饱和值。因为每个可整除子串只会在它的结束位置被统计一次，所以我们只需要记录那个唯一允许的成功事件是否已经出现。
因此 DP 分成两层：
$$L_0:\text{ 还没有出现可整除子串},\qquad L_1:\text{ 到目前为止恰好出现过一个}.$$
追加新数字后的层间转移为
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{丢弃},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{丢弃},& z_{k+1}\ge 1. \end{cases}$$
因此，最终只统计落在 \(L_1\) 的终止状态。
首位数字只能取 \(\{1,\dots,9\}\)。当当前前缀长度为 1 时，只有一个子串，就是该数字本身。所以初始向量只在余数 \(d\bmod n\) 的位置上有一个 1，其余位置都是 0。若该余数为 0，则初始状态进入 \(L_1\)；否则进入 \(L_0\)。
设两位数为 \(ab\)。它的连续子串为 \(a\)、\(b\)、\(ab\)。能否被 2 整除只取决于末位，因此
$$a \equiv 0 \pmod 2 \iff a \text{ 是偶数},$$
$$b \equiv 0 \pmod 2 \iff b \text{ 是偶数},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ 是偶数}.$$
如果 \(b\) 是偶数，那么 \(b\) 和 \(ab\) 都会被 2 整除，于是至少已经有两个满足条件的子串。因此必须让 \(b\) 为奇数。此时 \(b\) 与 \(ab\) 都不整除，唯一可整除的子串只能是 \(a\)，所以 \(a\) 必须是偶数。于是
$$g(2)=4\cdot 5=20,$$
因为 \(a\in\{2,4,6,8\}\)，\(b\in\{1,3,5,7,9\}\)。这与 DP 计算结果完全一致。
C++、Python 和 Java 实现遵循完全相同的数学思路。对每个长度 \(n\)，先预计算所有数字的余数转移 \(r\mapsto (10r+d)\bmod n\)。然后用两张哈希表分别保存层 \(L_0\) 与层 \(L_1\) 中所有可达的三进制编码状态。每次扩展一位数字时，程序都会更新饱和余数向量，检查新的零余数计数，并丢弃不可能再满足“总共恰好一次”的状态。长度达到 \(n\) 后，层 \(L_1\) 中所有方案数之和就是 \(g(n)\)；再把 \(g(1)\) 到 \(g(19)\) 相加即可得到最终总量。
记 \(S_n(k)\) 为处理到第 \(k\) 位后可达状态数，\(S_n=\max_k S_n(k)\)。对一个状态追加一位数字时，需要处理长度为 \(n\) 的余数向量，所以固定 \(n\) 的总时间复杂度为
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$$
空间复杂度为 \(O(S_n)\)，因为程序只保留当前层和下一层。在实际运行中，可达状态数远小于粗略上界 \(3^n\)。
Для каждой десятичной длины \(n\) рассматриваются все \(n\)-значные числа \(x=d_1d_2\dots d_n\) с условием \(d_1\neq 0\). Любая непрерывная подстрока \(d_i d_{i+1}\dots d_j\) понимается как десятичное целое число. Число называется one-child, если ровно одна из таких подстрок делится на \(n\). Обозначим через \(g(n)\) число таких \(n\)-значных чисел. Тогда искомая сумма до \(10^{19}\) равна
$$F(10^{19})=\sum_{n=1}^{19} g(n).$$
Зафиксируем \(n\). Пусть \(v_{i,k}\) обозначает значение подстроки, оканчивающейся в позиции \(k\):
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$$
Для каждого остатка \(r\in\{0,1,\dots,n-1\}\) определим
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$$
То есть \(A_k(r)\) считает, сколько подстрок, оканчивающихся в позиции \(k\), дают остаток \(r\) по модулю \(n\). Поскольку у каждой подстроки есть единственная конечная позиция, общее число подстрок, делящихся на \(n\), равно
$$\sum_{k=1}^{n} A_k(0).$$
Следовательно, условие one-child эквивалентно равенству
$$\sum_{k=1}^{n} A_k(0)=1.$$
Если известен остаток \(r\) некоторой подстроки и справа дописывается новая цифра \(d\), старое значение умножается на 10 и увеличивается на \(d\). Новый остаток равен
$$\phi_d(r)=(10r+d)\bmod n.$$
При переходе от позиции \(k\) к \(k+1\) каждая старая подстрока удлиняется, а также появляется новая одноцифровая подстрока. Поэтому
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r).$$
Эта формула позволяет обновлять все нужные подстроки через распределение по остаткам, не перебирая их явно.
Для проверки условия достаточно различать случаи 0, 1 и «не меньше 2». Поэтому точные значения заменяются насыщенными:
$$c_k(r)=\min(2, A_k(r)).$$
Полезная информация при этом не теряется, потому что дальнейшие переходы состоят только из сложения и последующего усечения до 2. Для любых неотрицательных целых \(a,b\) выполняется
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b)).$$
Значит, можно насыщать уже на каждом шаге и получать в точности те же будущие насыщенные состояния, что и при работе с точными счётчиками.
Переход принимает вид
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$$
Полный насыщенный профиль остатков в позиции \(k\) есть вектор
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$$
Поскольку каждая компонента имеет три возможных значения, весь вектор можно упаковать в одно целое число в системе счисления по основанию 3:
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
Так получается компактный ключ для хеш-таблицы состояний.
Пусть \(z_k=c_k(0)\) — насыщенное число подстрок, оканчивающихся в позиции \(k\) и делящихся на \(n\). Поскольку каждая делящаяся подстрока учитывается только в своей конечной позиции, нужно помнить лишь одно: произошло ли уже единственное допустимое событие.
Для этого достаточно двух слоёв DP:
$$L_0:\text{ пока не встретилось ни одной делящейся подстроки},\qquad L_1:\text{ к текущему моменту встретилась ровно одна}.$$
После добавления новой цифры переходы таковы:
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \text{отбросить},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \text{отбросить},& z_{k+1}\ge 1. \end{cases}$$
Следовательно, в конце учитываются только терминальные состояния из слоя \(L_1\).
Первая цифра выбирается из \(\{1,\dots,9\}\). Для префикса длины 1 существует ровно одна подстрока — сама эта цифра. Значит, начальный вектор имеет единственную единицу в классе остатка \(d\bmod n\) и нули в остальных местах. Если этот остаток равен 0, стартовое состояние попадает в \(L_1\), иначе в \(L_0\).
Пусть число имеет вид \(ab\). Его подстроки: \(a\), \(b\) и \(ab\). Делимость на 2 зависит только от последней цифры, поэтому
$$a \equiv 0 \pmod 2 \iff a \text{ чётно},$$
$$b \equiv 0 \pmod 2 \iff b \text{ чётно},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ чётно}.$$
Если \(b\) чётно, то и \(b\), и \(ab\) делятся на 2, то есть подходящих подстрок уже как минимум две. Значит, \(b\) должно быть нечётным. Тогда ни \(b\), ни \(ab\) не делятся на 2, и единственной делящейся подстрокой может быть только \(a\), что требует чётности \(a\). Поэтому
$$g(2)=4\cdot 5=20,$$
так как \(a\in\{2,4,6,8\}\), а \(b\in\{1,3,5,7,9\}\). Именно такой результат даёт DP.
Реализации на C++, Python и Java используют одну и ту же схему. Для каждого \(n\) заранее строятся переходы остатков \(r\mapsto (10r+d)\bmod n\). Затем две хеш-таблицы хранят достижимые состояния в слоях \(L_0\) и \(L_1\), причём само состояние кодируется как тернарное число. При добавлении новой цифры пересчитывается насыщенный профиль остатков, проверяется новое значение для остатка 0 и сохраняются только те состояния, которые ещё совместимы с условием «ровно одна делящаяся подстрока во всём числе». Сумма финальных состояний в слое \(L_1\) даёт \(g(n)\), а суммирование по \(n=1,\dots,19\) даёт общий ответ.
Пусть \(S_n(k)\) — число достижимых состояний после \(k\) цифр, а \(S_n=\max_k S_n(k)\). Обновление одного состояния для одной новой цифры проходит по вектору остатков длины \(n\). Поэтому для фиксированного \(n\) полная трудоёмкость равна
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$$
Память составляет \(O(S_n)\), потому что хранятся только текущий и следующий слои DP. На практике \(S_n\) существенно меньше грубой оценки \(3^n\).
لكل طول عشري \(n\)، ننظر إلى جميع الأعداد ذات \(n\) خانات من الشكل \(x=d_1d_2\dots d_n\) مع الشرط \(d_1\neq 0\). وكل مقطع متجاور \(d_i d_{i+1}\dots d_j\) يُقرأ كعدد عشري. يسمى العدد من نوع one-child إذا كان هناك مقطع واحد فقط من هذه المقاطع يقبل القسمة على \(n\). إذا رمزنا بعدد هذه الأعداد ذات \(n\) خانات بالرمز \(g(n)\)، فإن المطلوب حتى \(10^{19}\) هو
$$F(10^{19})=\sum_{n=1}^{19} g(n).$$
ثبّت \(n\). ولْيكن \(v_{i,k}\) هو القيمة العشرية للمقطع الذي ينتهي عند الموضع \(k\):
$$v_{i,k}=d_i d_{i+1}\dots d_k,\qquad 1\le i\le k.$$
ولكل باقٍ \(r\in\{0,1,\dots,n-1\}\) نعرّف
$$A_k(r)=\#\{\,i\in\{1,\dots,k\}: v_{i,k}\equiv r \pmod n\,\}.$$
أي أن \(A_k(r)\) يحصي عدد المقاطع المنتهية عند الموضع \(k\) والتي تعطي الباقي \(r\) modulo \(n\). وبما أن لكل مقطع موضع نهاية وحيدًا، فإن العدد الكلي للمقاطع القابلة للقسمة على \(n\) داخل العدد كله هو
$$\sum_{k=1}^{n} A_k(0).$$
ومن ثم فإن شرط one-child يكافئ تمامًا
$$\sum_{k=1}^{n} A_k(0)=1.$$
إذا كان باقِي مقطع ما هو \(r\) ثم ألحقنا به يمينًا خانة جديدة \(d\)، فإن القيمة القديمة تُضرب في 10 ثم يضاف إليها \(d\). لذلك يصبح الباقي الجديد
$$\phi_d(r)=(10r+d)\bmod n.$$
وعند الانتقال من الموضع \(k\) إلى \(k+1\)، تتم إطالة جميع المقاطع القديمة، كما يظهر مقطع جديد مكوّن من الخانة \(d\) وحدها. لذا نحصل على العلاقة
$$A_{k+1}(t)=\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} A_k(r).$$
وهذه هي الفكرة الأساسية في الـ DP: تحديث جميع المقاطع ذات الصلة عبر فئات البواقي بدلًا من تعداد المقاطع صراحة.
من أجل القرار النهائي لا يهمنا العدد الدقيق إذا تجاوز 1؛ المهم فقط التمييز بين 0 و1 و«2 فأكثر». لذلك نستبدل العدّ الدقيق بـ
$$c_k(r)=\min(2, A_k(r)).$$
وهذا لا يفقد أي معلومة مؤثرة، لأن الانتقالات اللاحقة لا تستخدم إلا الجمع ثم القطع مرة أخرى عند 2. وبالفعل، لكل عددين صحيحين غير سالبين \(a,b\) لدينا
$$\min(2, a+b)=\min(2,\min(2,a)+\min(2,b)).$$
إذن يمكن تشبيع القيم في كل خطوة من دون أن يتغير أي وضع مشبع مستقبلي.
وبهذا تصبح صيغة الانتقال
$$c_{k+1}(t)=\min\left(2,\mathbf{1}_{\,t\equiv d \,(\bmod n)}+\sum_{\substack{0\le r\lt n\\ \phi_d(r)=t}} c_k(r)\right).$$
متجه البواقي المشبع الكامل عند الموضع \(k\) هو
$$C_k=(c_k(0),c_k(1),\dots,c_k(n-1))\in\{0,1,2\}^n.$$
وبما أن كل مركبة لها ثلاث حالات ممكنة، يمكن ضغط المتجه في عدد صحيح واحد باستخدام الأساس 3:
$$\operatorname{key}(C_k)=\sum_{r=0}^{n-1} c_k(r)\,3^r.$$
وهكذا نحصل على مفتاح مضغوط مناسب لتخزين الحالات في جداول hash.
لنكتب \(z_k=c_k(0)\)، أي العدد المشبع للمقاطع المنتهية عند الموضع \(k\) والقابلة للقسمة على \(n\). وبما أن كل مقطع مقبول يُحصى عند موضع نهايته فقط، فيكفي أن نعرف هل استُهلك الحدث الوحيد المسموح به من قبل أم لا.
لهذا تستخدم الـ DP طبقتين فقط. الطبقة \(L_0\) تعني أنه لم يظهر أي مقطع قابل للقسمة بعد، والطبقة \(L_1\) تعني أن مقطعًا واحدًا فقط ظهر حتى الآن.
وبعد إضافة خانة جديدة تكون الانتقالات
$$L_0 \to \begin{cases} L_0,& z_{k+1}=0,\\ L_1,& z_{k+1}=1,\\ \mathrm{reject},& z_{k+1}=2, \end{cases}$$
$$L_1 \to \begin{cases} L_1,& z_{k+1}=0,\\ \mathrm{reject},& z_{k+1}\ge 1. \end{cases}$$
إذًا لا تُقبل في النهاية إلا الحالات الموجودة في الطبقة \(L_1\).
الخانة الأولى تؤخذ من \(\{1,\dots,9\}\). وعند طول بادئة يساوي 1 يوجد مقطع واحد فقط، وهو هذه الخانة نفسها. لذلك تكون الحالة الابتدائية ذات قيمة 1 واحدة في فئة الباقي \(d\bmod n\) وصفر في بقية الفئات. إذا كان هذا الباقي يساوي 0 تبدأ الحالة في \(L_1\)، وإلا فتبدأ في \(L_0\).
إذا كان العدد ذو خانتين هو \(ab\)، فالمقاطع المتجاورة هي \(a\) و\(b\) و\(ab\). القابلية للقسمة على 2 تعتمد فقط على الخانة الأخيرة، ولذلك
$$a \equiv 0 \pmod 2 \iff a \text{ is even},$$
$$b \equiv 0 \pmod 2 \iff b \text{ is even},$$
$$ab \equiv 0 \pmod 2 \iff b \text{ is even}.$$
إذا كانت \(b\) زوجية، فإن كلا من \(b\) و\(ab\) يقبل القسمة على 2، أي يوجد على الأقل مقطعان صالحان. لذلك يجب أن تكون \(b\) فردية. عندئذ لا يكون \(b\) ولا \(ab\) قابلين للقسمة على 2، فيبقى أن المقطع الوحيد القابل للقسمة هو \(a\)، وهذا يفرض أن تكون \(a\) زوجية. ومن ثم
$$g(2)=4\cdot 5=20,$$
لأن \(a\in\{2,4,6,8\}\) و\(b\in\{1,3,5,7,9\}\). وهذا يطابق تمامًا ناتج الـ DP.
التنفيذات في C++ وPython وJava تتبع البنية نفسها. لكل طول \(n\)، يتم أولًا تجهيز انتقالات البواقي \(r\mapsto (10r+d)\bmod n\) لجميع الخانات. ثم تُخزَّن الحالات المرمّزة ثلاثيًا والقابلة للوصول في جدولَي hash يمثلان الطبقتين \(L_0\) و\(L_1\). وعند كل توسعة بخانة جديدة يُحدَّث متجه البواقي المشبع، ويُفحَص عدّاد الباقي صفر، وتُستبعد أي حالة لم تعد منسجمة مع شرط وجود مقطع واحد فقط قابل للقسمة على \(n\) في العدد كله. مجموع الحالات النهائية في \(L_1\) يعطي \(g(n)\)، ثم يؤدي جمع \(g(1),g(2),\dots,g(19)\) إلى الناتج المطلوب.
إذا رمزنا بـ \(S_n(k)\) إلى عدد الحالات الممكنة بعد معالجة \(k\) خانات، وبـ \(S_n=\max_k S_n(k)\)، فإن تحديث حالة واحدة عند إضافة خانة جديدة يمر على متجه بواقي طوله \(n\). لذلك فإن الزمن الكلي لطول ثابت \(n\) هو
$$O\left(10n\sum_{k=1}^{n-1} S_n(k)\right)\subseteq O(10n^2 S_n).$$
أما الذاكرة فهي \(O(S_n)\)، لأن التنفيذ يحتفظ فقط بالطبقة الحالية والطبقة التالية. وعمليًا يكون \(S_n\) أصغر بكثير من الحد التقريبي الخشن \(3^n\).