[백준 10830] 행렬 제곱

알고스팟 빠른 행렬 거듭 제곱을 사용할 일이 생겨
이전에 배운 내용이지만 제대로 이해하지 못한 것 같아 문제를 풀어보자는 마음에 풀게되었습니다.

문제링크 입니다

이 문제에서 A^N을 A * A * A * A * A * A * A * N 이렇게 구하면 O(N)의 시간복잡도가 걸린다.

• 이를 해결하기 위해 빠른거듭제곱 알고리즘을 사용하여 O(logN)의 타임에 답을 내는 빠른 거듭제곱을 사용한다.

[빠른 거듭제곱] O(logN)

• N이 홀수이면 A^N을 A^(N-1)로 바꾸고 A를 결과값에 곱한다.
• N이 짝수이면 A^N을 (A^N/2)*(A^N/2) 즉 A를 제곱하기 N을 2로 나누어 문제를 해결한다.

[10830 행렬 제곱] 문제

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

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

입력 예제

2 5
1 2
3 4

3 3
1 2 3
4 5 6
7 8 9

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

출력 예제

69 558
337 406

468 576 684
62 305 548
656 34 412

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

전체 코드는 다음과 같습니다.

//
//  10830.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/14.
//

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;
ifstream fin("10830_baekjoon.txt");

class Matrix{
private:
    vector<vector <long long> > v;
    int m_size;
public:
    Matrix(int n, vector<vector<long long >> v2) : m_size(n){
        v.resize(m_size, vector<long long>(m_size,0));
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                v[i][j] = v2[i][j];
            }
        }
    };
    Matrix(int n) : m_size(n){
        v.resize(m_size, vector<long long>(m_size,0));
    };

    Matrix Identity(){
        Matrix result(m_size);
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                if(i==j) result.v[i][j] = 1;
                else result.v[i][j] = 0;
            }
        }
        return result;
    };

    Matrix operator*(Matrix &M){
        Matrix result(m_size);
        for(int i=0; i< m_size; i++){
            for(int j=0; j< m_size; j++){
                for(int k=0; k< m_size; k++){
                    result.v[i][j] += (v[i][k] * M.v[k][j]);
                }
                result.v[i][j] %= 1000;
            }
        }
        return result;
    };

    Matrix pow(long long k){
        if(k == 0) return Identity();
        Matrix result(m_size);
        // 홀
        if(k % 2 == 1) return pow(k-1)**this;
        Matrix half = pow(k/2);
        return half*half;
    };
    /*
    long long operator[](int i){
        return v[i][0];
    }
    */
    void PrintMatrix(){
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                cout << v[i][j] << " ";
            }
            cout << endl;
        }
    }
    /*
    Matrix& operator=(const Matrix &M2){
        for(int i=0; i<m_size; i++){
            for(int j=0; j<m_size; j++){
                this->v[i][j] = M2.v[i][j];
            }
        }
        return *this;
    }
    */
};




int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N;
    long long B;
    fin >> N >> B;
    vector<vector<long long > > arr(N, vector<long long>(N,0));

    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++){
            fin >> arr[i][j];
        }
    }

    Matrix matrix(N,arr);
    matrix.pow(B).PrintMatrix();
}