[백준] 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제곱한 결과를 출력한다.

 

 

행렬의 곱셈을 수행할 수 있는 함수를 정의하고, 지수 승을 나타내는 b의 크기가 굉장히 크기 때문에, 분할 정복을 이용해서 문제를 풀었습니다. n*n 같은 행렬을 제곱하는 형태이기 때문에 순서에 상관 없이 곱셈을 수행해줘도 됩니다. 

 

#include <iostream>
#include <vector>
using namespace std;

typedef vector<vector<int> > matrix;
matrix operator * (const matrix &a, const matrix &b) {
    int n = a.size();

    matrix ans(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++) {
                ans[i][j] += a[i][k] * b[k][j];
            }
            ans[i][j] %= 1000;
        }
    }
    
    return ans;
}

matrix calc(matrix a, long long exp) {
    int n = a.size();
    matrix ans(n, vector<int>(n));
    for (int i = 0; i < n; i++) ans[i][i] = 1;

    if (exp == 0) return ans;
    if (exp % 2) ans = ans * a;
    return ans * calc(a * a, exp / 2);
}

int main() {
    int n;
    long long b;
    cin >> n >> b;

    matrix a(n, vector<int>(n));

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> a[i][j];

    matrix ans = calc(a, b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}