백준 알고리즘 5095번 : Matrix Powers

링크

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

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>>;
int mod;

matrix operator *(const matrix a,const matrix b){
  int sz = a.size();
  matrix ret = vector(sz,vector<int>(sz));
  for(int i = 0; i < sz; i++){
    for(int j = 0; j < sz; j++){
      for(int k = 0; k < sz; k++){
        ret[i][j] += (a[i][k] * b[k][j]);
      }
      ret[i][j] %= mod;
    }
  }
  return ret;
}

matrix power(matrix a,int n){
  const int sz = a.size();
  matrix ret = vector(sz,vector<int>(sz));
  for(int i = 0; i < sz; i++) ret[i][i] = 1; // 단위 행렬
  while(n){
    if(n & 1) ret = ret * a;
    n >>= 1;
    a = a * a;
  }
  return ret;
}

int32_t main() {
  fastio;
  int n,k;
  while(cin >> n >> mod >> k && n != 0){
    matrix a = vector(n,vector<int>(n));
    for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) cin >> a[i][j];
    auto ans = power(a, k);
    for(int i = 0; i < n; i++){
      for(int j = 0; j < n; j++){
        cout << ans[i][j] << ' ';
      }
      cout << "\n";
    }
    cout << "\n";
  }
}

행렬의 거듭제곱을 구현해주면 됩니다.
거듭제곱을 할 때에는 분할정복을 이용한 거듭제곱(O(logN))을 사용해주면 됩니다