Here is the question I came across

Deterministic finite automaton(DFA) is a finite state machine that accepts/rejects finite strings of symbols and only produces a unique computation (or run) of the automation for each input string.

DFAs can be represented using state diagrams. For example, in the automaton shown below, there are three states: S0, S1, and S2 (denoted graphically by circles). The automaton takes a finite sequence of 0s and 1s as input. For each state, there is a transition arrow leading out to a next state for both 0 and 1. Upon reading a symbol, a DFA jumps deterministically from a state to another by following the transition arrow. For example, if the automaton is currently in state S0 and current input symbol is 1 then it deterministically jumps to state S1. A DFA has a start state (denoted graphically by an arrow coming in from nowhere) where computations begin, and a set of accept states (denoted graphically by a double circle) which help define when a computation is successful.

[![Sample DFA](https://i.stack.imgur.com/cNmcl.png)](https://i.stack.imgur.com/cNmcl.png)
These are some strings above DFA accepts,

```
0
00
000
11
110
1001

```

You are given a DFA in input and an integer N. You have to tell how many distinct strings of length N the given DFA accepts.

Notes 

* Assume each state has two outgoing edges(one for 0 and one for 1). Both outgoing edges won’t go to the same state.
* There could be multiple accept states, but only one start state.
* A start state could also be an accept state.

Input format 

* States are numbered from 0 to K-1, where K is total number of states in DFA.
* You are given three arrays A, B, C and two integers D and N.
* Array A denotes a 0 edge from state numbered i to state A[i], for all 0 ≤ i ≤ K-1
* Array B denotes a 1 edge from state numbered i to state B[i], for all 0 ≤ i ≤ K-1
* Array C contains indices of all accept states.
* Integer D denotes the start state.
* Integer N denotes you have to count how many distinct strings of length N the given DFA accepts.

Constraints

```
1 ≤ K ≤ 50 
1 ≤ N ≤ 10^4

```

Example :

For the DFA shown in image, input is

```
A = [0, 2, 1]
B = [1, 0, 2]
C = [0]
D = 0

```

Input 1
-------

```
N = 2
Strings '00' and '11' are only strings on length 2 which are accepted. So, answer is 2.

```

Input 2
-------

```
N = 1
String '0' is the only string. Answer is 1.

```

My Solution
-----------

I have a brute force recursive solution in Mind which works like this:

1. Start with the start state. let it be `curr`
2. check if `N==0` and `curr` is accept state then increment `1` to the total states and return;
3. Now for both `0 and 1` as input let the `curr` state goes to `curr0` and `curr1`. call the recursive function twice with `curr` state as `curr0` and `curr1` and also with `N-1`;

Problem with my solution
------------------------

But the problem is that this solution will check all possible strings of length `N` containing `{0,1}`. So the Time complexity of this would be `2^N` and since `1 <= N <= 10^4` this is exponential and not feasible.

Question
--------

Is there an efficient solution to this problem that this that someone could suggest? May be this problem is NP-Complete and this is the only solution. Any help would be appreciated.