백준 알고리즘 11524번 : Immortal Porpoises

링크

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

sol1) 수학

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

using matrix = vector<vector<int>>;
const int mod = 1e9;

matrix operator * (const matrix &a, const matrix &b) {
  int size = a.size();
  matrix res(size, vector<int>(size));
  for (int i = 0; i < size; i++) {
      for (int j = 0; j < size; j++) {
          for (int k = 0; k < size; k++) {
              res[i][j] += a[i][k] * b[k][j];
          }
          res[i][j] %= mod;
      }
  }
  return res;
}
 
matrix power(matrix a, int n) {
  int size = a.size();
  matrix res(size, vector<int>(size));
  for (int 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;
}

int32_t main() {
  fastio;
  int tc; cin >> tc;
  while(tc--){
    matrix baseFibo = {{1,1},{1,0}};
    int n,temp; cin >> temp >> n;
    auto ans = power(baseFibo, n);
    cout << temp << ' ' << ans[0][1] << "\n";
  }
}