백준 10830번 : 행렬 제곱 - 재귀

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

10830번: 행렬 제곱

#include <bits/stdc++.h>

using namespace std;

long long N, B;

struct Matrix {
    int arr[6][6] = {0};
};

Matrix multiple(Matrix m1, Matrix m2) {
    Matrix tmp;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                tmp.arr[i][k] += (m1.arr[i][j] * m2.arr[j][k]) % 1000;
                tmp.arr[i][k] %= 1000;
            }
        }
    }
    return tmp;
}

Matrix power(Matrix A, long long b) {
    if (b == 1) return A;

    Matrix powered = power(A, b / 2);
    Matrix ret = multiple(powered, powered);
    if (b % 2 == 1) {
        ret = multiple(ret, A);
    }
    return ret;
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> B;

    Matrix matrix, ans;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> matrix.arr[i][j];
        }
    }

    ans = power(matrix, B);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cout << ans.arr[i][j] % 1000 << ' ';
        }
        cout << '\n';
    }


    return 0;
}