문제 접근

행렬 A를 B번 거듭제곱한 결과의 각 원소를 1000으로 나눈 나머지를 원소로 갖는 행렬을 출력하는 문제다.
우선, 이 문제를 보고 가장 먼저 떠올려야 하는것은 행렬의 곱셈에 결합법칙이 성립하는가를 알아야 한다. 또한, 어떻게 해야 결합법칙을 활용해서 최대한 중복 행렬이 많이 발생하도록 쪼개서 결합해서 곱셈을 시킬까이다. 연산 과정에서 중복 행렬이 피연산자로 많이 재등장해야 우리가 DP로 시간을 아낄 수 있기 때문이다.
그렇다면 다음과 같이 쪼개면 어떨까?

예를 들어, A를 19번 거듭제곱해야 한다고 치자.
AAAAAAAAAAAAAAAAAAA
= (AAAAAAAAA) x (AAAAAAAAA) x A
= ((AAAA) x (AAAA) x A) x ((AAAA) x (AAAA) x A) x A
= ((AA x AA) x (AA x AA) x A) x ((AA x AA) x (AA x AA) x A) x A

위 과정에서 A에 대한 거듭제곱에서 AA를 한 번 구해놓으면 이걸 8번 써먹을 수 있다.
그리고 AAAA는 4번 써먹을 수 있다.
그리고 AAAAAAAAA는 2번 써먹을 수 있다.

여기까지만 해도 이 문제를 풀 수 있지만, 이 문제를 풀기 위해서는 모듈로 연산의 곱셈 성질도 알아야 한다.

• 참고 링크
  https://louanna97.tistory.com/93

문제 풀이

import java.io.*;
import java.util.*;

class Main {
    static int N;
    static long B;
    static int[][] origin;

    static HashMap<Long, int[][]> dp = new HashMap<>();

    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());
        B = Long.parseLong(st.nextToken());
        origin = new int[N][N];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                origin[i][j] = Integer.parseInt(st.nextToken()) % 1000;
            }
        }
        dp.put(1L, origin);

        int[][] result = solution(B);
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                sb.append(result[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.print(sb);
    }

    private static int[][] solution(long n) {
        if (dp.containsKey(n)) return dp.get(n);
        int[][] halfMultiple = solution(n / 2);
        int[][] next = multiple(halfMultiple, halfMultiple);
        if (n % 2 != 0) {
            next = multiple(next, origin);
        }

        dp.put(n, next);
        return next;
    }

    private static int[][] multiple(int[][] a, int[][] b) {
        int[][] next = new int[N][N];
        for (int i = 0; i < N; i++) { // a의 행
            for (int j = 0; j < N; j++) { // b의 열
                int sum = 0;
                for (int c = 0; c < N; c++) {
                    sum += a[i][c] * b[c][j];
                }
                next[i][j] = sum % 1000;
            }
        }
        return next;
    }
}