문제

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

예제

---

기본 개념

행렬의 곱셈

https://mathbang.net/562

정방행렬의 거듭제곱

https://greeksharifa.github.io/algorithm%20&%20data%20structure/2018/07/04/algorithm-matrix-power/

---

문제 풀이

https://seokjin2.tistory.com/9

이 문제에서 A^N을 말그대로 A * A * A * ... * A 이렇게 A를 N번 곱하는 방식으로 구하면 시간복잡도가 O(N)이 된다. 근데, N의 최댓값이 100,000,000,000이므로 이 방법으로는 시간초과가 날 수밖에 없다. 따라서 분할정복을 이용하여 O(logN)에 거듭제곱을 구할 수 있는 알고리즘을 사용해야 한다.

빠른 거듭제곱 알고리즘: O(logN)

• N이 홀수: A^N을 A * A^(N-1)로 바꾸고 즉, 밑을 하나 꺼내서 N을 짝수로 만들고 그 밑은 결과값에 곱한다.
• N이 짝수: A^N을 (A^2)^(N/2) 즉, A를 제곱하고 N을 2로 나눈다.
• N == 0이면 반복문 종료

정수의 거듭제곱을 예시로 들면 다음과 같다.

행렬을 거듭제곱 할 때도 위의 알고리즘을 사용하면 된다. 단, 행렬의 곱셈은 연산자 오버로딩으로 직접 구현해줘야 한다!

C++ 코드

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

typedef long long ll; 
typedef vector<vector<ll>> matrix; 

// 행렬의 곱셈을 위한 연산자 오버로딩 
matrix operator * (const matrix& a, const matrix& b){
	int size = a.size(); // 2 ≤ N ≤  5 
	matrix res(size, vector<ll>(size)); // 정방행렬 
    
	for(int i = 0; i < size; i++){ 
		for(int j = 0; j < size; j++){
			for(int k = 0; k < size; k++){
				// 행렬 A의 i행, 행렬 B의 j열 성분끼리 곱해서 더한다. 
                // 행벡터와 열벡터의 내적 
				res[i][j] += a[i][k] * b[k][j]; 
			}
			res[i][j] %= 1000; 
		}
	}
    
	return res; 
}

matrix power(matrix a, ll b){
	int size = a.size();
	matrix res(size, vector<ll>(size)); // 정방행렬 

	// 항등원은 곱해도 자기 자신이 나오게 하는 수 
	// 정수 곱셈에 대한 항등원은 1 
	// 행렬 곱셈에 대한 항등원은 단위 행렬 (res의 초기값으로 설정) 
	for(int i = 0; i < size; i++){
		res[i][i] = 1; // 단위 행렬 
	}

	while(b > 0){
		// b가 홀수일 때는 밑을 하나 꺼내서 b를 짝수로 만들고
		// 그 밑은 결과값에 곱한다. 
		if(b % 2 == 1){
			b -= 1; 
			res = res * a; // 행렬의 곱셈 
		}else{
			// b가 짝수일 때는 밑을 제곱하고 b를 2로 나눈다.
			a = a * a; // 행렬의 곱셈 
			b /= 2; 
		}
	}

	return res; // a의 b제곱 반환 
}

void printMatrix(const matrix& a){
	int size = a.size();
	for(int i = 0; i < size; i++){
		for(int j = 0; j < size; j++){
			cout << a[i][j] << " ";
		}
		cout << "\n"; 
	}
}

int main()
{ 
	ios::sync_with_stdio(0);
    cin.tie(0);

	int n; // 행렬의 크기 (2 ≤ N ≤  5) 
	ll b;  // 지수 (1 ≤ B ≤ 100,000,000,000)
	cin >> n >> b;

	matrix a(n, vector<ll>(n)); // 정방행렬 

	// 행렬의 각 원소 
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> a[i][j]; 
		}
	}

	// a의 b제곱 출력 
	printMatrix(power(a, b)); 
	
	return 0;
}