BOJ 10830 행렬 제곱

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

분할 정복 연습 문제다.

이 문제를 풀기 전에 

www.acmicpc.net/problem/2740

2740번: 행렬 곱셈

이 문제를 먼저 풀 줄 알아야 한다.

행렬 a, b가 있다면 a의 행과 b의 열을 같은 인덱스에 각각 곱해서 합친 값이 그 값이다.

이 문제를 풀 때에는 operator * 를 사용해서 pow계산을 하기 편하게 해 줬다.

vii operator* (const vii& a, const vii& b) {
	int sz = a.size();
	vii ret(sz, vi(sz));
	f(i, sz) {
		f(j, sz) {
			f(k, sz) {
				ret[i][j] += a[i][k] * b[k][j];
			}
			ret[i][j] %= 1000;
		}
	}
	return ret;
}

사실 ps를 하면서 이렇게 operator를 사용할 일이 없어서 재밌었다.

행렬 제곱은 행렬 곱셈을 b만큼 해주면 된다. 위 코드의 operator 함수를 구성했다면 나머지는 그냥

pow함수를 O(log N)으로 해주면 된다.

vii power(vii& a, ll b) {
	int sz = a.size();
	vii ret(sz, vi(sz));
	f(i, sz) ret[i][i] = 1; //단위 행렬
	while (b) {
		if (b % 2) ret = ret * a;
		b /= 2;
		a = a * a;
	}
	return ret;
}

 곱셈을 할 때에는 그냥 곱해주면 안 되고 단위행렬을 만들어 주고 거기다 곱해줘야 한다.

 

#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
#define vii vector<vector<ll>>
#define vi vector<ll>
#define f(i,n) for (int i=0;i<n;i++)

vii operator* (const vii& a, const vii& b) {
	int sz = a.size();
	vii ret(sz, vi(sz));
	f(i, sz) {
		f(j, sz) {
			f(k, sz) {
				ret[i][j] += a[i][k] * b[k][j];
			}
			ret[i][j] %= 1000;
		}
	}
	return ret;
}

vii power(vii& a, ll b) {
	int sz = a.size();
	vii ret(sz, vi(sz));
	f(i, sz) ret[i][i] = 1;
	while (b) {
		if (b % 2) ret = ret * a;
		b /= 2;
		a = a * a;
	}
	return ret;
}

int main() {
	ll n, b;
	cin >> n >> b;
	vii ar(n, vi(n));
	f(i, n) f(j, n) cin >> ar[i][j];

	vii ans = power(ar, b);

	f(i, n) {
		f(j, n) {
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

분할 정복은 이해가 잘 안 되는 것 같아서 더 풀어봐야겠다.