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

 
#include<iostream>
 
int N = 0;
long long B = 0;
long long graph[5][5] = {};
long long temp[5][5] = {};
long long answer[5][5] = {};
 
void power(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()
{
	std::cin >> N >> B;
 
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			std::cin >> graph[i][j];
		}
 
		answer[i][i] = 1; 
	}
 
	while (B > 0)
	{
		if (B % 2 == 1)
		{
			power(answer, graph);
		}
 
		power(graph, graph);
 
		B /= 2;
	}
 
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < N; ++j)
		{
			std::cout << answer[i][j] << " ";
		}
 
		std::cout << std::endl;
	}
}​

전번에 풀었던 이항계수랑 비슷한 풀이

행렬 제곱이란 게 좀 다르긴 하지만 어짜피 행렬 제곱도 곱셈이니

2로 나누면서 풀다보면 편하다.(logN)