백준 : 10830

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

10830번: 행렬 제곱

행렬을 2^n 제곱꼴로 미리 저장해둿다가    B 제곱을 구해야하면 B = 2^1 + 2^4 + 2^8 꼴로 분해해서 사용한다.

package day0301;

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

public class B10830 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		long B = Long.parseLong(st.nextToken());
		
		//초기값 E행렬
		int Answer[][] = new int[N][N];
		int dp[][][] = new int[10000][N][N];
		for(int i=0;i<N;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<N;j++) {
				if(i==j) {
					Answer[i][j]=1;
				}
				dp[0][i][j] = Integer.parseInt(st.nextToken());
			}
		}
		int n=1;
		while(Math.pow(2, n) <=B) {
			for(int i=0;i<N;i++) {
				for(int j=0;j<N;j++) {
					for(int k=0;k<N;k++) {
						dp[n][i][j] += (dp[n-1][i][k] *dp[n-1][k][j])%1000;
					}
				}
			}
			n++;
		}
		
		while(B>0) {
			n =0;
			while(Math.pow(2, n+1)<=B) {
				n++;
			}
			B-=Math.pow(2, n);
			int next[][] = 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++) {
						next[i][j] = (next[i][j]+ Answer[i][k] *dp[n][k][j])%1000;
					}
				}
			}
			
			for(int i=0;i<N;i++) {
				System.arraycopy(next[i], 0, Answer[i], 0, N);
			}
			
		}
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<N;j++) {
				System.out.print(Answer[i][j]+" ");
			}
			System.out.println();
		}
		
	}
}