백준 BOJ 10830 행렬제곱

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

10830번: 행렬 제곱

문제 해설

단순히 행렬 제곱을 구하는 문제다.

B가 크므로 행렬의 제곱을 분할 정복하도록 한다.

주의할 점은 아래 두 가지다.

1. B가 매우 큰 수 이므로 long long으로 받아야 한다는 것

2. 각 원소를 1,000으로 나눈 나머지를 출력하는 것

 

#include <iostream>
#define fio cin.tie(0)->sync_with_stdio(0);

using namespace std;

#include <vector>
#include <map>

map<long long, vector<vector<int> > > map_mat;

vector<vector<int> > mat_multi(const vector<vector<int> >&A, const vector<vector<int> >&B){
	int size = A.size();
	vector<vector<int> > ret(size, vector<int>(size, 0));
	for(int i=0; i<size; i++){
		for(int k=0; k<size; k++){
			for(int j=0; j<size; j++){
				ret[i][k] += (A[i][j] * B[j][k])%1000;
			}
			ret[i][k] %= 1000;
		}
	}
	return ret;
} 

void print_mat(const vector<vector<int> >& A){
	int N = A.size();
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			cout << A[i][j] <<' ';
		}cout <<'\n';
	}
}

bool is_exist(long long N){
	if(map_mat.find(N) != map_mat.end()){
		return true;
	}
	return false;
}

vector<vector<int> > get_sq_mat(long long N, const vector<vector<int> >& A){
	if(is_exist(N)){
		return map_mat[N];
	}
	//
	if(N % 2 == 0){
		map_mat[N/2] = get_sq_mat(N/2, A);
		return map_mat[N] = mat_multi(map_mat[N/2], map_mat[N/2]);
	}else{
		map_mat[N-1] = get_sq_mat(N-1, A);
		return map_mat[N] = mat_multi(A, map_mat[N-1]);
	}
}

int main() {
	fio;
	//입력
	int N; long long B; cin >> N >> B;
	vector<vector<int> >mat(N, vector<int>(N, 0));
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			cin >> mat[i][j];
			mat[i][j] %= 1000;
		}
	}
	//dp 기저사례
	map_mat[1] = mat;
	//B번 제곱
	vector<vector<int> >ret = get_sq_mat(B, mat);
	//print
	print_mat(ret);

	return 0;
}