https://www.acmicpc.net/problem/5095
#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))을 사용해주면 됩니다