[백준, BOJ 10830] 행렬 제곱 (java)

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

10830번: 행렬 제곱

---

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

728x90

 

예제 입력 1

2 5
1 2
3 4

예제 출력 1

69 558
337 406

 

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

468 576 684
62 305 548
656 34 412

 

예제 입력 3

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

---

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

public class Main {
	
	static int N;
	static int[][] matrix;
	static final int MOD = 1000;
	
	private static int[][] pow(long p) {
		if(p == 0 || p == 1) {
			return matrix;
		}
		
		int[][] tmp = pow(p / 2);
		int[][] result = multiply(tmp, tmp);
		
		if((p & 1) == 1) result = multiply(result, matrix);
		
		return result;
	}
	
	private static int[][] multiply(int[][] mt1, int[][] mt2) {
		
		int[][] result = 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++) {
					result[i][j] += mt1[i][k] * mt2[k][j];
				}
				result[i][j] %= MOD;
			}
		}
		
		return result;
	}

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		// 입력
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		long 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());
			}
		}
		
		// 행렬 제곱 구하기
		int[][] result = pow(B);
		
		// 답 출력
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				result[i][j] %= MOD;
				sb.append(result[i][j] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb);
	}

}