백준 : 10830 - 행렬 제곱

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

 

★ 주의할점 : 행렬곱이 나오면 시간초과를 주의하자!!

 

방법1 : 냅다 행렬곱 구현해서 b번 반복하기 -> 시간초과

 

행렬곱 자체가 n^3 시간복잡도가 나오는데 이걸 b번 반복하면,,,,,,,,,,,,,,,,,,,,,, 너무 계산량이 많다!

 

---

 

방법2 : A^4 = A^2 * A^2 이용하기

 

행렬의 거듭제곱은 이렇게 쪼갤수가 있다.

그러니까,,, A^b을 A^2, A^4, A^8 .... 여러개로 쪼개서 곱해준다고 생각해보면,,,,

약간 이진트리처럼 logn 이렇게 줄어드는 효과가 생기지 않을까 싶다!!ㅎㅎ

 

b를 2로 나눠가면서 곱하기 곱하기를 해도 비슷할것같은데

어케 구현해야 할지 감이 안잡혀서 걍 2거듭제곱 여러개로 해결해봤당ㅎㅎ

 

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

void mul(vector<vector<int>>, vector<vector<int>>, vector<vector<int>>*);
vector<vector<int>> mul2(vector<vector<int>>, vector<vector<int>>);
void print_vec(vector<vector<int>>);

int main() {

	int n;
	long long b;
	cin >> n >> b;

	vector<vector<int>> a(n, vector<int>(n));
	vector<vector<int>> result(n, vector<int>(n, 0));

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
			a[i][j] %= 1000;
			if (i == j) {
				result[i][j] = 1;
			}
		}
	}
	

	if (b == 1) {
		print_vec(a);
		return 0;
	}


	while (b > 0) {
		long long n2 = 1;
		vector<vector<int>> subresult = a;
		while (b >= (n2 * 2)) {
			// 제곱근 가능!
			n2 *= 2;
			subresult = mul2(subresult, subresult);
		}

		/*cout << "n2 : " << n2 << endl;
		print_vec(subresult);
		cout << "--------" << endl;*/

		b -= n2;
		result = mul2(result, subresult);

		/*cout << "result" << endl;
		print_vec(subresult);
		cout << "--------" << endl;*/

		/*if (b == 1) {
			result = mul2(subresult, a);
			break;
		}*/
	}
	

	print_vec(result);

	return 0;
}



vector<vector<int>> mul2(vector<vector<int>> a, vector<vector<int>> b){
	vector<vector<int>> result = a;
	for (int i = 0; i < (int)a.size(); i++) {
		for (int j = 0; j < (int)a.size(); j++) {
			result[i][j] = 0;
			for (int k = 0; k < (int)a.size(); k++) {
				result[i][j] += (a[i][k] * b[k][j]);
			}
			result[i][j] %= 1000;
		}
	}
	return result;
}

void print_vec(vector<vector<int>> vec) {
	for (int i = 0; i < (int)vec.size(); i++) {
		for (int j = 0; j < (int)vec.size(); j++) {
			cout << vec[i][j] << " ";
		}
		cout << endl;
	}
}

void mul(vector<vector<int>> a, vector<vector<int>> b, vector<vector<int>>* result) {
	for (int i = 0; i < (int)result->size(); i++) {
		for (int j = 0; j < (int)result->size(); j++) {
			(*result)[i][j] = 0;
			for (int k = 0; k < (int)a.size(); k++) {
				(*result)[i][j] += (a[i][k] * b[k][j]);
			}
			(*result)[i][j] %= 1000;
		}
	}
}

 

while문 부분이 나눠주는 부분!!