Calculate the number of strings of length $d$ that DFA of size $n$ accepts in $O(dn)$ operations

Question

We can find the number of strings as a sum of numbers of pathes in the oriented graph of DFA from $q_0$ to $q_i$ ($q_i\in F$, $F$ is the set of finite states, $q_0$ is the initial state) of the length $d$, calculating $M^d$ where $M$ is the adjacency matrix of the graph. And if we do exponentation by squaring and as the matrix $M$ has $n$ rows and $n$ columns, it takes $\log d$ squaring of matrices, and each squaring of matrix we can do in polynomial time. So we have to do $O(\log d \cdot p(n))$ operations, where $p(n)$ is a polynomial of $n$. But the task is to make this calculation in $O(dn)$ operations.

Answer 1

Let $f(i,j)$ be the number of inputs of length $j$ that make the automaton end in state $i$. One can compute all $f(i.j+1)$ from all $f(i.j)$ in [number of arrows] steps. Hence all $f(i,d)$ can be computed in $O(dn)$ steps when $n$ is the number of arrows (i.e., the number of states times the size of the alphabet) and with $O(n)$ memory (in act, only [number of states])