本解説内において、「同じ辺を連続して通らない」という条件を \((\ast)\) で表します。

\(N\) 次正方行列 \(X_k\) を以下のように定義します。

• \(X_k\) の \(ij\) 成分は頂点 \(i\) から頂点 \(j\) への長さ \(k\) の歩道であって、\((\ast)\) を満たす歩道の数

このとき、求めるべきは \(X_K\) の \(1N\) 成分です。以下、\(A,D,I,O\) をそれぞれ \(G\) の隣接行列、\(G\) の次数行列（対角成分に各頂点の次数を並べた行列）、単位行列、零行列とします。大きさはどれも \(N \times N\) です。

\(X_k\) を順に計算していきましょう。

\(k=1\) のとき

頂点 \(i\) から頂点 \(j\) への長さ \(1\) の歩道の個数は頂点 \(i\) から頂点 \(j\) への辺の本数に一致するので \(X_1=A\) です。

\(k=2\) のとき

\((\ast)\) がない場合、頂点 \(i\) から頂点 \(j\) への長さ \(2\) の歩道の個数は \(AX_1=A^2\) の \(ij\) 成分に一致します。ここから \((\ast)\) を満たさないものを引けばよく、これは \(i \rightarrow j \rightarrow i\) と移動するものだけです。このような歩道は各 \(i\) に対して \(j\) の選び方の数だけあるので \(X_2=A^2-D\) となります。

\(k \geq 3\) のとき

\(k=2\) のときと同様に \(AX_{k-1}\) から \((\ast)\) を満たさないものを引くことを考えます。\(k-2\) 回目の移動が終わったときに頂点 \(i\) にいるとします。ここで、\((\ast)\) を満たさないものは \(i \rightarrow j \rightarrow i\) と移動するものだけです。しかし、\(k-2\) 回目の移動の直前にいた頂点を \(j\) として選ぶことは出来ません。よって \(j\) として選べるのは 各 \(i\) に対して、\((次数-1)\) 通りあるので \(X_k=AX_{k-1}-(D-I)X_{k-2}\) となります。

以上をまとめれば

\[ X_k=\begin{cases} A \qquad(k=1)\\ A^2-D\qquad(k=2) \\ AX_{k-1}-(D-I)X_{k-2}\qquad(k \geq 3) \end{cases} \]

となります。しかし、これを愚直に計算しては \(O(N^3K)\) となり実行時間制限に間に合いません。そこで \(k \geq 3\) のときの式を次のように変形します。

\[\begin{pmatrix} X_k \\ X_{k-1} \end{pmatrix} = \begin{pmatrix} A & -(D-I) \\ I & O \end{pmatrix}\begin{pmatrix} X_{k-1} \\ X_{k-2} \end{pmatrix}\]

これは行列累乗を用いて

\[\begin{pmatrix} X_K \\ X_{K-1} \end{pmatrix} = \begin{pmatrix} A & -(D-I) \\ I & O \end{pmatrix}^{K-2}\begin{pmatrix} X_2 \\ X_1 \end{pmatrix}\]

として計算できるので \(O(N^3 \log K)\) でこの問題を解くことが出来ました。