[C/C++] 백준 - 10830번 : 행렬 제곱

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

10830번: 행렬 제곱

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

 

종만북에 있는 분할정복 알고리즘을 공부한 후 같은 문제를 풀어보았다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map> 
#include <algorithm>
#include <cmath>
#include <ctime>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

typedef vector<vector<int>> matrix;
matrix operator * (const matrix& a, const matrix& b) {
	int N = a.size();
	matrix ret(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			for (int k = 0; k < N; k++) {
				ret[i][j] += a[i][k] * b[k][j];
			}
			ret[i][j] %= 1000;
		}
	}
	return ret;
}

matrix identity(int n) {
	matrix ps(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (i == j) ps[i][j] = 1;
		}
	}
	return ps;
}

matrix pow(const matrix& A, ll B) {
	if (B == 0) return identity(A.size());
	if (B % 2 != 0) return pow(A, B - 1) * A;
	matrix half = pow(A, B / 2);
	return half * half;
}

void solution() {
	int N;
	ll B;
	cin >> N >> B;
	matrix board(N, vector<int>(N, 0));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
		}
	}
	matrix answer = pow(board, B);
	for (auto& ptr1 : answer) {
		for (auto& ptr2 : ptr1) {
			cout << ptr2 << " ";
		}
		ENDL;
	}
}

int main() {
	fastio;
	solution();

	return 0;
}