점화식은 행렬의 거듭 제곱을 이용해서, DP 보다 빠르게 구할 수가 있다

우리는 고등학교 시절, 점화식을 일반항으로 고치는 방법을 공부하였다.

그러나, 이 작업은 매우 기술적이여서 일반항으로의 변환이 그렇게 쉽지가 않다.

그러나, 행렬을 이용을 하면, 일반항을 매우 쉽게, 그리고 매우 빠른 속도로 구할 수가 있다.

위와 같은 점화식이 있다고 하자!

 

 

최종식

 

 

피보나치 수열의 점화식은 아래와 같다.

p == q == 1이므로, 위 식을 아래와 같이 변형할 수가 있다.

최종식

 

위 식을 귀납적으로 표현을 하면 위와 같다.

이 식을 이용을 하면, 피보나치 수열의 (n+2) 번째 항을 알 수가 있다.

( 만약, 이 문제를 DP로 풀게 되면, O(십억)의 비용이 들지만, 행렬의 거듭 제곱을 이진수로 구하게 되면, O(log십억)으로 빠르게 구할 수가 있다.)

( 아래 문제 참조 )

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6