10830번 행렬 제곱

문제링크 : www.acmicpc.net/problem/10830

10830번: 행렬 제곱

---

문제

크기가 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제곱한 결과를 출력한다.

예제 입력 1

2 5
1 2
3 4

예제 출력 1

69 558
337 406

예제 입력 2

3 3
1 2 3
4 5 6
7 8 9

예제 출력 2

468 576 684
62 305 548
656 34 412

예제 입력 3

5 10
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1
1 0 0 0 1

예제 출력 3

512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512
512 0 0 0 512

---

<알고리즘>

1) operator *의 정의를 변경하여 가독성을 높인다. -> 계산방식은 행렬 곱셈 문제와 동일

     2021.04.01 - [Baekjoon Online Judge] - 2740번 행렬 곱셈

 2) 제곱을 해줄 때 N이 0이 될때 까지, 

    2-1) N이 홀수 일때, A^N = A*A^(N-1) 를 이용하여 계산한다. 

    2-2) N이 짝수 일때, (A^2)^(N/2) 를 이용하여 계산한다.

 

 

 

 

메모리 : 2020KB    시간 : 0ms

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

typedef vector<vector<long long>> matrix;
int N = 0;
long long B = 0;

matrix operator* (matrix &first, matrix &second) {
	matrix calculate(N, vector<long long>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			int answer = 0;
			for (int a = 0; a < N; a++) {
				answer += ((first[i][a] % 1000) * (second[a][j] % 1000) % 1000);
			}
			calculate[i][j] = answer % 1000;
		}
	}
	return calculate;
}

matrix power(matrix origin) {
	//단위행렬
	matrix unit(N, vector<long long>(N));
	for (int i = 0; i < N; i++) {
		unit[i][i] = 1;
	}

	while (B > 0) {
		if (B % 2 == 1) {
			unit = unit * origin;
		}
		B /= 2;
		origin = origin * origin;
	}
	return unit;
}

void print(matrix mat) {
	mat = power(mat);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cout << mat[i][j] << " ";
		}
		cout << "\n";
	}
}

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

	matrix origin(N, vector<long long>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> origin[i][j];
		}
	}
	   
	print(origin);

	return 0;
}