[C++] 백준/Gold/10830. 행렬 제곱

문제: 행렬 제곱(백준 10830번)

문제 분석

$N \times N$ 크기의 행렬을 $B$번 제곱한 결과를 출력하는 문제이다.

보통 이런 지문 자체가 간단한 문제들은 입력 범위가 특정 알고리즘을 사용해야 시간 초과가 나지 않도록 설계되어 있다. 이번 문제 역시 단순히 행렬 제곱을 반복적으로 계산하면 $O(N^3 \times B)$의 시간 복잡도를 가지므로 1000억 번의 연산이 필요하다. 따라서 시간 복잡도를 $O(\log B \times N^3)$ 수준으로 줄일 수 있는 알고리즘이 필요하다.

거듭 제곱을 이용한 행렬 제곱 알고리즘

거듭 제곱을 활용하면, 행렬을 효율적으로 제곱할 수 있다.
행렬 $M$을 $B$번 제곱하는 과정을 다음과 같이 분할 정복 방식으로 처리한다.

1. $B = 0$일 경우, 단위 행렬을 반환한다.
2. $B$가 홀수일 경우: $M^B = M \times M^{B-1}$
3. $B$가 짝수일 경우: $M^B = \left(M^{B/2}\right) \times \left(M^{B/2}\right)$

이 방식을 적용하면, 제곱 연산의 반복 횟수를 $O(\log B)$로 줄일 수 있다.

코드 전체

#include <bits/stdc++.h>
using namespace std;

class Matrix : public vector<vector<int>> {
public:
    Matrix operator *(const Matrix& a) const {
        int n = size();
        Matrix result;
        result.resize(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++) {
                    result[i][j] += at(i).at(k) * a[k][j];
                }
                result[i][j] %= 1000;
            }
        }
        return result;
    }
};

Matrix Power(Matrix m, long long b) {
    int n = m.size();
    Matrix result;
    result.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) result[i][i] = 1;

    while (b > 0) {
        if (b % 2 == 1) {
            result = result * m;
        }
        m = m * m;
        b >>= 1;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; long long b; cin >> n >> b;
    Matrix m; m.resize(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> m[i][j];
        }
    }

    Matrix result = Power(m, b);
    for (const auto& row : result) {
        for (int val : row) cout << val << ' ';
        cout << '\n';
    }
}