BOJ 10830 - 행렬의 제곱

10830번: 행렬 제곱

 

N*N 크기의 행렬 A, A의 B제곱을 구하라. 수가 매우 커질 수 있으니 A^B의 각 원소를 1,000으로 나눈 나머지를 출력.

2≤N≤5, 1≤B≤100,000,000,000

B가 아주 크다. 단순한 방법으로는 안된다.

행렬 A의 B제곱은 A의 B-1 제곱에 A를 곱한 것이다. 팩토리얼과 유사하다. 그런데 B가 최대이면 단순하게 순회를 1번만 돌아도 시간초과이다.

B가 100만이라고 해보자 A^100만 = (A^50만)^2

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

이러면 B가 1천억이라 하더라도 500억 → 250억 → 125억 이렇게 logN으로 감소시킬 수 있다.

그런데 B가 홀수냐 짝수냐에 따라서 처리를 좀 달리해야 한다. B가 짝수라면 그냥 해도 되지만 B가 홀수라면 1일 빼서 짝수로 만든 다음 해당 과정을 처리하고 마지막에 하나를 다시 곱해준다.

필요한 연산들은 다음과 같다.

1. 행렬의 곱셈
2. 거듭제곱의 재귀

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

public class Main {

    static int N;
    static int[][] matrix;
    static long B;
    static final int MOD = 1_000;

    static FastReader scan = new FastReader();

    static void input() {
        N = scan.nextInt();
        B = scan.nextLong();
        matrix = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = scan.nextInt() % MOD;
            }
        }
    }

    static int[][] multiply(int[][] A, int[][] B) {
        int[][] C = new int[N][N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < N; k++) {
                    C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
                }
            }
        }
        return C;
    }

    static int[][] power(int[][] A, long B) {
        if (B == 1) {
            return A;
        }

        int[][] tmp = power(A, B / 2);
        tmp = multiply(tmp, tmp);

        if (B % 2 == 1) {
            tmp = multiply(tmp, matrix);
        }

        return tmp;
    }

    static void solve() {
        int[][] result = power(matrix, B);

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

    public static void main(String[] args) {
        input();
        solve();
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }
}