행렬을 이용한 피보나치 수열 문제의 해법

1. 피보나치 수열의 행렬 표현

 

피보나치 수열의 점화식은 다음과 같다.

 

$a_{n+1} = a_{n} + a_{n-1}$

 

$a_{n} = a_{n} + 0$

 

따라서 행렬로 나타내면 다음과 같다

 

$$\begin{pmatrix}
a_{n+1} \\
a_{n}
\end{pmatrix}=\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}\begin{pmatrix}
a_{n} \\
a_{n-1}
\end{pmatrix}$$

 

n = 1부터 반복적으로 곱해보면...

 

$$\begin{pmatrix}
a_{2} \\
a_{1}
\end{pmatrix}=\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}\begin{pmatrix}
a_{1} \\
a_{0}
\end{pmatrix}$$

 

n = 2이면...

 

$$\begin{pmatrix}
a_{n+1} \\
a_{n}
\end{pmatrix}=\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}\begin{pmatrix}
a_{1} \\
a_{0}
\end{pmatrix}$$

 

정리하면 다음과 같다.

 

$$\begin{pmatrix}
a_{2} \\
a_{1}
\end{pmatrix}=\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^{2}\begin{pmatrix}
a_{1} \\
a_{0}
\end{pmatrix}$$

 

따라서 일반적인 n에 대하여 다음과 같을 것이다.

 

$$\begin{pmatrix}
a_{n+1} \\
a_{n}
\end{pmatrix}=\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^{n}\begin{pmatrix}
a_{1} \\
a_{0}
\end{pmatrix}$$

 

$a_{1}$과 $a_{0}$은 기본적으로 주어지므로,

 

우리는 행렬

 

$$\begin{pmatrix}
1 & 1 \\
1 & 0 \\
\end{pmatrix}^{n}$$

 

 

을 구하면 된다.

 

그리고 나서 n번째 피보나치 항은 $a_{n}$이고 이것을 구해야한다.

 

n제곱한 행렬과

 

$$\begin{pmatrix}
a_{1} \\
a_{0}
\end{pmatrix}$$

 

을 곱해야하는데 $a_{1} = 1$, $a_{0} = 0$이므로

 

결국 n제곱한 행렬의 (1,0) 원소가 구하고자 하는 n번째 피보나치 항이다.

 

행렬의 거듭제곱을 구하는 방법은 이미 배웠다

 

ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 - (tistory.com)

ABC 293 복기 E - Geometric Progression - 행렬곱 배우기 -

 

2. 문제

 

11444번: 피보나치 수 6 (acmicpc.net)

11444번: 피보나치 수 6

 

이미 배운 행렬의 거듭제곱을 구현하고 (1,0)원소를 구하면 된다

 

from sys import stdin

def matrix_multiplication(a,b,mod):
    
    result = [[0,0],[0,0]]

    for i in range(2):
        
        for j in range(2):
            
            for k in range(2):
                
                result[i][j] += a[i][k]*b[k][j]

                result[i][j] %= mod
    
    return result

def matrix_exponentiation(m,n,mod):
    
    result = [[1,0],[0,1]]

    while n > 0:
        
        if n % 2 == 1:
            
            result = matrix_multiplication(result,m,mod)
        
        m = matrix_multiplication(m,m,mod)
        n //= 2
    
    return result

n = int(stdin.readline())

matrix = [[1,1],[1,0]]

mod = 1000000007

result = matrix_exponentiation(matrix,n,mod)

print(result[1][0])

 

 

피보나치 수를 구하는 여러가지 방법 (acmicpc.net)

피보나치 수를 구하는 여러가지 방법

 

 

피보나치 수열을 구하는 효율적인 방법 (tistory.com)

피보나치 수열을 구하는 효율적인 방법