[백준 11444] 피보나치 수 6 C++

11444번 - 피보나치 수 6

문제 이해

n번째 피보나치 수를 $ 1,000,000,007 $로 나눈 나머지를 구하는 문제.
$ 0 \leq n \leq 1,000,000,000,000,000,000$

접근

시간 제한 1초 내에 동적 계획법을 이용한 시간복잡도 $O(N)$의 방법으로는 해결이 불가능하다.
피보나치 수의 점화식을 행렬로 표현하면 다음과 같다.

\[\left[ \begin{matrix} F_{n+2}\\ F_{n+1}\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right] \left[ \begin{matrix} F_{n+1}\\ F_{n}\\ \end{matrix} \right]\]

이를 정리하면

\[\left[ \begin{matrix} F_{n+2} & F_{n}\\ F_{n} &F_{n-1}\\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right]^n\]

로 나타 낼 수 있고, 행렬 제곱을 통해 $F_n$을 구해 낼 수 있다.

정답 코드

#include <bits/stdc++.h>
#define REP(i, x, y) for (int i = x; i < y; i++)
#define MOD 1000000007

using namespace std;
typedef long long ll;

typedef vector<vector<ll>> matrix;

matrix operator*(matrix& a, matrix& b) {
  matrix r(2, vector<ll>(2));
  REP(i, 0, 2) {
    REP(j, 0, 2) {
      REP(k, 0, 2) r[i][j] += a[i][k] * b[k][j];
      r[i][j] %= MOD;
    }
  }
  return r;
}

void solve() {
  ll n;
  cin >> n;
  matrix result = {{1, 0}, {0, 1}};
  matrix a = {{1, 1}, {1, 0}};
  while (n > 0) {
    if (n % 2)
      result = result * a;
    a = a * a;
    n /= 2;
  }
  cout << result[1][0];
}


int main() {
  solve();
  return 0;
}