BOJ 10830: 행렬 제곱 작성일 2020-02-21 https://www.acmicpc.net/problem/10830 2월동안 187문제 풀기(지난달 누적 87개) (42/187) 행렬 곱셈방법 기억하기, 앞선 문제랑 동일한 pow 구현 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include <bits/stdc++.h> using namespace std; long long N, B; struct Mat { vector<vector<int>> arr; Mat() { arr.resize(N, vector<int>(N)); } Mat operator*(Mat& b) { Mat ans; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) for(int k = 0; k < N; k++) { int tmp = (arr[i][k] * b.arr[k][j]) % 1000; ans.arr[i][j] = (ans.arr[i][j] + tmp) % 1000; } return ans; } Mat& operator=(Mat b) { for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) arr[i][j] = b.arr[i][j]; return *this; } void print() { for(int i = 0; i < N; i++) { for(int j = 0; j < N; j++) cout << arr[i][j] << " "; cout << "\n"; } } }; Mat pow(Mat A, long long e) { Mat ret; for(int i = 0; i < N; i++) ret.arr[i][i] = 1; while(e) { if(e&1) ret = ret * A; e /= 2; A = A * A; } return ret; } int main() { ios::sync_with_stdio(false); cin >> N >> B; Mat A; for(int i = 0; i < N; i++) for(int j = 0; j < N; j++) cin >> A.arr[i][j]; pow(A, B).print(); return 0; }