Because the sum of in-degrees is fixed, once \((d_0, \ldots, d_{N-1})\) is determined, \(d_N\) is also determined. Hence, it suffices to count the possibilities of \(D \coloneqq (d_0, \ldots, d_{N-1})\).

Also, each element \(d_i\) of \(D\) clearly satisfies \(0 \leq d_i \leq 3\).

First, consider the problem for the graph obtained from the original \(G\) by removing the undirected edge \(\lbrace N-1, 0 \rbrace\). We can solve this in \(O(N)\) time using a dynamic programming algorithm that determines \(D\) from the beginning to the end with the table described below:

\(\mathrm{dp}[i][A] \coloneqq\) (The number of sequences \((d_0, \ldots, d_{i-1}) \in \{0, 1, 2, 3\}^i\) for which, in a direction assignment of \(G\) that realizes these in-degrees, the possible directions of the edge \(\lbrace i-1, i \rbrace\) form exactly the set \(A \subseteq \{\leftarrow, \rightarrow\}\))

Then, to solve the problem for the original \(G\) that includes the edge \(\lbrace N-1, 0 \rbrace\), we look at the three possible cases for the direction set of the edge \(\lbrace N-1, 0 \rbrace\): \(\{\leftarrow\}\), \(\{\rightarrow\}\), and \(\{\leftarrow, \rightarrow\}\). For each case, we run the above DP:

• Initialize \(\mathrm{dp}[0][\{\leftarrow\}] \coloneqq 1,\ \mathrm{dp}[0][\{\rightarrow\}] \coloneqq 0,\ \mathrm{dp}[0][\{\leftarrow, \rightarrow\}] \coloneqq 0\), run the DP, and take \(\mathrm{dp}[N][\{\leftarrow\}]\) as the answer for that case.
• Initialize \(\mathrm{dp}[0][\{\leftarrow\}] \coloneqq 0,\ \mathrm{dp}[0][\{\rightarrow\}] \coloneqq 1,\ \mathrm{dp}[0][\{\leftarrow, \rightarrow\}] \coloneqq 0\), run the DP, and take \(\mathrm{dp}[N][\{\rightarrow\}]\) as the answer.
• Initialize \(\mathrm{dp}[0][\{\leftarrow\}] \coloneqq 0,\ \mathrm{dp}[0][\{\rightarrow\}] \coloneqq 0,\ \mathrm{dp}[0][\{\leftarrow, \rightarrow\}] \coloneqq 1\), run the DP, and take \(\mathrm{dp}[N][\{\leftarrow, \rightarrow\}]\) as the answer.

However, in these three cases combined, only the sequence \((d_0, d_1, \ldots, d_{N-1}) = (1, 1, \ldots, 1)\) is counted multiple times, and specifically it is counted in all three. Therefore, we must subtract \(2\) from the sum in the end.

By this method, the problem can be solved in \(O(N)\) time.

A slightly different approach is to use the fact that the realizability of \((d_0, \ldots, d_{N-1})\) is equivalent to satisfying all of the following conditions, and then count all such \((d_0, \ldots, d_{N-1})\) via a similar DP in \(O(N)\) time:

• \(0 \leq d_i \leq 3\)
• \(d_i - s_i \leq 2\)
• Between any two indices \(i, j\) with \(d_i = d_j = 0\), there exists \(k\) such that \(d_k \geq 2\).
• Between any two indices \(i, j\) with \(d_i - s_i = d_j - s_j = 2\), there exists \(k\) such that \(d_k - s_k \leq 0\).