n이 5라 했을 때
n&1 == 1 -> ans = a, a = a^2 // n/=2 -> 2
n&1 != 1 -> a = a^2 // n/=2 -> 1
n&1 == 1 -> ans = ans a -> a a^4 = a^5, a = a^8
n이 홀수 일때만 ans에 곱해주면 해당 제곱수를 구할 수 있다.
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000
typedef long long ll;
typedef vector<vector<ll>> matrix;
ll n, m;
matrix operator *(matrix& a, matrix& b) {
matrix temp(n, vector<ll>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
temp[i][j] += a[i][k] * b[k][j];
}
temp[i][j] %= MOD;
}
}
return temp;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
matrix a(n, vector<ll>(n)), ans(n, vector<ll>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> a[i][j];
}
// 단위 행렬 사용
ans[i][i] = 1;
}
while (m) {
if (m & 1)ans = ans * a;
a = a * a;
m /= 2;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cout << ans[i][j] << ' ';
}
cout << '\n';
}
return 0;
}