정점 \(V\)개와 방향 간선 \(E\)개로 이루어진 그래프가 주어진다. 정점 \(s\) 에서 출발하여 정점 \(t\) 에 도착하는, 간선을 정확히 \(K\)개 사용하는 경로(walk; 정점·간선 재방문 허용)의 개수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 구하여라.

\(K\) 가 최대 \(10^{18}\) 이므로 단순 DP로는 불가능하다. 인접 행렬 \(A\) 의 \(K\) 거듭제곱 \(A^K\) 의 \((s, t)\) 성분이 정확히 답이 된다. \(V \le 50\) 이므로 행렬 빠른 거듭제곱으로 \(O(V^3 \log K)\) 에 해결할 수 있다. 같은 두 정점 사이에 여러 간선이 있을 수 있고, 자기 루프도 가능하다.

\(K = 0\) 이면 간선을 하나도 사용하지 않는 경로만 허용되며, 이는 \(s = t\) 일 때만 1, 아니면 0이다.

\(1 \le V \le 50\)

\(0 \le E \le V^2\)

\(1 \le s, t \le V\)

\(0 \le K \le 10^{18}\)

첫째 줄에 \(V\), \(E\), \(s\), \(t\), \(K\) 가 공백으로 구분되어 주어진다.

이후 \(E\)개의 줄에 간선 \(u \to v\) 가 주어진다.

\(s\) 에서 \(t\) 로 가는 길이 \(K\) 경로의 수를 \(1{,}000{,}000{,}007\) 로 나눈 나머지를 출력한다.

riseoj 작성

출처 Original