[백준/C,C++] 10830번: 행렬 제곱

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

hackids.tistory.com/52

[백준/C,C++] 1629번: 곱셈

hackids.tistory.com/55

[백준/C,C++] 2740번: 행렬 곱셈

1629번: 곱셈, 2740번: 행렬 곱셈을 풀 수 있다면 충분히 풀 수있는 문제입니다.

 

행렬 A가 있을 때, $A^{B}$는 B가 짝수일 때, $A^{B/2} \times A^{B/2}$로 나타낼 수 있습니다.

 

홀수 일땐 $A^{B-1} \times A$로 나타낼 수 있습니다.

 

#include<iostream>

using namespace std;

const int MOD = 1000;
const int MAX = 5;

using ll = long long;
using Matrix = struct {
    int mat[MAX][MAX];
};

ll n, b;

void io(Matrix& m, char c)
{
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (c == 'i') cin >> m.mat[i][j];
            else cout << m.mat[i][j] % MOD << " ";
        }
        if (c == 'o') cout << "\n";
    }
}

Matrix operator*(const Matrix& a, const Matrix& b)
{
    Matrix tmp;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tmp.mat[i][j] = 0;
            for (int k = 0; k < n; k++) {
                tmp.mat[i][j] += a.mat[i][k] * b.mat[k][j];
            }
            tmp.mat[i][j] %= MOD;
        }
    }
    return tmp;
}

Matrix power(const Matrix& m, ll num)
{
    if (num == 1) return m;
    if (num % 2 != 0) {
        return power(m, num - 1) * m;
    }
    Matrix half = power(m, num / 2);
    return half * half;
}

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

    Matrix m;

    io(m, 'i');
    m = power(m, b);
    io(m, 'o');

    return 0;
}

 

함수 io는 행렬 입출력 함수입니다.

 

행렬 곱셈은 연산자 오버로딩을 통해 해결하였습니다.

 

power는 지수를 분할해 재귀호출하고 분할한 행렬을 곱해 반환합니다.