\begin{tutorial}{Колобки против Энигмы}

Введём обозначение $A = 10$

Решение за $O(n A^3)$: заведём динамику $dp[n][d][g]$ --- количество чисел длины $n$ таких, что последняя цифра равна $d$ и её НОД с предыдущей цифрой равен $g$. База динамики -- переберём всевозможные двузначные числа, состояние определяется второй цифрой и её НОДом с первой, увеличиваем значение в состоянии на $1$. Считать эту динамику можно вперёд: $dp[n + 1][e][\gcd(d, e)] += dp[n][d][g], g \neq \gcd(d, e)$. Ответ ---  сумма по всем состояниям динамики.

Решение за $O(n A^2 \log A)$: заметим, что число состояний динамики на самом деле не $A^2$, а $A \log A$, поскольку $g | d$, состояний со вторым параметром равным $g$ будет $\frac{A}{g}$. Сумма $\sum \limits_{g=1}^{A} \frac{A}{g}$ оценивается как $A \log A$, на практике выходит $33$ состояния.

Эта динамика оптимизируется бинарным возведением матрицу в степень: возьмём матрицу $M$ размерами $33\ \times 33$, Пронумеруем как угодно все состояния, затем определим $M_{i,j} = $ можно ли из состояния $i$ перейти в состояние $j$, дописав одну цифру. Затем возводим $M$ в степень $n-2$ и домножаем на базу. Получаем время работы $O(t (A \log A)^3 \log n)$.

Заметим, что в бинарном возведении в степень мы каждый раз считаем $M^{2^k}$, но это можно сделать один раз. А с предподсчитанными степенями матрицы $M$ мы можем домножать на них не матрицу $33 \times 33$, а одномерный вектор размера $33$. Тогда время работы составит $O((A \log A)^3 \log n + t (A \log A)^2 \log n)$.

\end{tutorial}
