[C++] BAEKJOON 10830 행렬 제곱

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

 

2740번: 행렬 곱셈

행렬을 제곱하는 문제입니다. B 범위가 100,000,000,000 까지 이기 때문에 곱셈을 여러 번 한다면 시간복잡도에 걸리게 됩니다. 따라서 행렬에 대해서 분할 정복을 통해서 제곱을 수행합니다. 그리고 행렬의 곱셈을 하는 함수 matrixMul와 단위 행렬 ones 를 활용하였습니다. 행렬의 곱 함수 matrixMul 는 매 값마다 1000 으로 나눈 나머지를 구해주었습니다.

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int> > ones(5, vector<int> (5));

vector<vector<int> > matrixMul(vector<vector<int> > &a, vector<vector<int> > &b){
    int n = a.size();

    vector<vector<int>> c(n, vector<int>(n));
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            for (int k=0;k<n;k++){
                c[i][j] += a[i][k]*b[k][j];
            }
            c[i][j] %= 1000;
        }
    }
    return c;
}

vector<vector<int>> matrixPow(vector<vector<int>> &a, long long B){
    if(B == 0) return ones;
    else if(B == 1) return a;
    else if (B % 2 == 0){
        vector<vector<int>> temp = matrixPow(a,B/2);
        return matrixMul(temp, temp);
    }
    else {
        vector<vector<int>> temp = matrixPow(a,B-1);
        return matrixMul(temp, a);
    }
}

int main(){
    int N;
    long long B;

    cin >> N >> B;

    vector<vector<int>> a(N, vector<int> (N));
    vector<vector<int>> answer(N, vector<int> (N));


    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cin >> a[i][j];
        }
        ones[i][i] = 1;
    }

    answer = matrixPow(a, B);

    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            cout << answer[i][j] % 1000 << " ";
        }
        cout << "\n";
    }
}

마지막 answer 행렬을 출력할 때 처음에는 1000 으로 나누어주지 않았습니다. 그 결과,

// input
2 1
1000 1000
1000 1000
  
// output
1000 1000
1000 1000
  
// answer
0 0
0 0

많은 분들이 이 테스트 케이스에서 틀리시는 거 같아서 추가합니다.