BOJ 10830

행렬 제곱 성공

 

 

1 초

256 MB

23784

8324

6628

34.033%

문제

크기가 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제곱한 결과를 출력한다.

예제 입력 1 복사

2 5
1 2
3 4

예제 출력 1 복사

69 558
337 406

예제 입력 2 복사

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2 복사

468 576 684
62 305 548
656 34 412

예제 입력 3 복사

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3 복사

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512​

거듭제곱 분할하는 문제라 따로 어려운건 없었고, 행렬 곱셈만 해주면 되는데

왜인지 계속 안되서 코드를 세번이나 다시짰다.

화난다

 

코드는 power mod 2가 1일때는 power -1로 재귀를 돌려

A^P(power)/2 * A^P/2 * A가 될 수 있게 해주었고

0일때는 바로 power/2를 넣어

A^P/2 * A/P/2로 분할해주었다.

 

logB의 연산이므로 시간은 문제가 없다. 다만 B가 100000000000까지 이므로 longlong을 써줘야 한다는 점을 주의하자.

 

 

#include <iostream>
using namespace std;
long long N, B;
long long A[6][6], NA[6][6];
void func(long long power){
    if(power == 1)
        return;
    else if(power%2 == 0){
        func(power/2);
        long long check[6][6];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++){
                check[i][j] = 0;
                for(int k=0; k<N; k++)
                    check[i][j] += (A[i][k]*A[k][j])%1000;
            }
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                A[i][j] = check[i][j]%1000;
    }else{
        func(power-1);
        long long check[6][6];
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++){
                check[i][j] = 0;
                for(int k=0; k<N; k++)
                    check[i][j] += (A[i][k]*NA[k][j])%1000;
            }
        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++)
                A[i][j] = check[i][j]%1000;        
    }
    
}
int main(){
    cin>>N>>B;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++){
            cin>>A[i][j];
            NA[i][j] = A[i][j];
        }
    
    func(B);

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