[백준 10830] 행렬제곱 (C++)

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

10830번: 행렬 제곱

1. 주의할 점

- B가 최대 1000억까지 증가할 수 있다(단순 연산만 해도 100초)

- 시간 제한: 1초

- 행렬의 원소는 매 계산마다 MOD 1000 한 결과를 보유한다

 

2. 해결법

- B를 logB만큼 줄여서 1초내에 연산을 끝내도록 한다

 

3. 함수 기능

- mul 함수: 2차행렬 X 2차행렬을 위한 함수

- pow 함수: v^B 의 결과를 돌려준다

#define MOD 1000
#include <iostream>
#include <vector>
using namespace std;
int num;
vector<vector<int>> mul(vector<vector<int>> &a, vector<vector<int>> &b) {
	vector<vector<int>> result(num, vector<int>(num, 0));
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++) {
			for (int k = 0; k < num; k++) {
				result[i][j] += (a[i][k] * b[k][j]);
				result[i][j] %= MOD;
			}
		}
	}
	return result;
}

vector<vector<int>> pow(vector<vector<int>> &a, vector<vector<int>> &v, long long square) {
	if (square == 1) return v;
	vector<vector<int>> temp(num, vector<int>(num, 0));
	if (square % 2 == 0) {
		temp = pow(a, v, square / 2);
		return mul(temp, temp);
	}
	temp = pow(a, v, square - 1);
	return mul(temp, a);
}

int main() {
	long long square;
	cin >> num >> square;
	vector<vector<int>> v(num, vector<int>(num, 0));
	vector<vector<int>> arr(num, vector<int>(num, 0));
	for (int i = 0; i < num; i++)
		for (int j = 0; j < num; j++) {
			cin >> arr[i][j];
			v[i][j] = arr[i][j];
		}
	v = pow(arr,v,square);
	for (int i = 0; i < num; i++) {
		for (int j = 0; j < num; j++)
			cout << v[i][j]%MOD<<" ";
		cout << endl;
	}
	system("pause");
	return 0;
}