[10830] 행렬 곱셈

---

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

10830번: 행렬 제곱

분할 정복 문제이다.

 

 

이건 앞에서 했던 두 개의 문제를 동시에 쓰는 것이다.

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

1629번: 곱셈

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

2740번: 행렬 곱셈

 

분할 정복을 이용한 거듭제곱과, 행렬 곱셈을 함께 사용하였다.

 

 

이것도 값이 너무 커질 것을 대비하여 1000으로 나눈 나머지 값을 출력하는 것이 요점이다.

 

 

일단 행렬 계산을 해주는 함수를 만든다.

// 행렬 계산
int** matrix(int** a, int** b) {
	// 동적할당
	int** ans = new int* [N + 1];
	for (int i = 0; i <= N; i++)ans[i] = new int[N + 1];
	// 계산
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			long long sum = 0;
			for (int k = 1; k <= N; k++) {
				sum += (a[i][k] * b[k][j]);
			}
			ans[i][j] = sum % 1000;
		}
	}
	return ans;
}

ans에 들어오는 값은 항상 1000보다 작기 때문에 int형으로 선언했고, sum은 엄청나게 커질 수 있기 때문에 long long으로 선언하였다.

ans에서 동적할당을 하지 않으면 오류가 나와서 동적할당을 해주었다.

 

 

행렬 계산은 끝났고, 분할 정복을 이용한 거듭제곱을 계산할 차례이다.

이것또한 1629번에 있던 코드를 조금 변형해서 사용하였다.

이용한 식

https://kmyobin.tistory.com/114

[1629] 곱셈

int** f(int**a, long long b) {
	if (b == 1) {
		// 1000으로 나눈 나머지 계산
		// 동적할당
		int** ans = new int* [N + 1];
		for (int i = 0; i <= N; i++)ans[i] = new int[N + 1];
		// 계산
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				ans[i][j] = a[i][j] % 1000;
			}
		}
		return ans;
	}

	if (b % 2 == 0) {
		// even
		int** x = f(a, b / 2);
		int** ans = matrix(x, x);
		return ans;
	}
	else {
		// odd
		int** x = f(a, (b - 1) / 2);
		int** ans = matrix(matrix(x, x), a);
		return ans;
	}
}

 

 

전체 코드는 아래와 같다.

#include <iostream>
using namespace std;

int N; long long B;

// 행렬 계산
int** matrix(int** a, int** b) {
	// 동적할당
	int** ans = new int* [N + 1];
	for (int i = 0; i <= N; i++)ans[i] = new int[N + 1];
	// 계산
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			long long sum = 0;
			for (int k = 1; k <= N; k++) {
				sum += (a[i][k] * b[k][j]);
			}
			ans[i][j] = sum % 1000;
		}
	}
	return ans;
}

int** f(int**a, long long b) {
	if (b == 1) {
		// 1000으로 나눈 나머지 계산
		// 동적할당
		int** ans = new int* [N + 1];
		for (int i = 0; i <= N; i++)ans[i] = new int[N + 1];
		// 계산
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				ans[i][j] = a[i][j] % 1000;
			}
		}
		return ans;
	}

	if (b % 2 == 0) {
		// even
		int** x = f(a, b / 2);
		int** ans = matrix(x, x);
		return ans;
	}
	else {
		// odd
		int** x = f(a, (b - 1) / 2);
		int** ans = matrix(matrix(x, x), a);
		return ans;
	}
}

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

	cin >> N >> B;

	// 동적할당
	int** A = new int* [N + 1];
	for (int i = 0; i <= N; i++) {
		A[i] = new int[N + 1];
	}

	// 입력받기
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> A[i][j];
		}
	}

	int** ans = f(A, B);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cout << ans[i][j] << " ";
		}
		cout << endl;
	}
}