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

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.

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])