[백준/C++] 10830번 - 행렬 제곱

 

문제

https://www.acmicpc.net/problem/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제곱한 결과를 출력한다.

 

 

풀이

 

행렬의 곱을 구하기 위해서는 행렬의 성질을 알아야 한다.

 

일반적으로 행렬의 곱은 A*B와 B*A의 값이 다르다. 하지만 같은 정사각행렬의 곱에서는 A*A^2과 A^2*A가 같다.

 

이를 이용하면 재귀를 통해 절반씩 나눠가며 행렬의 곱을 구할 수 있다.

 

이전에 풀었던 곱셈의 나머지를 구하는 문제들과 크게 다를게 없는 문제이며, 절반씩 나눈뒤 곱해서 풀었다.

 

 

 

Code

 

 

#include<iostream>
using namespace std;

// 10830

long long **arr;
long long **ans;
long long **save_ans;
int A;
long long B;

void bin(long long C) {
	if (C == 1) {
		return;
	}
	else {
		bin(C / 2);
	}
	long long idx_sum = 0;
	for (int i = 0; i < A; i++) {
		for (int j = 0; j < A; j++) {
			idx_sum = 0;
			for (int k = 0; k < A; k++) {
				idx_sum += ans[i][k] * ans[k][j];
			}
			save_ans[i][j] = idx_sum;
		}
	}
	if (C % 2) {
		for (int i = 0; i < A; i++) {
			for (int j = 0; j < A; j++) {
				idx_sum = 0;
				for (int k = 0; k < A; k++) {
					idx_sum += arr[i][k] * save_ans[k][j];
				}
				ans[i][j] = idx_sum%1000;
			}
		}
	}
	else{
		for (int i = 0; i < A; i++) {
			for (int j = 0; j < A; j++) {
				ans[i][j] = save_ans[i][j]%1000;
			}
		}	
	}
}

int main() {
	int idx=0;
	cin >> A >> B;
	arr = new long long*[A];
	ans = new long long*[A];
	save_ans = new long long*[A];
	for (int i = 0; i < A; i++) {
		arr[i] = new long long[A];
		ans[i] = new long long[A];
		save_ans[i] = new long long[A];
		for (int j = 0; j < A; j++) {
			cin >> idx;
			arr[i][j] = idx;
			ans[i][j] = idx;
			save_ans[i][j] = 0;
		}
	}
	bin(B);
	for (int i = 0; i < A; i++) {
		for (int j = 0; j < A; j++) {
			cout<<ans[i][j]%1000<<" ";
		}
		cout << "\n";
	}

	return 0;
}

 

---

 

 

 

10830번: 행렬 제곱