행렬 멱법으로 피보나치 수열을 빠르게 구해 보고, 이를 확장해 보자. 행렬을 곱하는 방법 알고 있다면,

$\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix}=$$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$$\begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix}$임을 이용해

$\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix}=\begin{bmatrix} 1&&1 \\ 1&&0 \end{bmatrix}^n$$\begin{bmatrix} 1 \\ 0 \end{bmatrix}$임을 재귀적으로 알 수 있다.

$\begin{bmatrix} 1&&1 \\ 1&&0 \end{bmatrix}^n$는 어떻게 하면 빠르게 구할 수 있을까? O(logn)에 구하는 방법이 있다.

행렬 대신 숫자로 바꾸어 3^21을 구해 보자.

arr[i]=3^(1<<i)로 정의하자. arr[i]={3, 9, 81, 6561, 43046721, …}처럼 저장되어 있을 것이다. 21은 0001 0101이므로 arr[4]arr[2]arr[0]=3^163^43^1=3^21. 이런 방식으로 빠르게 구할 수 있다. 정리하자면 a^n을 1. n을 이진법으로 나타낸 후, 2. 해당할 때마다 arr[i]에 저장된 값을 곱해주면 O(logn)의 시간에 구할 수 있다. 행렬도 마찬가지로 구하면 된다.

$\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^n$을 O(logn)에 구할 수 있으므로, Fib(n)을 로그의 시간복잡도에 계산할 수 있다.

다음과 같이 n이 10^18으로 아주 큰 수여도 빠르게 계산할 수 있다.

참고로, 피보나치 수는 재귀적으로 계산할 경우 약 $O(2^n)$의 시간복잡도가 소요된다. 정확히는 $O(Fib(n))$의 시간복잡도가 소요되므로, $O(\frac{1 + \sqrt{5}}{2} ^n)$의 시간복잡도가 소요된다. dp를 이용해 계산할 경우 $O(n)$의 시간복잡도가 걸린다. 두 방식으로 모두 위의 문제를 풀 수 없다.

참고로, 피보나치 수열은 일반항이 $Fib(n) = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$임이 알려져 있긴 하지만, n에 10^18을 넣어서 실수 오차나 오버플로우 문제 없이 문제를 풀 수 없다.

피보나치 수열 말고 다른 수열은 같은 방식으로 log만에 계산할 수 없을까? 내적의 형태로 표현 가능한 최고차가 1인 다항식은 모두 행렬을 이용해서도 표현할 수 있음이 알려져 있다. 따라서 다른 수열도 한 번 구해보자.

https://www.acmicpc.net/problem/1160(easy)와

https://www.acmicpc.net/problem/17118(hard)이다. 위 문제를 기준으로 설명하겠다.