알고리즘/백준

백준 BOJ 10830 행렬제곱

등반 2022. 1. 18. 23:24

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

 

10830번: 행렬 제곱

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

www.acmicpc.net

문제 해설

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

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;
}

 

'알고리즘 > 백준' 카테고리의 다른 글

백준 BOJ 2824 최대공약수  (0) 2022.01.17
백준 BOJ 9711 피보나치  (0) 2022.01.16
백준 BOJ 1948 임계경로  (0) 2022.01.15
백준 BOJ 4386 별자리 만들기  (0) 2022.01.07
백준 BOJ 12850 본대 산책2  (0) 2022.01.05