BOJ 1160 - Random Number Generator

image.png

풀 때는 분할정복으로 풀었지만, xn+1=axn+cx_{n+1}=ax_n+c 라는 의미는 행렬로 표현할 수 있다.

(xn+11)=(ac01)(xn1) \begin{pmatrix} x_{n+1} \\ 1 \end{pmatrix} = \begin{pmatrix} a & c \\ 0 & 1 \end{pmatrix} \begin{pmatrix}x_n \\ 1 \end{pmatrix}

따라서 (ac 01)\begin{pmatrix}a & c \ 0 & 1\end{pmatrix}을 nn번 거듭제곱하고 (x0 1)\begin{pmatrix}x_0 \ 1\end{pmatrix} 을 넣어서 정답을 확인하자.

오버플로우에 유의한다.

Tags:

Categories:

Updated:

Comments

You may also enjoy