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

 

www.acmicpc.net/problem/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제곱한 결과를 출력한다.

 

지수가 int형 최댓값보다 더 큰 숫자도 가능하므로

거듭제곱하는 과정이나 모듈러 연산에서 시간초과가 날 것이다.

 

이는 '지수 법칙'과 '모듈러 성질'로 해결이 가능하다.

지수법칙

모듈러 성질

이를 연산자 식으로 표현하면,

이와 같다.

 

 

1. 지수법칙 이용

 1 ) 짝수일 경우, 

 

 2) 홀수일 경우, 

이런 식으로 지수를 반으로 나누며 활용할 수 있다.

지수를 2로 나누게 되면 지수가 짝수로 나오다가 1로 나오게 된다.

 

위에 예시를 보자면,

지수가 8인 경우, 8->4->2->1

지수가 9인 경우, 9->4->2->1

 

 

 

일단 지식은 여기까지 알면 응용만이 남아있다 !

#include<iostream>
using namespace std;

long long n, b;
long long a[5][5];
long long tmp[5][5];
long long ans[5][5];

// 행렬 곱셈
void Matrix_multi(long long x[5][5], long long y[5][5]) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            tmp[i][j] = 0; // 행렬 초기화
            for (int k = 0; k < n; k++) { //행렬 곱셈
                tmp[i][j] += (x[i][k] * y[k][j]);
            }

            tmp[i][j] %= 1000; //모듈러 곱셈
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            x[i][j] = tmp[i][j];
        }
    }
}

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

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
        }
        ans[i][i] = 1; // 정답행렬 단위행렬로 초기화
    }

    while (b > 0) { //5 -> 2 -> 1
        if (b % 2 == 1) { //홀수이면 정답행렬에 A행렬 곱
            Matrix_multi(ans, a); //ans: a -> a * a^4
        }
        Matrix_multi(a, a); //지수법칙 a: a^2 -> a^4
        b /= 2;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
}

해당 코드에서 단위행렬을 이용하는 방법은 2가지다.

홀수일 때, 바로 if 구문으로 들어가 A를 이용하기 위해 ans에 저장하는 것이다.

모든 경우, 지수가 1로 되기 때문에 if 구문으로 들어가 ans에 결과값을 저장하는 것이다.

 

지수를 2로 나누며 계산해주기 때문에

시간 복잡도는 O(logN)이다.