BOJ 1160 - Random Number Generator
BOJ 1160 - Random Number Generator
풀 때는 분할정복으로 풀었지만, $x_{n+1}=ax_n+c$ 라는 의미는 행렬로 표현할 수 있다.
$$
\begin{pmatrix}
x_{n+1} \\ 1
\end{pmatrix}
=
\begin{pmatrix}
a & c \\
0 & 1
\end{pmatrix} \begin{pmatrix}x_n \\
1
\end{pmatrix}
$$
따라서 $\begin{pmatrix}a & c \ 0 & 1\end{pmatrix}$을 $n$번 거듭제곱하고 $\begin{pmatrix}x_0 \ 1\end{pmatrix}$ 을 넣어서 정답을 확인하자.
오버플로우에 유의한다.
Comments