[Gold 4] 10830 행렬 제곱

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

 

지수가 int 값 범위를 초과할 수 있으므로 거듭 제곱을 하는 과정에서 시간 초과가 발생할 수 있다.

 

이는 지수 법칙과 나머지 연산의 성질을 이용해서 해결할 수 있다.

지수법칙
a^(n + m) = a^n + a^m

모듈러 성질
(a x b) mod c = (a mod c x b mod c) mod c
(a * b) % c = (a % c * b % c) % c

 

지수 법칙 이용 방법

짝수인 경우
a^8 = a^4 * a^4
    = (a^2 * a^2) * (a^2 * a^2)
    = ((a^1 * a^1) * (a^1 * a^1)) * ((a^1 * a^1) * (a^1 * a^1))
    
홀수인 경우
a^9 = a^4 * a^4 * a
    = (a^2 * a^2) * (a^2 * a^2) * a
    = ((a^1 * a^1) * (a^1 * a^1)) * ((a^1 * a^1) * (a^1 * a^1)) * a

위와 같이 지수를 반으로 나누면서 활용할 수 있다.

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

 

 

 

#include <iostream>
using namespace std;

long long N, B;
long long matrix[5][5];
long long answer[5][5];
long long sum[5][5];

void calc(long long x[5][5], long long y[5][5]){
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            sum[i][j] = 0;
            for(int k = 0;k<N;k++){
                sum[i][j] += x[i][k] * y[k][j];
            }
            sum[i][j] %= 1000;
        }
    }
    for(int i = 0;i<N;i++)
        for(int j = 0;j<N;j++)
            x[i][j] = sum[i][j];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>N>>B;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++)
            cin>>matrix[i][j];
        answer[i][i] = 1; // 단위 행렬
    }

    while(B > 0){ // 5 -> 2 -> 1
        if(B % 2 == 1){
            // 홀수 인 경우 정답행렬에 A행렬 곱
            calc(answer, matrix);     
        }
        // 지수법칙 사용 
        calc(matrix, matrix);

        B /= 2;
    }

    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++)
            cout<<answer[i][j]<<' ';
        cout<<'\n';
    }
}