yukariko   2년 전

식을 정리해본결과 a~b 항의 합은

f(b+2) - f( a +1) 항으로 구할수있다는것 까진 알아냈는데

저 범위를 충당할 방법이 떠오르질 않네요..

피보나치의 일반항을 이용해서 double형 + great pow로 해결해보려했지만 이것도 힘든것같고..

어떻게 해야할까요?

baekjoon   2년 전

\(n\)번째 피보나치 수를 \(f(n)\) 이라고 했을 때, 이를 구하는 점화식은 \(f(n) = f(n-1) + f(n-2)\)입니다. (\(f(1) = f(2) = 1\)

\(n-1\)번째 피보나치 수는 \(f(n-1) = f(n-2) + f(n-3)\) 이고요

그럼 이것을 행렬로 나타낼 수 있습니다.

\[\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} \]

\[\begin{pmatrix} f(n-1) \\ f(n-2) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} f(n-2) \\ f(n-3) \end{pmatrix} \]

\[\begin{pmatrix} f(n) \\ f(n-1) \end{pmatrix}=\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} ^{2} \begin{pmatrix} f(n-2) \\ f(n-3) \end{pmatrix}\]

그럼, 앞의 행렬을 적절히 제곱을 한 다음에, 뒤의 행렬에 \(f(2)\)와 \(f(1)\)를 넣어주면 \(f(n)\)의 값을 빠르게 구할 수 있습니다.

yukariko   2년 전

와.. 행렬을 이용해서 f(n)을 구하는방법도 있군요.. 덕분에 중요한것 배워가네요

감사합니다!

yukariko   2년 전

덕분에 해결했습니다.. 감격 ㅠㅠ

ZZangZZang   2년 전

행렬왕 백준형

댓글을 작성하려면 로그인해야 합니다.