7280 : 피보나치 행렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
행렬 곱셈과 분할 정복을 이용하여 $N$번째 피보나치 수 $F_N \bmod 10^9+7$을 구하십시오.
핵심 공식: $\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}^n \begin{pmatrix}1\\0\end{pmatrix}$
$N$이 최대 $10^{18}$이므로 $O(\log N)$ 행렬 거듭제곱이 필요합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
핵심 공식: $\begin{pmatrix}F_{n+1}\\F_n\end{pmatrix} = \begin{pmatrix}1&1\\1&0\end{pmatrix}^n \begin{pmatrix}1\\0\end{pmatrix}$
$N$이 최대 $10^{18}$이므로 $O(\log N)$ 행렬 거듭제곱이 필요합니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정수 $N$이 주어집니다. ($1 \le N \le 10^{18}$)
출력 설명
$N$번째 피보나치 수 $F_N \bmod (10^9+7)$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
10
출력 예시
COPY
복사되었습니다!
복사되었습니다!
55도움
행렬 $M = [[1,1],[1,0]]$의 $N-1$제곱을 구하면 $M^{N-1}[0][0] = F_N$. 행렬 곱셈 함수와 분할 정복 거듭제곱 함수를 구현합니다.