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

• 문제 링크: https://www.acmicpc.net/problem/10830

 

행렬 A^B를 구하는 문제입니다. 두 가지만 알면 쉽게 풀 수 있습니다.

• 분할정복을 이용한 거듭제곱
• 큰 수의 모듈러 연산

1000으로 나눈 나머지를 출력하라고 되어 있으니 제곱할 때마다 mod 연산을 해주면 되고, B의 값이 최대 1000억이기 때문에 그냥 제곱하면 안됩니다..

분할정복으로 a^n을 O(log n)에 계산할 수 있는 방법이 있으니 그런 식으로 계산해야 하구요 1000억이라고 해봐야 log_2(1000억) = 36...이니 얼마 안됩니다.

참고로 결과값 배열을 구할때 항등원(기약행렬)부터 곱해나가기 시작해야 합니다.

#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

using ll = long long;
using matrix = vector<vector<int>>;
const int MOD = 1000;

matrix mul(matrix a, matrix b) {
	assert(a[0].size() == b.size());

	// (l행 m열) * (m행 n열) = (l행 n열)
	const auto rows = a.size(),
		cols = b[0].size(),
		m = a[0].size();

	matrix res(rows, vector<int>(cols));
	for (int i = 0; i < rows; ++i) {
		for (int j = 0; j < cols; ++j) {
			for (int k = 0; k < m; ++k) {
				res[i][j] += a[i][k] * b[k][j];
			}
			res[i][j] %= MOD;
		}
	}

	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif	// ONLINE_JUDGE
	
	ll n, b;
	cin >> n >> b;

	matrix a(n, vector<int>(n));
	matrix res = a;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> a[i][j];

	for (int i = 0; i < n; ++i)
		res[i][i] = 1;

	while (b > 0) {
		if (b & 1) {
			res = mul(res, a);
		}

		a = mul(a, a);
		b >>= 1;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (j) cout << ' ';
			cout << res[i][j];
		}
		cout << '\n';
	}

	return 0;
}