[백준] 골4 - 행렬 제곱

10830번: 행렬 제곱

문제 설명

행렬을 최대 1000억번 제곱하는 문제다.

풀이

ret = Identity Matrix

a^p라면

p가 0이 될때 까지

• p가 홀수면?
  • ret에 a를 곱함
• p를 2로 나눔
• a=a^2

코드

/*
reference
<https://seokjin2.tistory.com/9>
*/
#define MOD 1000
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<vector<ll>> Mat;

int n;
ll p;

Mat operator * (const Mat& a, const Mat& b)
{
	Mat ret(n, vector<ll>(n, 0));

	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] %= MOD;
		}
	}

	return ret;
}

Mat Mat_Power(Mat a, ll p)
{
	Mat ret(n, vector<ll>(n, 0));
	for (int i = 0; i < n; i++) // Identity Matrix
		ret[i][i] = 1;

	while (p > 0)
	{
		if (p % 2 == 1)
			ret = ret * a;
		
		p /= 2;
		a = a * a;
	}

	return ret;
}

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

	cin >> n >> p;
	Mat base(n, vector<ll>(n, 0));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> base[i][j];

	Mat ans = Mat_Power(base, p);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << ans[i][j] << " ";
		}
		cout << "\\n";
	}

	return 0;
}

소감

Matrix를 연산자 중복을 써야 깔끔하게 코드가 나온다.

• 행렬 곱 연산

ret[i][j] += a[i][k] * b[k][j];

• 2차원 벡터 초기화

Mat ret(n, vector<ll>(n, 0));