[백준 10830번] 행렬 제곱 - (빠른 거듭제곱 알고리즘)

문제 링크: https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

<문제 풀이> 행렬, 선형대수학

 

이 문제에서 A ^ N을 A* A* A*.... A*N 이렇게 구하면 O(N)의 시간 복잡도가 걸리므로 시간 초과가 나게 됩니다. 따라서 O(logN)의 시간 복잡도에 거듭제곱을 할 수 있는 알고리즘을 사용해야 됩니다.

 

<빠른 거듭제곱 알고리즘> O(logN)

-----------------------------------------------------------------------------

N이 홀수이면 A^N을 A * A^(N-1)로 바꾸고 A를 결과값에 곱한다

 

N이 짝수이면 A^N을 (A^2)^(N/2) 즉 A를 제곱하고 N을 2로 나눈다

 

N = 0 이면 종료

-----------------------------------------------------------------------------

 

2^5를 구하는걸 예로 들어보겠습니다.

n = 5

res = 1

 

2^5 = 2 * 2^4  (n이 홀수일 때 밑을 하나 꺼내서 n을 짝수로 만든다) -> n = 4

res = res * 2; (꺼낸 수를 결과값에 저장한다) res = 2

 

2^4 = (2^2)^2 = 4^2 (n이 짝수일 때 밑을 제곱하고 n을 2로 나눈다) -> n = 2

 

4^2 = 16^1 (n이 짝수일때 밑을 제곱하고 n을 2로 나눈다) -> n = 1

 

16^1 = 16 * 16^0 = 16 (n이 홀수일 때 밑을 하나 꺼내서 n을 짝수로 만든다) -> n = 0

res = res * 16; (꺼낸 수를 결과값에 저장한다) res = 32

 

n == 0이면 종료

 

 

행렬을 제곱할 때도 이 알고리즘을 사용하면 됩니다.

 

<c++ 소스 코드> 

#include <iostream>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef vector<vector<ll> > matrix;
 
matrix operator * (const matrix &a, const matrix &b) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            for (ll k = 0; k < size; k++) {
                res[i][j] += a[i][k] * b[k][j];
            }
            res[i][j] %= 1000;
        }
    }
    return res;
}
 
matrix power(matrix a, ll n) {
    ll size = a.size();
    matrix res(size, vector<ll>(size));
    for (ll i = 0; i < size; i++) { // 단위 행렬
        res[i][i] = 1;
    }
    while (n > 0) {
        if (n % 2 == 1) {
            res = res * a;
        }
        n /= 2;
        a = a * a;
    }
    return res;
 
}
 
void PrintMatrix(const matrix& a) {
    ll size = a.size();
    for (ll i = 0; i < size; i++) {
        for (ll j = 0; j < size; j++) {
            cout << a[i][j] << " ";
        }
        cout << '\n';
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n, b;
    cin >> n >> b;
    matrix a(n, vector<ll>(n));
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < n; j++) {
            cin >> a[i][j];
        }
    }
    PrintMatrix(power(a,b));
 
    return 0;
}