행렬 제곱

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	29759	10520	8339	34.120%

문제

크기가 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제곱한 결과를 출력한다.

예제 입력 1

2 5
1 2
3 4

예제 출력 1

69 558
337 406

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

468 576 684
62 305 548
656 34 412

예제 입력 3

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

추가 반례

https://www.acmicpc.net/board/search/all/problem/10830

예제 입력 A

2 1
1000 1000
1000 1000

예제 출력 A

0 0
0 0

예제 입력 B

2 100000000000
999 998
997 996

예제 출력 B

751 250
875 626

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: doju
• 잘못된 조건을 찾은 사람: dreammusic23

알고리즘 분류

• 수학
• 분할 정복
• 분할 정복을 이용한 거듭제곱
• 선형대수학

---

통과된 코드

입력 받는 B 값이 int의 범위를 벗어나는 경우를 조심

행렬을 B만큼 곱하는 연산을 할 필요가 없이 효율적으로 처리

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 새로운 데이터 유형을 정의
typedef vector<vector<unsigned long long int>> Matrix;

long long int _N, _B;
constexpr int MOD = 1000;

// 행렬 제곱 계산
Matrix MatrixMultiply(Matrix& A, Matrix& B) {

    int _Size = A.size();

    Matrix _Temp(_Size, vector<unsigned long long int>(_Size));

    for (int i = 0; i < _Size; i++) {
        for (int j = 0; j < _Size; j++) {

            unsigned long long int _Sum = 0;

            for (int k = 0; k < _Size; k++) // 모듈러 연산
                _Sum += ((A[i][k] % MOD) * (B[k][j] % MOD)) % MOD;
            _Temp[i][j] = _Sum % MOD;
        }
    }
    return _Temp;
}

// 행렬을 제곱합니다.
Matrix MatrixPow(Matrix& p_Matrix, unsigned long long int p_Cnt) {

    long long int _Size = p_Matrix.size();

    Matrix _Res(_Size, vector<unsigned long long int>(_Size));

    // 항등 행렬로 초기화 => _Res는 거듭제곱의 곱을 누적하는 데 사용
    for (int i = 0; i < _Size; i++) 
        _Res[i][i] = 1;
    
    while (p_Cnt > 0) {

        // 지수가 홀수인 경우 현재 _Res행렬과 입력 행렬을 곱하고 다시 할당
        if (p_Cnt % 2 == 1) _Res = MatrixMultiply(_Res, p_Matrix);       
        p_Matrix = MatrixMultiply(p_Matrix, p_Matrix); 
        p_Cnt /= 2;
        // p_Matrix => A
        // cnt = 4 >  A * A * A * A
        // cnt = 2 > (A * A) * (A * A)
        // cnt = 1 > ((A * A) * (A * A))
    }
    return _Res;
}

int main()
{
    cin >> _N >> _B;

    // 동적으로 행렬 생성
    Matrix _Matrix(_N, vector<unsigned long long int>(_N));

    for (int i = 0; i < _N; i++) {
        for (int j = 0; j < _N; j++) 
            cin >> _Matrix[i][j];       
    }

    // 제곱 시작
    Matrix C = MatrixPow(_Matrix, _B);

    for (int i = 0; i < _N; i++) {
        for (int j = 0; j < _N; j++)
            cout << C[i][j] << " ";
        cout << "\n";
    }

    return 0;
}

수학은 너무 어려운 것 같다.