[BOJ] 백준 10830 - 행렬 제곱

문제 링크

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

풀이

$b$가 너무 큽니다. 백준 1629 - 곱셈 문제와 같은 테크닉을 이용해 거듭제곱 시간을 줄여줍시다.

행렬 곱셈의 경우 vector<vector<long long>> 타입의 곱셈 연산을 오버로딩해주면 편합니다.

 

1000으로 나눈 답을 출력해야 하는데, 초기 행렬 값이 1000이고 $b$=1인 경우를 주의해주세요. 입력받을 때도 1000으로 나눠주어야 합니다.

정답 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
const ll MOD = 1'000;

ll n, b;
vvll p;

vvll operator*(vvll &x, vvll &y) {
    vvll ret(n, vll(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                ret[i][j] += x[i][k] * y[k][j];
                ret[i][j] %= MOD;
            }
        }
    }
    return ret;
}

vvll go(ll k) {
    if (k == 1) return p;
    if (k & 1) {
        auto ret = go(k - 1);
        return ret * p;
    }
    auto ret = go(k / 2);
    return ret * ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> b;
    p.resize(n, vll(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> p[i][j];
            p[i][j] %= MOD;
        }
    }
    vvll ans = go(b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }
}