행렬제곱

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

소스코드

MAIN

 public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        StringBuilder sb = new StringBuilder();

        n = Integer.parseInt(st.nextToken()); // 행렬 크기
        b = Integer.parseInt(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())% DIV;
            }
        }

        int[][] answer = solution(matrix,b);

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                sb.append(answer[i][j]).append(' ');
            }
            sb.append('\n');
        }
        System.out.println(sb);
    }

POW

public static int[][] pow(int[][] arr, int[][] arr2) {

        // 매개변수로 넘어 온 배열에 영향을 주지 않기 위해 새로운 배열 선언
        int[][] tmp = new int[n][n];

        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                int num = 0;
                for(int k = 0; k < n; k++) {
                    num += arr[i][k] * arr2[k][j];
                    num %= DIV;
                }
                tmp[i][j] = num;
            }
        }

        return tmp;
    }

Solution

  public static int[][] solution(int[][] arr, int exp) {
        if(exp == 1) return arr;

        int[][] tmp = solution(arr, exp / 2);

        tmp = pow(tmp, tmp);

        if(exp % 2 == 1) {
            tmp = pow(tmp, matrix);
        }

        return tmp;
    }

+@ 곱셈

public class BOJ1629 {
    static int A,B,C;
    public static void main(String[] args) throws IOException {


        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
         A = Integer.parseInt(st.nextToken());
         B = Integer.parseInt(st.nextToken());
         C = Integer.parseInt(st.nextToken());


        System.out.println(solution(A,B));

    }

    static long solution(long A , int b){

        if(b ==1){
            return A % C;
        }
        long result = solution(A,b/2);

        if(b%2 ==1){
            return (result * result % C) * A % C;
        }

        return  result * result % C;
    }
}

공부할 것

분할 정복 , 재귀

참고

https://loosie.tistory.com/237#h1
https://st-lab.tistory.com/237