10830번 : 행렬 제곱

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

10830번: 행렬 제곱

 

이 문제는 100,000,000,000번 곱해야하는 문제이다 . 즉 시간복잡도가 O(log n)이 아니면 불가능 하다.

그래서 분할 정복을 생각하였다.

문제 풀이는

제곱수가 n이라 하고 행렬 a가 있다고 할 때,

ex)n=10이라고 하자. 나는 재귀로 풀었기에 n은 1,2,4,5,10으로 올라가는 형태이다. 

즉 n=1일때 A

n=2일때 A*A=A^2

n=4일 떄 는  (A^2)*(A^2)=A^4

n=5일 때 는 기본행렬 곱이므로  (A^4)*A

n=10일 떄는 ((A^4)*A)*((A^4)*A)

이렇게 나온다.

 

즉 n%2==1이면 제곱 행렬에 기본행렬을 곱하고

n%2==0이면 제곱행렬을 두번 곱한다.

 

코드를 보면 이해가 될 것 이다.

#include <iostream>
using namespace std;
#define mod 1000
long long n,m;
long long matrix[6][6];
long long temp[6][6];
long long ans[6][6];
void divide(long long x){
    if(x==1){
        for(int i=0;i<n;i++){
            for(int k=0;k<n;k++){
                ans[i][k]=temp[i][k]%mod;
        }
    }
        return;
    }
    if(x%2==1){
        divide(x-1);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                ans[i][j]=0;
                for(int t=0;t<n;t++){
                    ans[i][j]+=temp[i][t]*matrix[t][j];              //홀수 이면 기본 행렬 곱해주기
                    
                }
                ans[i][j]%=mod;
            }
        }
        for(int i=0;i<n;i++){
            for(int k=0;k<n;k++){
                temp[i][k]=ans[i][k];                             //결과값 저장
        }
    }
        return;
    }
    divide(x/2);
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            ans[i][j]=0;
            for(int t=0;t<n;t++){
                ans[i][j]+=temp[i][t]*temp[t][j];                       //짝수이면 거듭곱 행렬 곱하기
            }
            ans[i][j]%=mod;
        }
    }
    for(int i=0;i<n;i++){
        for(int k=0;k<n;k++){
            temp[i][k]=ans[i][k];
        }
    }
    
}
int main(){
    cin >>n>>m;
    for(int i=0;i<n;i++){
        for(int k=0;k<n;k++){
            cin>>matrix[i][k];
            temp[i][k]=matrix[i][k];
        }
    }
    divide(m);
    for(int i=0;i<n;i++){
        for(int k=0;k<n;k++){
            cout <<ans[i][k]<<' ';
        }
        cout<<'\n';
    }
}