Detailed mathematical approach

Problem Summary

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\).

Mathematical Approach

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.

Step 1: Turn substrings into pairs of equal prefix residues

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.

Step 2: Count new divisible substrings incrementally

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.

Step 3: Why only values modulo \(3\) are needed

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.$

Step 4: Transition produced by one new digit

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.

Step 5: Use digit-class multiplicities instead of all ten digits

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\).

Step 6: Initial state, acceptance condition, and a worked example

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.

How the Code Works

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\).

Complexity Analysis

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.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=706
2. Divisibility rule for \(3\): Wikipedia — Divisibility rule
3. Congruence in number theory: Wikipedia — Congruence relation
4. Dynamic programming: Wikipedia — Dynamic programming
5. Finite-state machine: Wikipedia — Finite-state machine