백준 10830 행렬 제곱 oo

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

입력

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤  5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

 

2차원 배열을 사용하면 반환형과 매개변수로 쓰기가 어려움.

따라서 vector로 2차원 배열 타입을 지정하고 사용한다.

 

곱셈을 operator로 구현하고, 분할 정복으로 B제곱을 구현하면 됨.

 

#include <iostream>
#include <string.h>
#include <deque>
#include<queue>
#include<vector>
#include<map>
#include <algorithm>

using namespace std;
long long N, B;
typedef vector<vector<long long>> vec;

vec operator * (vec a, vec b)
{
	int n = a.size();
	vec c(n, vector<long long>(n));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
			{
				c[i][j] += a[i][k] * b[k][j];
			}
			c[i][j] %= 1000;
		}
	}
	return c;

}



vec go(vec a, long long B)
{
	if (B == 1)
	{
		return a;
	}

	vec ans(N, vector<long long>(N));
	if (B % 2)
	{
		ans = a * go(a, B - 1);
	}
	else
	{
		ans = go(a, B / 2);
		ans = ans * ans;
	}
	return ans;
}




int main(void)
{
	cin >> N >> B;
	vec a(N, vector<long long>(N));

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> a[i][j];
		}
	}
	vec b(N, vector<long long>(N));
	
	b = go(a, B);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cout << b[i][j] % 1000 << " ";
		}
		cout << endl;
	}

	return 0;
}