[BOJ] 백준 10830번: 행렬 제곱 (빠른 거듭 제곱)

먼저 우리는 빠른 거듭 제곱 알고리즘을 알고있습니다.

pow(a,y), 즉 a^y 를 구할때 만약 y가 홀수면 a * a^y/2*a^y/2로 분해하여 짝수 거듭 제곱의 반을 구해가면서 O(lgY)의 복잡도로 구할 수 있습니다.

int pow(int a, int y) {
	int x = 1;
	while (y) {
		if (y & 1) {
			x *= a;
		}
		a *= a;
		y /= 2;
	}
	return x;
}

math.h 헤더의 내장 pow를 사용하지 않고 직접 구현하여 쓰는 이유는, 몇몇 문제에서 특정 수로 나눈 나머지 값을 요구하기 때문입니다. 이유는 답이 너무 커지거나 하는 경우에, 보통 1,000,000,007 (1e9+7)와 같은 소수로 나눈 나머지 값을 요구합니다. 소수는 어떠한 수와도 나누어 떨어지지 않기 때문에 최종 결과값에 소수를 나눈 나머지를 취하든 계산하는 과정에서 소수를 나눠가면서 나머지값으로 결과값을 계산하든 답이 같기 때문입니다. (중간 과정에서 답이 해당 소수가 아닌 이상)

만약 a가 11이고 y가 10000인 조건에서 a^y의 MOD (예를 들어, 1e9+7)로 나눈 값을 출력하라는 문제가 있으면 아래와 같이 중간 단계에서 계속 MOD로 나눈 나머지 값만 취해가면 됩니다.

int pow(int a, int y) {
	int x = 1;
	while (y) {
		if (y & 1) {
			x *= a;
			x %= MOD;
		}
		a *= a;
		a %= MOD;
		y /= 2;
	}
	return x;
}

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

10830번: 행렬 제곱

행렬의 제곱도 같은 방식으로 동작합니다. 어떤 행렬 A를 B번 제곱하는 경우를 AAAA...AAAA 라고 한다면 A(AA) = (AA)A 이므로, 빠른 거듭 제곱의 알고리즘을 그대로 적용시킬 수 있습니다.

행렬에서 곱셈에 대한 자기 자신이 나오는 항등원은 단위 행렬 I 이므로 x = I 로 두시면 됩니다.  (대각성분이 1이고 나머지는 0)

#include <iostream>
#include <queue>
#include <memory.h>
#include <math.h>
#include <algorithm>
#define MOD (1000)
using namespace std;

typedef long long ll;
ll n, b;
int mat[5][5];
int res[5][5];

void power(ll y) {
    while (y) {
        if (y & 1) {
           // res = res * mat 
            int result[5][5] = { 0, };
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int k = 0; k < n; k++) {
                        result[i][j] += (res[i][k] * mat[k][j]);
                        result[i][j] %= MOD;
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    res[i][j] = result[i][j];
                }
            }
        }
        int result[5][5] = { 0, };
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    result[i][j] += (mat[i][k] * mat[k][j]);
                    result[i][j] %= MOD;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                mat[i][j] = result[i][j];
            }
        }
        y /= 2;
        // mat  = mat*mat
        // y /= 2;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> b;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> mat[i][j];
            if (i == j) {
                res[i][j] = 1;
            }
            else {
                res[i][j] = 0;
            }
        }
    }
    // mat 의 b 승
    power(b);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << res[i][j] <<" ";
        }
        cout << "\n";
    }
}