[코테] 2206 - 피보나치 행렬연산

📌 [BOJ 11444] 피보나치 수 6

✅ 왜?

일반 DP 피보나치는 O(N)
입력 최대 N = 10¹⁸ → O(N) 불가
반드시 O(log N)으로 풀어야 함

✅ 이유

피보나치는 점화식이 있다:

$$ F(n) = F(n-1) + F(n-2) $$

이걸 행렬로 바꿀 수 있다:

$$ \begin{bmatrix} F(n) \\\\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\\\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} F(1) \\\\ F(0) \end{bmatrix} $$

거듭제곱 분할로 행렬 거듭제곱을 O(log N)으로 처리할 수 있다.

✅ 그래서 이렇게 함

1. 기본 2×2 행렬:
   $$ A = \begin{bmatrix} 1 & 1 \\\\ 1 & 0 \end{bmatrix} $$
2. 행렬 거듭제곱:
   짝수: \( A^n = (A^{n/2})^2 \)
   홀수: \( A^n = A^{n-1} \times A \)
3. 단위 행렬:
   $$ I = \begin{bmatrix} 1 & 0 \\\\ 0 & 1 \end{bmatrix} $$
   지수가 0이면 단위 행렬 반환
4. 기본 벡터: [1, 0]
5. 곱셈 시 MOD를 반드시 중간에 나눠서 큰 수 연산 최적화

✅ 핵심 주의

- 중간 곱셈에 MOD 없으면 시간 초과!
- 파이썬 큰 수 곱셈은 느리므로 반드시 나머지로 잘라서 연산량 줄이기

🟢 핵심 코드

MOD = 10**9 + 7

def mat_mul(A, B):
    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]) % MOD
                result[i][j] %= MOD
    return result

def fast_pow(mat, exp):
    if exp == 0:
        return [[1, 0], [0, 1]]
    if exp == 1:
        return mat

    if exp % 2 == 0:
        half = fast_pow(mat, exp // 2)
        return mat_mul(half, half)
    else:
        half = fast_pow(mat, exp - 1)
        return mat_mul(half, mat)

base = [[1, 1], [1, 0]]
result = fast_pow(base, n - 1)

vector = [1, 0]
answer = [0, 0]
for i in range(2):
    for j in range(2):
        answer[i] += result[i][j] * vector[j]
        answer[i] %= MOD

print(answer[0])

이렇게 하면 피보나치 수를 O(log N)으로 구할 수 있다! 🚀