[BOJ 10830] 행렬 제곱 (Java)

문제

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

10830번: 행렬 제곱

 

풀이

밑이 같은 두 거듭제곱의 곱은 밑은 그대로 쓰고 지수만 더해준다는 지수법칙을 활용한다. 

예를 들어 2의 10제곱은 2^10 = 2^5 * 2^5 로 분할 할 수 있다. 

그러면 2를 10번 곱하는게 아닌 2를 5번 곱한 값을 가져와서 제곱을 하면 된다. 

2^5 또한 아래와 같이 분할 할 수 있다.

2^5 = 2^2 * 2^2 * 2

 

이렇게 지수의 거듭제곱을 절반 씩 분할 하면서 제곱 계산의 수를 현저히 줄일 수 있다. 

 

소스코드

package divideconquer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ10830 {

    public static int N;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        long B = Long.parseLong(st.nextToken());
        long[][] arr = new long[N][N];
        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                arr[i][j] = Long.parseLong(st.nextToken());
            }
        }

        long[][] answer = pow(arr, B);
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                System.out.print(answer[i][j]%1000 + " ");
            }
            System.out.println();
        }

    }

    public static long[][] pow(long[][] base, long B){
        if(B == 1) return base;
        long[][] temp = null;
        if(B % 2 == 0) {
            temp = pow(base, B/2);
            return multiply(temp, temp);
        } else {
            temp = pow(base,(B-1)/2);
            return multiply(base, multiply(temp, temp));
        }
    }

    public static long[][] multiply(long[][] arr1, long[][] arr2){
        long[][] answer = new long[N][N];
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                long ans = 0;
                for(int k = 0; k < N; k++){
                    ans += arr1[i][k]*arr2[k][j]%1000;
                }
                answer[i][j] = ans%1000;
            }
        }
        return answer;
    }
}