백준 알고리즘 7677번 : Fibonacci

링크

https://www.acmicpc.net/problem/7677

sol1) 행렬 곱

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
//#include <bits/extc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;
//using namespace __gnu_cxx;

using ll = long long;

typedef vector<vector<ll>> matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 10000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
void PrintMatrix(const matrix& a) {
    ll size = a.size();
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
}

int32_t main() {
  fastio;
  int n;
  matrix v = {{1,1},{1,0}};
  while(cin >> n && n != -1){
    auto ans = power(v, n);
    cout << ans[0][1] << "\n";
  }
  return 0;
}