C++:: boj 10830 < 행렬 제곱 >

행렬 제곱을 계산해 주어야 하는데 지수의 크기가 1000억까지 가는 문제이다. 핵심적인 풀이는 N^30 은 N^16 N^8 N^4* N^2 와 같은 형식으로 나누어 곱해주는 방식이다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
#include <string>
using namespace std;
// 행렬 제곱
long long n, b;

vector<vector<long long>> mulVec(vector<vector<long long>> &a, vector<vector<long long>> &b) {
	vector<vector<long long>> res(n, vector<long long>(n, 0));
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			for (int k=0; k<n; k++) {
				res[i][j] += a[i][k] * b[k][j];
			}
			res[i][j] %= 1000;
		}
	}
	return res;
}

int main() {
	cin >> n >> b;
	vector<vector<long long>> v(n, vector<long long>(n)), answer(n, vector<long long>(n, 0));
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			if (i==j) answer[i][j] = 1;// 단위 행렬 E
			cin >> v[i][j];
		}
	}
	string bits = bitset<64>(b).to_string();
    // 행력의 몇 제곱 형태를 사용하는지 판별하기위해 bitset 사용
	int maxPower = 64 - bits.find("1", 0);
	vector<vector<vector<long long>>> v_power(maxPower + 1, vector<vector<long long>>(n, vector<long long>(n, 0)));
	v_power[1] = v;
	for (int i=2; i<=maxPower; i++) {
		v_power[i] = mulVec(v_power[i-1], v_power[i-1]);
	}
	reverse(bits.begin(), bits.end());
	for (int i=0; i<maxPower; i++) {
		if (bits[i] == '1') {
			answer = mulVec(answer, v_power[i+1]);
		}
	}
	if (b == 0) {
		answer = v_power[0];
	}
	for (auto r : answer) {
		for (auto c : r) {
			cout << c << " ";
		}
		cout << "\n";
	}
}