[백준 / BOJ] 10830 행렬 제곱

문제

출처 : www.acmicpc.net/problem/10830

10830번: 행렬 제곱

크기가 N*N인 행렬A가 주어졌을때, 해당 행렬을 B제곱한 결과를 구하는 문제다. 수가 매우 커질수있으니 A^B의 각 원소를 1000으로 나눈 나머지를 출력한다.

 

풀이

B가 최대 100,000,000,000까지 가서 일반적인 곱셈(A*A*A*A*A)으로는 시간초과가 난다. 분할정복을 이용해 풀어야하는데,

A*A = A^2

A*A*A*A = A^2*A^2 = A^4

A*A*A*A*A*A*A*A = A^2*A^2*A^2*A^2 = A^4*A^4 = A^8

.

.

.

위와같이 거듭제곱의 성질을 이용해서 풀면된다. A의 8제곱은 A^4를 곱한것과 같으므로 굳이 A*A*A...를 해줄필요없이 A^4만 해주면된다. 즉, B를 1/2씩 줄여나가며 연산을 할수있다는 뜻인데, 이런식으로 연산하면 log(B)초만에 연산이 가능하다.

 

처음에는 곱셈 문제처럼 바텀업으로 양쪽으로 보내는 식으로 코드를 짰는데 시간초과가 났다. 

시간초과 소스코드

//
// xb205
// 2021.01.26
//

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll N, B, rem = 1000;
vector<vector<ll> > arr;
vector<vector<ll> > sumvec(vector<vector<ll> > vec1, vector<vector<ll> > vec2){
    vector<vector<ll> > answer(N+2, vector<ll>(N+2));
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            for(int l = 1; l <= N; l++){
                answer[i][j] += vec1[i][l] * vec2[l][j];
            }
            answer[i][j] %= 1000;
        }
    }
    return answer;
}

vector<vector<ll> > getvec(ll squ){
    if(squ == 1){
        return arr;
    }
    vector<vector<ll> > temp = getvec(squ/2);
    if(squ % 2 == 0){
        return sumvec(temp, temp);
    }
    else{
        return sumvec(sumvec(temp, temp), getvec(1));
    }
    return arr;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N >> B;
    arr.resize(N+2, vector<ll>(N+2));
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cin >> arr[i][j];
        }
    }
    vector<vector<ll> > print;
    print = getvec(B);
    for(int i = 1; i <= N; i++){
        for(int j = 1; j <= N; j++){
            cout << print[i][j] % rem << " ";
        }
        cout << "\n";
    }
    return 0;
}

이 문제는 양쪽으로 제곱/2 를 계산해서 곱하면 안되고, 한쪽으로만 제곱/2를 가져온후 그 값에 제곱을 해줘야한다.

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/10830%20%ED%96%89%EB%A0%AC%20%EC%A0%9C%EA%B3%B1/main.cpp

devxb/JJUNalgo