入次数の総和は一定であるので \((d_0, \ldots, d_{N-1})\) が決まると \(d_N\) も決まります。 よって、以下では \(D \coloneqq (d_0, \ldots, d_{N-1})\) としてありえるものを数えれば十分です。

また明らかに、\(D\) としては各要素 \(d_i\) が \(0 \leq d_i \leq 3\) を満足するものだけを考えれば十分です。

まず、元の \(G\) から無向辺 \(\lbrace N-1, 0 \rbrace\) を消去したグラフに対する問題を考えます。 これは、\(D\) を先頭から決定していくことを考え、下記のテーブルを用いる動的計画法のアルゴリズムによって \(O(N)\) 時間で解くことができます：

\(\mathrm{dp}[i][A] \coloneqq\)（\((d_0, \ldots, d_{i-1}) \in \{0, 1, 2, 3\}^i\) であって、その入次数列を実現する \(G\) の向きづけにおける辺 \(\lbrace i-1, i \rbrace\) の向きとしてあり得るものの集合が \(A\)（集合 \(\{\leftarrow, \rightarrow\}\) の部分集合）であるものの個数）

無向辺 \(\lbrace N-1, 0 \rbrace\) を含む元の \(G\) での問題を解くには、辺 \(\lbrace N-1, 0 \rbrace\) の向きとしてあり得るものの集合が、 \(\{\leftarrow\}\) である場合、\(\{\rightarrow\}\) である場合、\(\{\leftarrow, \rightarrow\}\) である場合の、\(3\) 通りの場合それぞれについて、上記の DP を行えば良いです。

例えば、下記の \(3\) 個の答えの総和を求めれば良いです。

• \(\mathrm{dp}[0][\{\leftarrow\}] \coloneqq 1, \mathrm{dp}[0][\{\rightarrow\}] \coloneqq 0, \mathrm{dp}[0][\{\leftarrow, \rightarrow\}] \coloneqq 0\) と初期化して DP を行い、\(\mathrm{dp}[N][\{\leftarrow\}]\) を答えとする。
• \(\mathrm{dp}[0][\{\leftarrow\}] \coloneqq 0, \mathrm{dp}[0][\{\rightarrow\}] \coloneqq 1, \mathrm{dp}[0][\{\leftarrow, \rightarrow\}] \coloneqq 0\) と初期化して DP を行い、\(\mathrm{dp}[N][\{\rightarrow\}]\) を答えとする。
• \(\mathrm{dp}[0][\{\leftarrow\}] \coloneqq 0, \mathrm{dp}[0][\{\rightarrow\}] \coloneqq 0, \mathrm{dp}[0][\{\leftarrow, \rightarrow\}] \coloneqq 1\) と初期化して DP を行い、\(\mathrm{dp}[N][\{\leftarrow, \rightarrow\}]\) を答えとする。

ただし、この方法では \((d_0, d_1, \ldots, d_{N-1}) = (1, 1, \ldots, 1)\) のみ、上記の \(3\) ケースにわたって重複して数え上げられるため、最後に総和から \(2\) を引く必要があります。

以上によって、本問題を \(O(N)\) 時間で解くことができます。

やや異なる解法として、\((d_0, \ldots, d_{N-1})\) が実現できるのは下記の全部が成り立つのと同値であることを用い、 これら全ての満たす \((d_0, \ldots, d_{N-1})\) を上述の解法と同様の DP で数え上げても \(O(N)\) 時間で解くことができます。

• \(0 \leq d_i\leq 3\)
• \(d_i-s_i \leq 2\)
• \(d_i = d_j = 0\) である \(i, j\) の間には \(d_k \geq 2\) となる \(k\) がある。
• \(d_i-s_i = d_j-s_j = 2\) である \(i, j\) の間には \(d_k-s_k \leq 0\) となる \(k\) がある。