[백준][Python] 11444 피보나치수6 - 행렬의 곱셈

행렬의 곱셈을 연습하는 문제이다. 각 항을 어떻게 표현 할 것인가?

2x2 행렬의 i행 j열의 요소는 두개의 요소의 곱이 두개씩 합해져 들어간다.

 

def matrix_mult(a, b):
    ret = [[0 ,0], [0, 0]]
    for i in range(2):
        for j in range(2):
            for k in range(2):
                ret[i][j] += (a[i][k] * b[k][j]) % MOD
    return ret


n = bin(int(input()))[2:]

MOD = 1000000007
base = [[1, 1], [1, 0]]
answer = [[1, 0], [0, 1]]

for i in range(1, len(n) + 1):
    if n[-i] == '1':
        answer = matrix_mult(answer, base)
    base = matrix_mult(base, base)
        
print(answer[0][1] % MOD)