행렬 제곱 (feat. 백준, 10830번)

행렬 제곱
https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
long long tmp[5][5];
int N;
void solution(long long(*arr1)[5], long long(*arr2)[5]) {
	for (register int i = 0, j, k; i < N; ++i)
		for (j = 0; j < N; ++j) {
			tmp[i][j] = 0;
			for (k = 0; k < N; ++k)
				tmp[i][j] += arr1[i][k] * arr2[k][j];
			tmp[i][j] %= 1000;
		}
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j)
			arr1[i][j] = tmp[i][j];
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register long long B, arr[5][5]{ 0 }, ans[5][5]{ 0 };
	cin >> N >> B;
	for (register int i = 0, j; i < N; ++i) {
		for (j = 0; j < N; ++j)
			cin >> arr[i][j];
		ans[i][i] = 1;
	}
	while (B) {
		if (B % 2)
			solution(ans, arr);
		solution(arr, arr);
		B /= 2;
	}
	for (register int i = 0, j; i < N; ++i) {
		for (j = 0; j < N; ++j)
			cout << ans[i][j] << " ";
		cout << "\n";
	}
	return 0;
}
// *&)*@*