[백준(Baekjoon)][자바(java)] 10830 : 행렬 제곱 / 분할 정복

 

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

10830번: 행렬 제곱

 

1629 : 곱셈  ( hyunjiishailey.tistory.com/136 ) 

2740 : 행렬 곱셈  ( hyunjiishailey.tistory.com/138 )

( 위 두 문제의 콜라보 문제 )

 

import java.util.Scanner;

public class Main {
	
	static Scanner sc = new Scanner(System.in);
	static int n = sc.nextInt(), p = 1000;
	static long b = sc.nextLong();
	static int a[][] = new int[n][n], r[][] = new int[n][n];
	
	public static int[][] matrix_pow( long k ) {
    
		if( k == 1 )	return r = a;
        
		int t[][] = matrix_pow( k / 2 ), i, j, l;	// tmp arr
        
		int t_e[][] = new int[n][n];		// tmp arr - if k is even 
		for( i = 0; i < n; i++ ) 
			for( j = 0; j < n; j++ ) 
				for( l = 0; l < n; l++ )
					t_e[i][j] += t[i][l] * t[l][j] % p;
		r = t_e;
		if( k % 2 == 1 ) {
			int t_o[][] = new int[n][n];	// tmp arr - if k is odd 
			for( i = 0; i < n; i++ ) 
				for( j = 0; j < n; j++ ) 
					for( l = 0; l < n; l++ )
						t_o[i][j] += t_e[i][l] * a[l][j] % p;
			r = t_o;
		}
        
		for( i = 0; i < n; i++ ) 
			for( j = 0; j < n; j++ ) 
				r[i][j] %= p;
                
		return r;
	}

	public static void main(String[] args) {
		
		int i, j;
		for( i = 0; i < n; i++ )
			for( j = 0; j < n; j++ )
				a[i][j] = sc.nextInt() % p;
		sc.close();
                
		matrix_pow( b );
        
		for( i = 0; i < n; i++ ) {
			for( j = 0; j < n; j++ )
				System.out.print( r[i][j] + " " );
			System.out.println();
		}

	}
}