For a \(d\)-digit decimal number \(a_1a_2\dots a_d\) with \(a_1\ne 0\), consider every contiguous substring. A substring is divisible by \(3\) exactly when the sum of its digits is divisible by \(3\). The task is to count those \(d\)-digit numbers for which the total number of divisible substrings is itself a multiple of \(3\), and to return that count modulo \(10^9+7\).
The crucial observation is that divisibility by \(3\) depends only on prefix sums modulo \(3\). Once that is written down carefully, the whole search collapses to a tiny finite-state dynamic program with only \(243\) states.
Let the digits be \(a_1,\dots,a_d\), and define prefix sums modulo \(3\) by
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d).$$
Because \(10\equiv 1\pmod 3\), a decimal substring \(a_{l+1}\dots a_r\) is congruent modulo \(3\) to the sum of its digits. Therefore
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3,$$
so this substring is divisible by \(3\) if and only if
$$S_r\equiv S_l\pmod 3.$$
Thus every divisible substring corresponds exactly to a pair of equal prefix residues.
After processing the first \(k\) digits, let \(C_i(k)\) denote how many prefix indices \(j\in\{0,\dots,k\}\) satisfy \(S_j=i\). Then the total number of divisible substrings among the first \(k\) digits is
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}.$$
The implementations do not recompute this from scratch. If the next prefix residue is \(r=S_k\), then every earlier prefix with residue \(r\) creates one new divisible substring ending at position \(k\). Hence
$$T_k=T_{k-1}+C_r(k-1),$$
and after recording the new prefix we have
$$C_r(k)=C_r(k-1)+1.$$
This online update is the key recurrence.
The final acceptance condition is \(T_d\equiv 0\pmod 3\), so during the dynamic program we only care about \(T_k\bmod 3\). But the update adds \(C_r(k-1)\), which means only \(C_r(k-1)\bmod 3\) matters as well. Therefore the exact counts are unnecessary; each of the three prefix counters can be reduced modulo \(3\) without losing any information relevant to the final test.
So a state is fully described by
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
Each component has \(3\) possible values, so the total number of states is
$$3^5=243.$$
Suppose the next digit belongs to residue class \(c\in\{0,1,2\}\) modulo \(3\). If the current state is
$$\bigl(s,a_0,a_1,a_2,t\bigr),$$
then the next prefix residue is
$$s'=(s+c)\bmod 3.$$
The number of new divisible substrings contributed at this step is the current number of earlier prefixes with residue \(s'\), namely \(a_{s'}\) modulo \(3\). Therefore
$$t'=(t+a_{s'})\bmod 3.$$
Finally the newly created prefix must itself be counted, so
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
while the other two counters stay unchanged. For each state and each residue class \(c\), the transition is therefore deterministic.
The dynamic program groups digits by their residue modulo \(3\).
For the first position, the allowed digits are \(1,\dots,9\), and the three residue classes occur equally often:
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
So the first-digit multiplicities are
$$(3,3,3).$$
After the first position, the available digits are \(0,\dots,9\). Their residue counts are
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\},$$
so later positions use multiplicities
$$(4,3,3).$$
This is why the same transition graph is reused at every step, but with a different weight vector at position \(1\).
Before any digit is read, only the empty prefix exists, so
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0.$$
Hence the starting state is
$$\bigl(0,1,0,0,0\bigr).$$
After all \(d\) digits have been processed, a number is valid exactly when
$$T_d\equiv 0\pmod 3.$$
Worked example for \(d=2\). A two-digit number has three substrings: \(a\), \(b\), and \(ab\). Let \(x\equiv a\pmod 3\) and \(y\equiv b\pmod 3\). These substrings are divisible by \(3\) precisely under the conditions
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3.$$
For the total count to be divisible by \(3\), it must be either \(0\) or \(3\). The value \(3\) occurs only for \((x,y)=(0,0)\), giving \(3\cdot 4=12\) numbers. The value \(0\) occurs for \((x,y)=(1,1)\) and \((2,2)\), giving \(3\cdot 3+3\cdot 3=18\) numbers. Therefore
$$12+18=30,$$
which matches the small checkpoint used by the implementations.
The C++, Python, and Java implementations first enumerate all \(243\) states and precompute, for each state and each residue class \(0,1,2\), which state comes next. That turns the main loop into table lookups and additions.
They then run a standard layered dynamic program over the digit positions. At position \(1\), each residue-class transition is weighted by \((3,3,3)\) because the first digit cannot be zero. At every later position, the same transitions are reused with weights \((4,3,3)\). After \(d\) steps, the answer is the sum of all state counts whose substring-total component is \(0\) modulo \(3\).
The number of states is fixed at \(243\), and each position performs \(3\) weighted transitions from each active state. Thus the total running time is
$$O(d\cdot 243\cdot 3)=O(d),$$
with a small constant factor. The memory usage is \(O(243)\), because only the current and next DP layers are stored.
Für eine \(d\)-stellige Dezimalzahl \(a_1a_2\dots a_d\) mit \(a_1\ne 0\) betrachten wir alle zusammenhängenden Teilstrings. Ein Teilstring ist genau dann durch \(3\) teilbar, wenn seine Quersumme durch \(3\) teilbar ist. Gesucht ist die Anzahl der \(d\)-stelligen Zahlen, bei denen die Gesamtzahl dieser durch \(3\) teilbaren Teilstrings selbst ein Vielfaches von \(3\) ist. Das Ergebnis soll modulo \(10^9+7\) ausgegeben werden.
Die entscheidende Beobachtung ist, dass Teilbarkeit durch \(3\) nur von Präfixsummen modulo \(3\) abhängt. Dadurch wird aus einem scheinbar quadratischen Teilstring-Problem ein sehr kleiner dynamischer Automat mit nur \(243\) Zuständen.
Seien \(a_1,\dots,a_d\) die Ziffern und
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d).$$
Da \(10\equiv 1\pmod 3\) gilt, ist ein Dezimal-Teilstring \(a_{l+1}\dots a_r\) modulo \(3\) zur Summe seiner Ziffern kongruent. Also
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3,$$
und damit ist der Teilstring genau dann durch \(3\) teilbar, wenn
$$S_r\equiv S_l\pmod 3.$$
Jeder gültige Teilstring entspricht also genau einem Paar gleicher Präfixreste.
Nach den ersten \(k\) Ziffern sei \(C_i(k)\) die Anzahl der Präfixindizes \(j\in\{0,\dots,k\}\) mit \(S_j=i\). Dann ist die Gesamtzahl der durch \(3\) teilbaren Teilstrings in den ersten \(k\) Ziffern
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}.$$
Die Implementierungen berechnen das aber nicht jedes Mal neu. Wenn der nächste Präfixrest \(r=S_k\) ist, dann erzeugt jeder frühere Präfixrest mit demselben Wert genau einen neuen gültigen Teilstring, der an Position \(k\) endet. Daher
$$T_k=T_{k-1}+C_r(k-1),$$
und anschließend wird der neue Präfixrest mitgezählt:
$$C_r(k)=C_r(k-1)+1.$$
Diese Online-Rekurrenz treibt die gesamte Lösung.
Am Ende interessiert nur, ob \(T_d\equiv 0\pmod 3\) gilt. Während der Berechnung reicht also \(T_k\bmod 3\). Da in der Rekurrenz nur \(C_r(k-1)\) addiert wird, genügt auch \(C_r(k-1)\bmod 3\). Die exakten Größen der Zähler sind für die Endbedingung nicht notwendig; jede der drei Präfixhäufigkeiten kann sofort modulo \(3\) reduziert werden.
Ein Zustand ist damit vollständig beschrieben durch
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
Jede Komponente hat \(3\) Möglichkeiten, also gibt es insgesamt
$$3^5=243$$
Zustände.
Angenommen, die nächste Ziffer liegt in der Restklasse \(c\in\{0,1,2\}\) modulo \(3\). Ist der aktuelle Zustand
$$\bigl(s,a_0,a_1,a_2,t\bigr),$$
dann ist der neue Präfixrest
$$s'=(s+c)\bmod 3.$$
Die Zahl der neu entstehenden gültigen Teilstrings ist die aktuelle Anzahl früherer Präfixe mit Rest \(s'\), also \(a_{s'}\) modulo \(3\). Folglich
$$t'=(t+a_{s'})\bmod 3.$$
Danach muss das neu entstandene Präfix selbst verbucht werden, also
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
während die anderen beiden Zähler unverändert bleiben. Für jeden Zustand und jede Restklasse ist der Übergang damit eindeutig bestimmt.
Das dynamische Programm arbeitet nicht mit zehn einzelnen Ziffern, sondern mit ihren Restklassen modulo \(3\).
In der ersten Position sind nur \(1,\dots,9\) erlaubt, und jede der drei Restklassen kommt genau dreimal vor:
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
Daher lauten die Multiplikitäten für die erste Ziffer
$$(3,3,3).$$
Danach sind die Ziffern \(0,\dots,9\) erlaubt. Die Restklassen haben dann die Häufigkeiten
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\},$$
also
$$(4,3,3).$$
Darum wird in jedem Schritt derselbe Übergangsgraph benutzt, nur mit einem anderen Gewichtsvektor an Position \(1\).
Vor dem Lesen irgendeiner Ziffer existiert nur das leere Präfix. Also gilt
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0.$$
Der Startzustand ist daher
$$\bigl(0,1,0,0,0\bigr).$$
Nach \(d\) Schritten ist eine Zahl genau dann gültig, wenn
$$T_d\equiv 0\pmod 3.$$
Durchgerechnetes Beispiel für \(d=2\). Eine zweistellige Zahl besitzt die drei Teilstrings \(a\), \(b\) und \(ab\). Sei \(x\equiv a\pmod 3\) und \(y\equiv b\pmod 3\). Dann sind diese Teilstrings genau unter den Bedingungen
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3$$
durch \(3\) teilbar. Damit die Gesamtzahl durch \(3\) teilbar ist, muss sie \(0\) oder \(3\) sein. Der Wert \(3\) tritt nur bei \((x,y)=(0,0)\) auf und liefert \(3\cdot 4=12\) Zahlen. Der Wert \(0\) tritt bei \((x,y)=(1,1)\) und \((2,2)\) auf und liefert \(3\cdot 3+3\cdot 3=18\) Zahlen. Also
$$12+18=30,$$
genau der kleine Kontrollwert der Implementierungen.
Die C++-, Python- und Java-Implementierungen enumerieren zunächst alle \(243\) Zustände und berechnen für jeden Zustand und jede Restklasse \(0,1,2\) den Folgezustand vor. Dadurch besteht die Hauptschleife nur noch aus Tabellenzugriffen und Additionen.
An Position \(1\) werden die Übergänge mit \((3,3,3)\) gewichtet, weil die erste Ziffer nicht null sein darf. An allen späteren Positionen werden dieselben Übergänge mit \((4,3,3)\) wiederverwendet. Nach \(d\) Schritten wird über genau die Zustände summiert, deren Teilstring-Zählerkomponente \(0\) modulo \(3\) ist.
Die Zahl der Zustände ist konstant \(243\), und pro Position gibt es \(3\) gewichtete Übergänge je aktivem Zustand. Damit beträgt die Laufzeit insgesamt
$$O(d\cdot 243\cdot 3)=O(d),$$
mit kleinem konstantem Faktor. Der Speicherbedarf ist \(O(243)\), weil nur die aktuelle und die nächste DP-Schicht benötigt werden.
İlk basamağı sıfır olmayan \(a_1a_2\dots a_d\) biçimindeki \(d\) basamaklı bir onluk sayı için tüm ardışık alt dizileri inceliyoruz. Bir alt dizi ancak ve ancak rakamları toplamı \(3\)'e bölünüyorsa \(3\)'e bölünür. İstenen şey, \(3\)'e bölünebilen alt dizi sayısının kendisi de \(3\)'ün katı olan tüm \(d\) basamaklı sayıların sayısını bulmak ve sonucu \(10^9+7\) modunda vermektir.
Kritik gözlem, \(3\)'e bölünebilirliğin yalnızca önek toplamlarının \(3\)'e göre kalıntılarına bağlı olmasıdır. Bu gözlem problemdeki devasa aramayı sadece \(243\) durumlu küçük bir sonlu durum dinamik programına indirger.
Rakamlar \(a_1,\dots,a_d\) olsun. \(3\)'e göre önek toplamlarını
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d)$$
şeklinde tanımlayalım. \(10\equiv 1\pmod 3\) olduğundan, bir onluk alt dizi \(a_{l+1}\dots a_r\) mod \(3\) bakımından rakamları toplamına denktir. Dolayısıyla
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3,$$
ve bu alt dizi tam olarak
$$S_r\equiv S_l\pmod 3$$
olduğunda \(3\)'e bölünür. Yani her uygun alt dizi, aynı kalıntıya sahip iki önek seçimine karşılık gelir.
İlk \(k\) rakam işlendiğinde \(C_i(k)\), \(S_j=i\) olan \(j\in\{0,\dots,k\}\) öneklerinin sayısı olsun. O zaman ilk \(k\) rakam içindeki \(3\)'e bölünebilen alt dizi sayısı
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}$$
olur. Fakat uygulama bunu her adımda baştan hesaplamaz. Yeni önek kalıntısı \(r=S_k\) olduğunda, daha önce \(r\) kalıntısıyla görülen her önek konumu, \(k\)'de biten yeni bir uygun alt dizi üretir. Bu yüzden
$$T_k=T_{k-1}+C_r(k-1),$$
ve yeni öneği ekledikten sonra
$$C_r(k)=C_r(k-1)+1$$
olur. Çözümün temel yinelemesi budur.
Son kabul koşulu \(T_d\equiv 0\pmod 3\) olduğundan, hesap boyunca yalnızca \(T_k\bmod 3\) önemlidir. Güncellemede eklenen değer \(C_r(k-1)\) olduğu için \(C_r(k-1)\bmod 3\) bilgisi de yeterlidir. Bu nedenle önek sayılarının tam değerlerini tutmaya gerek yoktur; üç sayacın her biri doğrudan mod \(3\) tutulabilir.
Demek ki bir durum şu \(5\)-li ile tamamen belirlenir:
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
Her bileşen için \(3\) olasılık vardır; toplam durum sayısı
$$3^5=243$$
olur.
Sıradaki rakamın \(3\)'e göre kalıntı sınıfı \(c\in\{0,1,2\}\) olsun. Mevcut durum
$$\bigl(s,a_0,a_1,a_2,t\bigr)$$
ise yeni önek kalıntısı
$$s'=(s+c)\bmod 3$$
olur. Bu adımda eklenen yeni uygun alt dizi sayısı, daha önce \(s'\) kalıntısıyla görülen önek sayısıdır; yani mod \(3\) bakımından \(a_{s'}\). Dolayısıyla
$$t'=(t+a_{s'})\bmod 3.$$
Ardından yeni oluşan öneğin kendisi de sayılmalıdır; bu yüzden
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
öteki iki sayaç ise değişmeden kalır. Böylece her durum ve her kalıntı sınıfı için geçiş deterministiktir.
Dinamik program on rakamın tamamını ayrı ayrı dolaşmaz; rakamları \(3\)'e göre kalıntı sınıflarına ayırır.
İlk basamakta yalnızca \(1,\dots,9\) kullanılabilir ve üç kalıntı sınıfının her biri tam \(3\) kez görünür:
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
Bu nedenle ilk basamak için çokluk vektörü
$$(3,3,3)$$
olur. Sonraki basamaklarda \(0,\dots,9\) kullanılabildiği için sınıf çoklukları
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}$$
ve dolayısıyla
$$(4,3,3)$$
şeklindedir. Aynı geçiş grafiği her adımda kullanılır; sadece ilk adımın ağırlıkları farklıdır.
Henüz hiçbir rakam okunmamışken yalnızca boş önek vardır. Bu yüzden
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0$$
olur. Başlangıç durumu da
$$\bigl(0,1,0,0,0\bigr)$$
şeklindedir. \(d\) rakam tamamlandıktan sonra bir sayı tam olarak
$$T_d\equiv 0\pmod 3$$
ise geçerlidir.
\(d=2\) için örnek. İki basamaklı bir sayının üç alt dizisi vardır: \(a\), \(b\) ve \(ab\). \(x\equiv a\pmod 3\), \(y\equiv b\pmod 3\) olsun. Bu alt diziler sırasıyla
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3$$
olduğunda \(3\)'e bölünür. Toplam sayının \(3\)'ün katı olması için değer \(0\) ya da \(3\) olmalıdır. \(3\) değeri yalnızca \((x,y)=(0,0)\) için gelir ve \(3\cdot 4=12\) sayı üretir. \(0\) değeri \((x,y)=(1,1)\) ve \((2,2)\) için gelir; bunlar da \(3\cdot 3+3\cdot 3=18\) sayı verir. Sonuç olarak
$$12+18=30,$$
ki bu da uygulamalardaki küçük kontrol değeriyle aynıdır.
C++, Python ve Java uygulamaları önce tüm \(243\) durumu listeler ve her durum ile her kalıntı sınıfı \(0,1,2\) için hangi yeni duruma gidileceğini önceden hesaplar. Böylece ana döngü yalnızca tablo erişimleri ve toplamalardan oluşur.
Birinci basamakta geçişler \((3,3,3)\) ile ağırlıklandırılır; çünkü ilk rakam sıfır olamaz. Sonraki tüm basamaklarda aynı geçişler \((4,3,3)\) ağırlıklarıyla tekrar kullanılır. \(d\) adım sonunda, alt dizi sayacı bileşeni mod \(3\) bakımından \(0\) olan bütün durumların sayıları toplanır.
Durum sayısı sabit \(243\)'tür ve her pozisyonda aktif her durumdan \(3\) ağırlıklı geçiş yapılır. Bu nedenle toplam çalışma süresi
$$O(d\cdot 243\cdot 3)=O(d)$$
olur ve sabit katsayı küçüktür. Bellek kullanımı \(O(243)\)'tür; çünkü yalnızca mevcut ve bir sonraki DP katmanı saklanır.
Tomamos un número decimal de \(d\) cifras \(a_1a_2\dots a_d\) con \(a_1\ne 0\) y miramos todas sus subcadenas contiguas. Una subcadena es divisible por \(3\) exactamente cuando la suma de sus cifras es divisible por \(3\). Hay que contar cuántos números de \(d\) cifras tienen la propiedad de que el número total de subcadenas divisibles por \(3\) también es múltiplo de \(3\), y devolver el resultado módulo \(10^9+7\).
La idea decisiva es que la divisibilidad por \(3\) depende solo de las sumas prefijo módulo \(3\). Al escribir eso con cuidado, el problema completo se convierte en una programación dinámica sobre un espacio finito de solo \(243\) estados.
Sean \(a_1,\dots,a_d\) las cifras y definamos las sumas prefijo módulo \(3\) por
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d).$$
Como \(10\equiv 1\pmod 3\), una subcadena decimal \(a_{l+1}\dots a_r\) es congruente módulo \(3\) con la suma de sus cifras. Por tanto
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3,$$
y esa subcadena es divisible por \(3\) si y solo si
$$S_r\equiv S_l\pmod 3.$$
Así, cada subcadena válida corresponde exactamente a un par de prefijos con el mismo residuo.
Después de procesar las primeras \(k\) cifras, sea \(C_i(k)\) el número de índices de prefijo \(j\in\{0,\dots,k\}\) tales que \(S_j=i\). Entonces el número total de subcadenas divisibles por \(3\) en las primeras \(k\) cifras es
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}.$$
Las implementaciones no recalculan esta fórmula desde cero. Si el siguiente residuo prefijo es \(r=S_k\), entonces cada prefijo anterior con residuo \(r\) genera exactamente una nueva subcadena válida que termina en la posición \(k\). Por ello
$$T_k=T_{k-1}+C_r(k-1),$$
y después de registrar el nuevo prefijo tenemos
$$C_r(k)=C_r(k-1)+1.$$
Esta recurrencia en línea es el corazón del método.
La condición final pide \(T_d\equiv 0\pmod 3\), así que durante el proceso solo importa \(T_k\bmod 3\). Pero la actualización añade \(C_r(k-1)\), luego solo importa también \(C_r(k-1)\bmod 3\). En consecuencia, no hace falta guardar los conteos exactos: las tres frecuencias de residuos prefijo pueden reducirse módulo \(3\) sin perder información relevante para la respuesta final.
Por tanto, un estado queda descrito por
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
Cada componente tiene \(3\) posibilidades, así que el número total de estados es
$$3^5=243.$$
Supongamos que la siguiente cifra pertenece a la clase residual \(c\in\{0,1,2\}\) módulo \(3\). Si el estado actual es
$$\bigl(s,a_0,a_1,a_2,t\bigr),$$
entonces el nuevo residuo prefijo es
$$s'=(s+c)\bmod 3.$$
El número de nuevas subcadenas válidas creadas en este paso es el número actual de prefijos anteriores con residuo \(s'\), es decir, \(a_{s'}\) módulo \(3\). Luego
$$t'=(t+a_{s'})\bmod 3.$$
Después hay que contar también el prefijo recién creado, así que
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
mientras los otros dos contadores no cambian. Para cada estado y cada clase residual, la transición es determinista.
La programación dinámica no recorre las diez cifras una por una; las agrupa según su residuo módulo \(3\).
En la primera posición se permiten solo \(1,\dots,9\), y cada una de las tres clases aparece exactamente \(3\) veces:
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
Por eso, las multiplicidades del primer dígito son
$$(3,3,3).$$
Después de la primera posición ya se permiten \(0,\dots,9\). Las clases tienen entonces las frecuencias
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\},$$
o sea
$$(4,3,3).$$
Por eso se reutiliza el mismo grafo de transiciones en todas las posiciones, salvo que el vector de pesos de la primera es diferente.
Antes de leer ninguna cifra, solo existe el prefijo vacío. Por tanto
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0.$$
El estado inicial es entonces
$$\bigl(0,1,0,0,0\bigr).$$
Tras procesar las \(d\) cifras, un número es válido exactamente cuando
$$T_d\equiv 0\pmod 3.$$
Ejemplo para \(d=2\). Un número de dos cifras tiene tres subcadenas: \(a\), \(b\) y \(ab\). Si \(x\equiv a\pmod 3\) y \(y\equiv b\pmod 3\), esas tres subcadenas son divisibles por \(3\) bajo las condiciones
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3.$$
Para que el total sea múltiplo de \(3\), ese total debe ser \(0\) o \(3\). El valor \(3\) ocurre solo cuando \((x,y)=(0,0)\), lo que da \(3\cdot 4=12\) números. El valor \(0\) ocurre para \((x,y)=(1,1)\) y \((2,2)\), lo que da \(3\cdot 3+3\cdot 3=18\) números. En consecuencia,
$$12+18=30,$$
que coincide con la pequeña comprobación usada por las implementaciones.
Las implementaciones en C++, Python y Java enumeran primero los \(243\) estados y precalculan, para cada estado y cada clase residual \(0,1,2\), cuál es el siguiente estado. Así, el bucle principal se reduce a consultas en tablas y sumas.
En la posición \(1\), cada transición se pondera con \((3,3,3)\) porque la primera cifra no puede ser cero. En las posiciones posteriores se reutilizan exactamente las mismas transiciones, pero con pesos \((4,3,3)\). Al final de los \(d\) pasos, la respuesta es la suma de los conteos de todos los estados cuyo componente de total de subcadenas vale \(0\) módulo \(3\).
El número de estados es fijo e igual a \(243\), y cada posición realiza \(3\) transiciones ponderadas por estado activo. Por tanto, el tiempo total es
$$O(d\cdot 243\cdot 3)=O(d),$$
con una constante muy pequeña. La memoria es \(O(243)\), porque solo se guardan la capa actual y la siguiente de la programación dinámica.
设 \(a_1a_2\dots a_d\) 是一个首位不为 \(0\) 的 \(d\) 位十进制数。我们考察它的所有连续子串。一个子串能被 \(3\) 整除，当且仅当它的各位数字之和能被 \(3\) 整除。题目要求统计这样一类 \(d\) 位数：它们“可被 \(3\) 整除的子串总数”本身也恰好是 \(3\) 的倍数。答案需要对 \(10^9+7\) 取模。
最关键的观察是：是否能被 \(3\) 整除，只取决于前缀和模 \(3\) 的结果。一旦把这一点写清楚，原本看起来需要处理大量子串的任务，就会收缩成一个只有 \(243\) 个状态的小型有限状态动态规划。
记数字为 \(a_1,\dots,a_d\)，定义模 \(3\) 的前缀和
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d).$$
由于 \(10\equiv 1\pmod 3\)，一个十进制子串 \(a_{l+1}\dots a_r\) 在模 \(3\) 意义下与其数位和同余，因此
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3.$$
于是这个子串能被 \(3\) 整除，当且仅当
$$S_r\equiv S_l\pmod 3.$$
也就是说，每一个满足条件的子串，都恰好对应一对前缀余数相同的前缀位置。
处理完前 \(k\) 位后，设 \(C_i(k)\) 表示前缀下标 \(j\in\{0,\dots,k\}\) 中满足 \(S_j=i\) 的个数。那么前 \(k\) 位里可被 \(3\) 整除的子串总数就是
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}.$$
不过实现并不会每次都重新计算这个组合数公式。若新出现的前缀余数是 \(r=S_k\)，那么此前每一个余数也等于 \(r\) 的前缀，都会与当前位置组成一个新的合法子串。因此有
$$T_k=T_{k-1}+C_r(k-1),$$
接着把新的前缀本身记入统计，于是
$$C_r(k)=C_r(k-1)+1.$$
这个在线更新公式，就是整套解法真正使用的递推关系。
最终我们只关心 \(T_d\equiv 0\pmod 3\) 是否成立，因此计算过程中只需要知道 \(T_k\bmod 3\)。而递推里加上的量是 \(C_r(k-1)\)，所以同样只需要 \(C_r(k-1)\bmod 3\)。换句话说，三个前缀余数计数器的精确大小并不重要；把它们全部改成模 \(3\) 的值，不会损失任何与最终判定有关的信息。
所以，一个状态可以完整写成
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
每个分量都有 \(3\) 种可能，因此总状态数为
$$3^5=243.$$
设下一个数字的模 \(3\) 余数类为 \(c\in\{0,1,2\}\)。如果当前状态是
$$\bigl(s,a_0,a_1,a_2,t\bigr),$$
那么新的前缀余数就是
$$s'=(s+c)\bmod 3.$$
这一位新产生的合法子串数量，等于此前余数也为 \(s'\) 的前缀个数，也就是模 \(3\) 意义下的 \(a_{s'}\)。因此
$$t'=(t+a_{s'})\bmod 3.$$
随后还要把刚刚形成的新前缀本身计入对应计数器，所以
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
另外两个计数器保持不变。于是，对每个状态和每个余数类 \(c\)，转移都是确定的。
动态规划并不把十个数字都单独处理，而是先按模 \(3\) 的余数类分组。
在第一位，允许的数字是 \(1,\dots,9\)，三种余数类各出现 \(3\) 次：
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
因此第一位的权重向量是
$$(3,3,3).$$
从第二位开始，允许数字变成 \(0,\dots,9\)。此时三类的个数分别是
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\},$$
所以后续各位的权重向量为
$$(4,3,3).$$
这就是为什么整个过程始终复用同一张状态转移表，只是在第一位使用不同的权重。
在还没有读入任何数字之前，只有空前缀存在，因此
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0.$$
所以初始状态是
$$\bigl(0,1,0,0,0\bigr).$$
当 \(d\) 位都处理完以后，一个数字合法，当且仅当
$$T_d\equiv 0\pmod 3.$$
\(d=2\) 的例子。 两位数只有三个连续子串：\(a\)、\(b\) 和 \(ab\)。令 \(x\equiv a\pmod 3\)，\(y\equiv b\pmod 3\)。这三个子串分别在下列条件下能被 \(3\) 整除：
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3.$$
要让总数本身是 \(3\) 的倍数，这个总数只能是 \(0\) 或 \(3\)。总数等于 \(3\) 时，只可能是 \((x,y)=(0,0)\)，第一位有 \(3\) 种选法，第二位余数为 \(0\) 的数字有 \(4\) 个，所以得到 \(3\cdot 4=12\) 个数。总数等于 \(0\) 时，只可能是 \((x,y)=(1,1)\) 或 \((2,2)\)，分别各有 \(3\cdot 3\) 个，因此一共 \(18\) 个。最终
$$12+18=30,$$
这正好和实现中的小规模校验结果一致。
C++、Python 和 Java 实现都会先枚举全部 \(243\) 个状态，并预先算出“当前状态 + 下一个余数类 \(0,1,2\)”会走到哪个新状态。这样主循环里就不再需要做复杂判断，只需查表并累加方案数。
在第 \(1\) 位，状态转移要乘上权重 \((3,3,3)\)，因为首位不能为 \(0\)。从第 \(2\) 位开始，同样的转移表继续复用，但权重改为 \((4,3,3)\)。处理完全部 \(d\) 位后，把“合法子串总数这一分量为 \(0\) 模 \(3\)”的所有状态计数加起来，就是最终答案。
状态总数固定为 \(243\)，每一位至多从每个活动状态做 \(3\) 次带权转移，因此总时间复杂度为
$$O(d\cdot 243\cdot 3)=O(d),$$
常数非常小。空间复杂度为 \(O(243)\)，因为只需要保留当前层和下一层两组动态规划数组。
Рассматривается десятичное число длины \(d\) с цифрами \(a_1a_2\dots a_d\), где \(a_1\ne 0\). Нужно просмотреть все его непрерывные подстроки. Подстрока делится на \(3\) тогда и только тогда, когда сумма ее цифр делится на \(3\). Требуется посчитать все \(d\)-значные числа, у которых общее число таких подстрок само кратно \(3\), и вернуть ответ по модулю \(10^9+7\).
Главное наблюдение состоит в том, что делимость на \(3\) зависит только от префиксных сумм по модулю \(3\). После этого задача о большом количестве подстрок превращается в маленькую динамику по конечному числу состояний, а именно по \(243\) состояниям.
Пусть цифры равны \(a_1,\dots,a_d\), и определим префиксные суммы по модулю \(3\):
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d).$$
Так как \(10\equiv 1\pmod 3\), любая десятичная подстрока \(a_{l+1}\dots a_r\) сравнима по модулю \(3\) с суммой своих цифр. Значит,
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3,$$
и эта подстрока делится на \(3\) тогда и только тогда, когда
$$S_r\equiv S_l\pmod 3.$$
Иными словами, каждая подходящая подстрока соответствует паре префиксов с одинаковым остатком.
После обработки первых \(k\) цифр обозначим через \(C_i(k)\) число префиксных индексов \(j\in\{0,\dots,k\}\), для которых \(S_j=i\). Тогда общее число подстрок, делящихся на \(3\), внутри первых \(k\) цифр равно
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}.$$
Однако реализации не пересчитывают эту формулу заново. Если новый префиксный остаток равен \(r=S_k\), то каждая более ранняя позиция с тем же остатком образует новую подходящую подстроку, заканчивающуюся в \(k\). Поэтому
$$T_k=T_{k-1}+C_r(k-1),$$
а после учета нового префикса получаем
$$C_r(k)=C_r(k-1)+1.$$
Именно эта рекуррентная формула лежит в основе решения.
Финальное условие принимает вид \(T_d\equiv 0\pmod 3\), значит в процессе достаточно знать только \(T_k\bmod 3\). Но в переходе к нему прибавляется \(C_r(k-1)\), следовательно, нужен лишь \(C_r(k-1)\bmod 3\). Точные значения счетчиков не важны; каждую из трех частот префиксных остатков можно сразу сокращать по модулю \(3\).
Значит, состояние полностью описывается пятеркой
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
У каждого компонента по \(3\) возможных значения, поэтому всего состояний
$$3^5=243.$$
Пусть следующая цифра принадлежит классу остатка \(c\in\{0,1,2\}\) по модулю \(3\). Если текущее состояние имеет вид
$$\bigl(s,a_0,a_1,a_2,t\bigr),$$
то новый префиксный остаток равен
$$s'=(s+c)\bmod 3.$$
Количество новых подходящих подстрок, возникающих на этом шаге, равно текущему числу более ранних префиксов с остатком \(s'\), то есть \(a_{s'}\) по модулю \(3\). Поэтому
$$t'=(t+a_{s'})\bmod 3.$$
После этого нужно учесть и сам новый префикс, так что
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
а два остальных счетчика не меняются. Тем самым для каждого состояния и каждого класса остатка переход однозначен.
Динамика не перебирает все десять цифр по отдельности, а работает только с их остатками по модулю \(3\).
На первой позиции разрешены цифры \(1,\dots,9\), и каждая из трех остаточных классов встречается по \(3\) раза:
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
Поэтому кратности для первой позиции равны
$$(3,3,3).$$
Начиная со второй позиции доступны цифры \(0,\dots,9\). Тогда частоты классов становятся
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\},$$
то есть
$$(4,3,3).$$
Поэтому один и тот же граф переходов используется на всех шагах, а отличается только вес первой позиции.
До чтения первой цифры существует только пустой префикс, поэтому
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0.$$
Следовательно, начальное состояние равно
$$\bigl(0,1,0,0,0\bigr).$$
После обработки всех \(d\) цифр число считается подходящим тогда и только тогда, когда
$$T_d\equiv 0\pmod 3.$$
Пример для \(d=2\). У двузначного числа есть три непрерывные подстроки: \(a\), \(b\) и \(ab\). Пусть \(x\equiv a\pmod 3\), \(y\equiv b\pmod 3\). Эти три подстроки делятся на \(3\) при условиях
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3.$$
Чтобы итоговое число подходящих подстрок было кратно \(3\), оно должно равняться либо \(0\), либо \(3\). Значение \(3\) возникает только для \((x,y)=(0,0)\), что дает \(3\cdot 4=12\) чисел. Значение \(0\) возникает для \((x,y)=(1,1)\) и \((2,2)\), что дает \(3\cdot 3+3\cdot 3=18\) чисел. Итак,
$$12+18=30,$$
и это точно совпадает с маленькой проверкой, встроенной в реализации.
Реализации на C++, Python и Java сначала перечисляют все \(243\) состояния и заранее вычисляют, в какое состояние ведет каждый из трех возможных остаточных классов \(0,1,2\) из каждого состояния. Благодаря этому основной цикл состоит только из обращений к таблице переходов и сложений.
На первой позиции каждый переход умножается на веса \((3,3,3)\), потому что первая цифра не может быть нулем. На всех последующих позициях те же переходы повторно используются с весами \((4,3,3)\). После \(d\) шагов суммируются количества всех состояний, у которых компонент, отвечающий за число подходящих подстрок, равен \(0\) по модулю \(3\).
Число состояний постоянно и равно \(243\), а на каждой позиции выполняются \(3\) взвешенных перехода из каждого активного состояния. Следовательно, общее время работы равно
$$O(d\cdot 243\cdot 3)=O(d),$$
причем с маленькой константой. Память составляет \(O(243)\), поскольку хранятся только текущий и следующий слои динамики.
نأخذ عددًا عشريًا طوله \(d\) على الصورة \(a_1a_2\dots a_d\) مع الشرط \(a_1\ne 0\)، ثم ننظر إلى كل المقاطع الجزئية المتصلة فيه. يكون المقطع قابلًا للقسمة على \(3\) إذا وفقط إذا كان مجموع أرقامه قابلًا للقسمة على \(3\). المطلوب هو عدّ جميع الأعداد ذات \(d\) خانات التي يكون فيها عدد المقاطع القابلة للقسمة على \(3\) نفسه من مضاعفات \(3\)، ثم إرجاع النتيجة بترديد \(10^9+7\).
الفكرة الحاسمة هي أن قابلية القسمة على \(3\) تعتمد فقط على مجاميع البادئات modulo \(3\). وبمجرد صياغة هذه الفكرة بدقة، يتحول الفحص الهائل لكل المقاطع إلى برمجة ديناميكية صغيرة جدًا على فضاء من \(243\) حالة فقط.
لتكن الأرقام \(a_1,\dots,a_d\)، ولنعرّف مجاميع البادئات modulo \(3\) كما يلي:
$$S_0=0,\qquad S_k\equiv a_1+\cdots+a_k \pmod 3 \quad (1\le k\le d).$$
وبما أن \(10\equiv 1\pmod 3\)، فإن أي مقطع عشري \(a_{l+1}\dots a_r\) يكون مكافئًا modulo \(3\) لمجموع أرقامه. لذلك
$$a_{l+1}\dots a_r\equiv S_r-S_l\pmod 3,$$
ومن ثم يكون هذا المقطع قابلًا للقسمة على \(3\) إذا وفقط إذا
$$S_r\equiv S_l\pmod 3.$$
إذن كل مقطع صالح يقابل بالضبط زوجًا من البادئات لهما الباقي نفسه.
بعد معالجة أول \(k\) خانات، لِنرمز بـ \(C_i(k)\) إلى عدد فهارس البادئات \(j\in\{0,\dots,k\}\) التي تحقق \(S_j=i\). عندئذ يكون العدد الكلي للمقاطع القابلة للقسمة على \(3\) ضمن أول \(k\) خانات هو
$$T_k=\binom{C_0(k)}{2}+\binom{C_1(k)}{2}+\binom{C_2(k)}{2}.$$
لكن التنفيذ لا يعيد حساب هذه الصيغة من الصفر كل مرة. إذا كان باقي البادئة الجديدة هو \(r=S_k\)، فإن كل بادئة سابقة لها الباقي نفسه \(r\) تولد مقطعًا صالحًا جديدًا ينتهي عند الموضع \(k\). لذلك
$$T_k=T_{k-1}+C_r(k-1),$$
وبعد تسجيل البادئة الجديدة يصبح
$$C_r(k)=C_r(k-1)+1.$$
هذه العلاقة التكرارية المباشرة هي جوهر الحل.
شرط القبول النهائي هو \(T_d\equiv 0\pmod 3\)، ولذلك لا يهم أثناء الحساب إلا \(T_k\bmod 3\). وبما أن الانتقال يضيف \(C_r(k-1)\)، فهذا يعني أن \(C_r(k-1)\bmod 3\) يكفي أيضًا. إذن لا حاجة إلى القيم الدقيقة للعدادات؛ يمكن اختزال عدادات بواقي البادئات الثلاثة مباشرة modulo \(3\) من دون فقدان أي معلومة مهمة للجواب النهائي.
وعليه فإن الحالة توصف بالكامل بالخمسة
$$\bigl(S_k,\ C_0(k)\bmod 3,\ C_1(k)\bmod 3,\ C_2(k)\bmod 3,\ T_k\bmod 3\bigr).$$
ولأن لكل مركبة \(3\) احتمالات، فإن عدد الحالات الكلي هو
$$3^5=243.$$
افترض أن الرقم التالي ينتمي إلى فئة الباقي \(c\in\{0,1,2\}\) modulo \(3\). إذا كانت الحالة الحالية هي
$$\bigl(s,a_0,a_1,a_2,t\bigr),$$
فإن باقي البادئة الجديد يساوي
$$s'=(s+c)\bmod 3.$$
وعدد المقاطع الصالحة الجديدة المتولدة في هذه الخطوة يساوي عدد البادئات السابقة ذات الباقي \(s'\)، أي \(a_{s'}\) modulo \(3\). لذا
$$t'=(t+a_{s'})\bmod 3.$$
ثم يجب احتساب البادئة الجديدة نفسها، ومن ثم
$$a_{s'}\leftarrow (a_{s'}+1)\bmod 3,$$
بينما يبقى العدادان الآخران كما هما. وهكذا يكون الانتقال محددًا حتميًا لكل حالة ولكل فئة بواقي.
البرمجة الديناميكية لا تتعامل مع الأرقام العشرة واحدًا واحدًا، بل تجمعها بحسب بواقيها modulo \(3\).
في الخانة الأولى، الأرقام المسموح بها هي \(1,\dots,9\)، وكل فئة من فئات الباقي الثلاث تظهر \(3\) مرات:
$$\{3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\}.$$
ولهذا تكون أوزان الخانة الأولى
$$(3,3,3).$$
أما بعد الخانة الأولى فتصبح الأرقام الممكنة \(0,\dots,9\)، وتكون التعدادات
$$\{0,3,6,9\},\qquad \{1,4,7\},\qquad \{2,5,8\},$$
أي
$$(4,3,3).$$
ولهذا يُعاد استخدام جدول الانتقالات نفسه في كل المواضع، لكن بمتجه أوزان مختلف في الموضع الأول.
قبل قراءة أي رقم لا توجد إلا البادئة الفارغة، ولذلك
$$S_0=0,\qquad C_0(0)=1,\qquad C_1(0)=C_2(0)=0,\qquad T_0=0.$$
إذًا الحالة الابتدائية هي
$$\bigl(0,1,0,0,0\bigr).$$
وبعد معالجة \(d\) خانات يكون العدد صالحًا إذا وفقط إذا
$$T_d\equiv 0\pmod 3.$$
مثال عند \(d=2\). العدد ذو الخانتين يملك ثلاثة مقاطع متصلة هي \(a\) و\(b\) و\(ab\). إذا كتبنا \(x\equiv a\pmod 3\) و\(y\equiv b\pmod 3\)، فإن هذه المقاطع تكون قابلة للقسمة على \(3\) عندما
$$a:\ x=0,\qquad b:\ y=0,\qquad ab:\ x+y\equiv 0\pmod 3.$$
ولكي يكون العدد الكلي للمقاطع من مضاعفات \(3\)، فلا بد أن يساوي \(0\) أو \(3\). القيمة \(3\) تحدث فقط عندما \((x,y)=(0,0)\)، وهذا يعطي \(3\cdot 4=12\) عددًا. أما القيمة \(0\) فتحدث عند \((x,y)=(1,1)\) و\((2,2)\)، وهذا يعطي \(3\cdot 3+3\cdot 3=18\) عددًا. ومن ثم
$$12+18=30,$$
وهو بالضبط مقدار التحقق الصغير المستخدم في التطبيقات.
تقوم تطبيقات C++ وPython وJava أولًا بحصر جميع الحالات \(243\)، ثم تحسب مسبقًا لأي حالة حالية وأي فئة باقٍ \(0,1,2\) ما هي الحالة التالية المقابلة. بهذا تصبح الحلقة الرئيسة مجرد عمليات رجوع إلى جداول وجمع للأعداد.
في الموضع الأول تُوزن الانتقالات بالمتجه \((3,3,3)\) لأن الرقم الأول لا يجوز أن يكون صفرًا. وفي جميع المواضع اللاحقة يُعاد استعمال الانتقالات نفسها مع الأوزان \((4,3,3)\). وبعد اكتمال \(d\) خطوة، يُجمع عدد الطرق في كل حالة يكون فيها مركب عدد المقاطع الصالحة مساويًا لـ \(0\) modulo \(3\).
عدد الحالات ثابت ويساوي \(243\)، وفي كل موضع توجد \(3\) انتقالات موزونة من كل حالة فعالة. لذلك يكون زمن التنفيذ الكلي
$$O(d\cdot 243\cdot 3)=O(d),$$
وبثابت صغير جدًا. أما الذاكرة فهي \(O(243)\)، لأننا نحتاج فقط إلى طبقة البرمجة الديناميكية الحالية والطبقة التالية.