[PS] 백준 10830번 행렬 제곱

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

문제 설명

N x N 행렬 A 가 주어졌을 때, $A ^ B$ 의 각 원소를 1000으로 나눈 나머지를 출력하는 문제이다.
이 때, B <= 100,000,000,000 이다.

문제 풀이

B가 매우 크다. 어떤 수의 제곱을 구할 때 분할 정복이 유용함을 알고있다. 따라서 행렬의 제곱을 구할 때도 분할 정복을 사용하면 될 것이라는 생각을 할 수 있다. 기저조건은 B가 1일 때와 2일 때이다. 1인 경우는 원래 행렬을 원소 별로 1000으로 나눈 행렬을 반환, 2인 경우는 A와 A의 행렬곱을 반환하면 된다.

B % 2 == 0 인 경우 아래와 같다.

$A ^ B = ((A ^ {(B / 2)}) ^ 2)$

B % 2 != 0 인 경우 아래와 같다.

$A ^ B = ((A ^ {(B / 2)}) ^ 2)$ * A

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

    public class Main {

        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static StringTokenizer st;

        static int n;
        static long b;
        static int[][] matrix;
        static final int MOD = 1000;

        public static void main(String[] args) throws Exception {
            st = new StringTokenizer(br.readLine());

            n = Integer.parseInt(st.nextToken());
            b = Long.parseLong(st.nextToken());

            matrix = new int[n][n];

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                for (int j = 0; j < n; j++) {
                    matrix[i][j] = Integer.parseInt(st.nextToken()) % MOD;
                }
            }

            matrix = go(matrix, b);

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(matrix[i][j] + " ");
                }
                System.out.println();
            }
        }

        static int[][] go(int[][] a, long b) {
            if (b == 1) {
                return a;
            } else if (b == 2) {
                return multiplication(a, a);
            }

            // b가 짝수면 a^(b / 2) * a^(b / 2)
            if (b % 2 == 0) {
                return go(go(a, b / 2), 2);
            } else {
                // b가 홀수면 a^(b / 2) * a^(b / 2) * a
                return multiplication(go(go(a, b / 2), 2), a);
            }
        }

        /**
         * 행렬곱
         * @param a 행렬1
         * @param b 행렬2
         * @return
         */
        static int[][] multiplication(int[][] a, int[][] b) {
            int[][] result = new int[n][n];

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int sum = 0;
                    for (int k = 0; k < n; k++) {
                        sum += (a[i][k] * b[k][j]) % MOD;
                    }

                    result[i][j] = sum % MOD;
                }
            }

            return result;
        }
    }