[백준] 10830 행렬 제곱

문제링크: www.acmicpc.net/problem/10830

10830번: 행렬 제곱

이전에 풀었던 행렬 곱셈과 분할정복을 활용했다.

그런데, 임시 배열을 써서 복사행위를 해서 코드가 길어졌다.

다른 분의 코드를 보니 배열을 인자로 넘겨서 하더라.

나중에 다시 풀어보고 활용 해볼 것이다.

import java.io.*;
import java.util.*;
public class Main {
	public static int [][]A;
	public static int N;
	public static long M;
	public static int [][]temp;
	public static int [][] temp2;
	public static void gob() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				temp2[i][j] = 0;
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				for(int k=0;k<N;k++) {
					temp2[i][j] += (A[i][k]*A[k][j])%1000;
				}
				temp2[i][j] %= 1000;
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				A[i][j] = temp2[i][j];
			}
		}
	}
	public static void gob2() {
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				temp2[i][j] = 0;
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				for(int k=0;k<N;k++) {
					temp2[i][j] += (A[i][k]*temp[k][j])%1000;
				}
				temp2[i][j] %= 1000;
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				A[i][j] = temp2[i][j];
			}
		}
	}
	
	public static void divide_q(long N) {
		if(N == 0 || N == 1) {
			return;
		}
		divide_q(N/2);
		gob();
		if(N%2==1) {
			gob2();
		}
		
	}
	
	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());
		M = Long.parseLong(st.nextToken());
		A = new int[N][N];
		temp = new int[N][N];
		temp2 = new int[N][N];
		for(int i=0;i<N;i++) {
			st =  new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
				A[i][j] %= 1000;
			}
		}
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				temp[i][j] = A[i][j];
			}
		}
		divide_q(M);
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(A[i][j] + " ");
			}
			System.out.println();
		}
	}

}