[백준] 10830번 행렬 제곱

문제 출처: https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

재귀를 이용하여 시간복잡도를 줄이는 방법에서 제곱 대신 행렬 제곱을 사용하여 해결할 수 있다.

함수의 리턴 값을 배열으로 하려면 번거롭다. 따라서 리턴을 하지 않는 방법(참조를 이용하여 직접 값을 변경)을 사용하거나 배열을 가지고 있는 구조체를 선언하여 구조체를 리턴해주는 방법이 덜 번거로운 것 같다.

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


typedef long long LL;
using namespace std;
int modul = 1000;


struct arrData {
	LL val[5][5] = {};
};


int N;

arrData matrixSquare(arrData a, arrData b){
	arrData c;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			LL sum = 0;
			for (int k = 0; k < N; k++) {
				sum = (sum + (a.val[i][k] % modul) * (b.val[k][j] % modul)) % modul;
			}
			c.val[i][j]=sum;
		}
	}

	return c;
}


arrData recurFact(arrData arr , LL B){

	arrData result;
	arrData temp;
	if (B == 1) {
		return arr;
	}

	if (B % 2 == 0) {

		temp = matrixSquare(arr, arr);
		if (B == 2)return temp;
		result = recurFact(temp, B / 2);

	}
	else {

		temp = matrixSquare(arr, arr);
		if (B == 3)return matrixSquare(temp, arr);
		result = matrixSquare(recurFact(temp, B / 2),arr);

	}
	

	return result;
}


int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	arrData arr;

	LL B;
	cin >> N;
	cin >> B;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> arr.val[i][j];
			arr.val[i][j] %= modul;
		}
	}

	arrData result = recurFact(arr, B);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << result.val[i][j] << " ";
		}
		cout << "\n";
	}



}