[백준 2749] 피보나치 수 3 C++

2749번 - 피보나치 수 3

문제 이해

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

접근

11444번 - 피보나치 수 6와 나머지 조건만 다른 문제.

정답 코드

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

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;
}