Project Euler Problem 706

Solution

Answer: 884837055

Let

$p_i$ be the prefix sum of digits modulo $3$, with $p_0=0$,
and $c_r$ be the number of prefixes congruent to $r \pmod 3$.

A substring is divisible by $3$ iff its endpoints have the same prefix residue, so:

$$f(n)=\sum_{r=0}^{2} \binom{c_r}{2}$$

We only care whether $f(n)\equiv 0 \pmod 3$, and since

$$\binom{c}{2}\pmod 3$$

depends only on $c \bmod 3$, the problem reduces to a finite-state DP with:

current prefix residue ($3$ possibilities),
$c_0,c_1,c_2 \bmod 3$ ($3^3$ possibilities),

for a total of $3^4=81$ states.

Using matrix exponentiation on the $81\times81$ transition matrix to compute $F(10^5)$ modulo $1,000,000,007$, and verifying against the given checks:

$F(2)=30$
$F(6)=290898$

the final result is:

Answer: 464171410