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 |