① 12849 - 본대 산책 문제에 이은 숭실대학교 본대를 산책하여 정보대로 다시 돌아오는 경우의 수를 구하는 문제입니다. 이전 문제와는 다르게 D값이 매우 큽니다. 이 정도의 D값이면 시간복잡도를 $O(\log D)$ 수준으로 낮춰야 합니다. 이전 문제는 DP를 이용한 $O(D)$ 방법이었다는 것을 생각해보면 이번에는 조금 다른 방식으로 접근을 해야 할 것 같습니다. 여기서 고려해야 할 점이라면 선형 점화식을 푸는 DP 문제는 행렬을 이용하여 그 시간복잡도 수준을 낮출 수 있다는 것입니다. 이제 그 행렬을 구해보도록 하겠습니다.
먼저 지도에는 8개의 건물이 있고, 그 사이의 길이 존재합니다. 이제 아래와 같이 건물에 번호를 매기겠습니다.
| 번호 |
이름 |
| 0 |
정보과학관 |
| 1 |
전산관 |
| 2 |
미래관 |
| 3 |
신양관 |
| 4 |
한경직기념관 |
| 5 |
진리관 |
| 6 |
형남공학관 |
| 7 |
학생회관 |
그리고 지도에 주어진 도로에 따라 각 건물에 도달하는 경우의 수를 구하는 점화식을 세웁니다.
\[\begin{pmatrix}
\begin{aligned}
d_{n+1,0}=&d_{n,1}+d_{n,2}\\
d_{n+1,1}=&d_{n,0}+d_{n,2}+d_{n,3}\\
d_{n+1,2}=&d_{n,0}+d_{n,1}+d_{n,3}+d_{n,4}\\
d_{n+1,3}=&d_{n,1}+d_{n,2}+d_{n,4}+d_{n,5}\\
d_{n+1,4}=&d_{n,2}+d_{n,3}+d_{n,5}+d_{n,6}\\
d_{n+1,5}=&d_{n,3}+d_{n,4}+d_{n,7}\\
d_{n+1,6}=&d_{n,4}+d_{n,7}\\
d_{n+1,7}=&d_{n,5}+d_{n,6}\\
\end{aligned}
\end{pmatrix}\]
이를 행렬로 나타내면 아래와 같습니다.
\[D_{n+1}=AD_{n}\\
A=
\begin{pmatrix}
0&1&1&0&0&0&0&0\\
1&0&1&1&0&0&0&0\\
1&1&0&1&1&0&0&0\\
0&1&1&0&1&1&0&0\\
0&0&1&1&0&1&1&0\\
0&0&0&1&1&0&0&1\\
0&0&0&0&1&0&0&1\\
0&0&0&0&0&1&1&0\\
\end{pmatrix}\]
그리고 위 식을 일반화하면 \(D_n=A^n D_0\)가 되고, D0는 시간이 0일 때의 경우의 수이므로 아래와 같은 값이 됩니다.
\[D_0=\begin{pmatrix}1\\0\\0\\0\\0\\0\\0\\0\end{pmatrix}\]
그리고 \(A^n\)을 구할 때에는 아래의 관계식을 사용하여 로그 스케일의 시간 복잡도를 통해 구합니다.
\[A^n=
\begin{cases}
A^{\frac{n}{2}}\times A^{\frac{n}{2}}&(n\equiv 0\mod{2})\\
A^{\lfloor\frac{n}{2}\rfloor}\times A^{\lfloor\frac{n}{2}\rfloor}\times A&(n\equiv 1\mod{2})
\end{cases}\]
이제 주어지는 시간 값에 따라 \(D_n\)을 구하고, \(d_{n,0}\)을 출력하면 됩니다.
PS알못 OrbitHv의 PS