[Gold IV] 행렬 제곱 - 10830

[문제 위치]

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

[문제 풀이]

행렬의 제곱을 구현하여 푸는 문제이다.

행렬의 곱셈을 구현한 다음 이를 두 번 반복해주면 된다.

행렬의 곱셈은 반복문을 통한 곱셈과 합산으로 이루어진다.

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

long long N, B;
long long A[5][5];
long long temp[5][5];
long long ans[5][5];


// 배열 출력
void print_arr(long long arr[5][5])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cout << arr[i][j] << " ";
		cout << endl;
	}
}

// 행렬 곱셈
void Matrix_multi(long long X[5][5], long long Y[5][5])
{

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			temp[i][j] = 0; // 행렬 초기화
			for (int k = 0; k < N; k++)
				temp[i][j] += (X[i][k] * Y[k][j]);

			temp[i][j] %= 1000;
		}

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			X[i][j] = temp[i][j];
}

int main()
{
	cin >> N >> B;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cin >> A[i][j];
		ans[i][i] = 1; // 정답행렬은 단위행렬로
	}

	while (B > 0)
	{
		if (B % 2 == 1)
		{
			Matrix_multi(ans, A); // 정답행렬에 A행렬 곱하기
		}
		Matrix_multi(A, A);
		B /= 2;
	}

	print_arr(ans); // A를 B번 곱한 결과

}