Write a program to calculate the total number of strings that are made of exactly N characters. None of the strings can have "13" as a substring. The strings may contain any integer from "0-9", repeated any number of times.
From above question I derived a recursive equation which gives total "13" s as follow:
$$F_{n} = 10F_{n-1} + 10^{n-2} - F_{n-2}$$
I am trying to solve the problem using Fast Fibonacci Transform with O(logn) time complexity as described in this link.
Taking reference to this post I tried to convert the obtained recursive equation into matrix recursive form:
I need to find A such that:
$$\begin{bmatrix} F_n \\\ F_{n-1} \end{bmatrix} = A \begin{bmatrix} F_{n-1} \\\ F_{n-2} \end{bmatrix}$$
But because of the presence of 10n-2 I am not getting the constant.
My $A$ looks like the following:
$$ A = \begin{bmatrix} 10 & -10^{n-2} \\\ 1 & 0 \end{bmatrix}$$
Thus matrix $A$ is not constant.
What should I do in this case? Please shed some light