[C++] 백준 10830번: 행렬 제곱

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

10830번: 행렬 제곱

과거에 이와 비슷한 문제를 푼 적이 있다. 그 때도 동일한 방법으로 문제를 해결했었는데, 그 때는 다른 블로그의 답안을 참고했었다. 분할정복법을 이용하여 O(log N) 시간에 문제를 해결할 수 있다. 입력이 최대 100,000,000,000으로 꽤 큰 수이지만 log_2(100,000,000,000) = 36.5밖에 되지 않으므로 시간초과가 나지 않는다. 같은 이유로 함수의 반환 형식을 vector<vector<int>>로 남발해도 메모리 초과가 발생하지 않는다. 그래서 편안하게 코드를 작성하고 제출하는데 80%에서 WA를 받아 난감했다. 질문글을 살펴보니 입력된 행렬의 원소 값이 1,000인 경우가 있다고 하여, 이를 1000을 나눈 나머지를 출력하도록 고친 후 제출했고 AC를 받았다. 매번 반복적으로 깨닫지만, 문제를 꼼꼼히 읽자.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>
#define VP vector<pair<int, int>>
#define VVP vector<VP>

/* declare variables here */
int N;
long long B;
VVI A, ans;

/* define debug functions here */
void print(VVI& mat) {
	FOR(r, N) {
		FOR(c, N)
			cout << mat[r][c] << ' ';
		cout << EL;
	}
	cout << EL;
}

/* define functions here */
void product(VVI& mat, const VVI& other) {
	VVI ret(N, VI(N, 0));
	FOR(r, N) FOR(c, N) {
		FOR(i, N)
			ret[r][c] += mat[r][i] * other[i][c];
		ret[r][c] %= 1'000;
	}
	mat = ret;
}

VVI solve(long long B) {
	if (B == 1)
		return A;
	VVI ret = solve(B / 2);
	product(ret, ret);
	if (B % 2)
		product(ret, A);
	return ret;
}

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	/* Write input codes here  */
	cin >> N >> B;
	A = VVI(N, VI(N));
	FOR(r, N) FOR(c, N)
		cin >> A[r][c];

	/* Write solution codes here */
	FOR(r, N) FOR(c, N)
		A[r][c] %= 1'000;
	ans = solve(B);
	print(ans);

	return 0;
}