[백준 5095번] Matrix Powers (C++)

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

5095번: Matrix Powers

10830 행렬제곱 문제와 똑같은 문제다.

 

알고리즘 포스팅에서 분할정복을 주제로 한 포스팅이 있었는데, 마지막 부분에 분할정복 연습문제로 분할정복을 이용한 거듭제곱 유형을 소개했었다.

큰 수의 거듭제곱을 계산할 때, 분할정복을 사용한다는 사실이 Matrix power에서도 똑같이 적용된다. 따라서 앞선 개념을 알고 있으면 행렬제곱만 구현할 줄 알면 끝.

(큰 수의 거듭제곱 계산을 다뤄보지 않았다면 포스팅을 참고 문제를 풀면 잘 풀릴 것이다.)

 

 

#include <iostream>
#include <cstring>
#define endl "\n"
#define lint long long
using namespace std;

int n,m,p;

struct tmp {
	lint arr[101][101];
};

tmp operator*(tmp a, tmp b){
	tmp c;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			c.arr[i][j] = 0;
			for(int k = 0; k < n; k++){
				c.arr[i][j] += (a.arr[i][k] * b.arr[k][j]);
				c.arr[i][j] %= m;
			}
		}
	}
	return c;
}

int main() {
	while(true){
		tmp matrix, ans;
		memset(ans.arr,0,sizeof(ans.arr));
		cin >> n >> m >> p;
		if(!n && !m && !p) break;
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cin >> matrix.arr[i][j];
			}
			ans.arr[i][i] = 1;
		}
		
		while(p){
			if(p&1) ans = ans * matrix;
			matrix = matrix * matrix;
			p >>= 1;
		}
		
		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				cout << ans.arr[i][j] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}
}