[백준] 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제곱한 결과를 출력한다.

---

풀이)

B의 범위가 크기 때문에 하나씩 곱해보는 A*A*A..*A 이런식으로 계산하면 시간초과가 나는 문제이다.

지수 법칙을 생각해서 풀어야 하는 문제다.

지수 법칙을 이용해 분할정복(divide and conquer) 으로 푼다. 

코드)

#include <stdio.h>
#include <vector>
using namespace std;
 
typedef vector<vector<int>> matrix;
int N, B;
 
matrix A;
matrix temp, result;
 
matrix cal(matrix x, matrix y) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            temp[i][j] = 0;
            for (int t = 0; t < N; t++) {
                temp[i][j] += x[i][t] * y[t][j];
            }
            temp[i][j] %= 1000;
        }
    }
    return temp;
}
int main() {
    scanf("%d %d", &N, &B);
 
    A.resize(N, vector<int>(N));
    temp.resize(N, vector<int>(N));
    result.resize(N, vector<int>(N));
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) scanf("%d", &A[i][j]);
        result[i][i] = 1; //단위행렬로 초기값
    }
    while (B > 0)
    {
        if (B % 2 == 1)//지수가 홀수면 result * A 진행
        {
            result = cal(result, A);
        }
        A = cal(A, A);//행렬 A * A 진행
        B /= 2;
    }
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++) printf("%d ", result[i][j]);
        printf("\n");
    }
 
    return 0;
}