문제

boj10830_1 boj10830_2

행렬곱 계산식 만드는거랑 벡터 초기화하는게 헷갈렸다. 나머지는 아까 곱셈 문제랑 패턴이 거의 비슷함!

그리고 B의 범위를 안 보고 int로 선언한 거나 B == 1이고 A 원소 값에 1000이 있는 경우 예외처리 등을 안해줘서 세 번 만에 맞혔다. 테케 통과했다고 신나서 바로 제출하러 가지 말고 문제 조건 다시 따져본 다음에 제출하자..

구현

// BOJ 10830: 행렬 제곱
#include <iostream>
#include <vector>
using namespace std;
typedef vector< vector<int> > matrix;

matrix A(6, vector<int>(6, 0));

matrix mul(matrix & A, matrix & B, int N) {
	matrix ans(6, vector<int>(6, 0));
	int i, j, k;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			for (k = 0; k < N; k++) {
				ans[i][j] += (A[i][k] * B[k][j]);
				ans[i][j] %= 1000;
			}
		}
	}
	return ans;
}

matrix solve(matrix & A, long long B, int N) {
	if (B == 1) { // A = ((1000, 1000), (1000, 1000)), B = 1 같은 경우 예외처리
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				A[i][j] %= 1000;
			}
		}
		return A;
	}

	matrix tmp = solve(A, B / 2, N);
	matrix tmp2 = mul(tmp, tmp, N);
	if (B % 2 == 0) return tmp2;
	else return mul(A, tmp2, N);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int N, i, j, tmp;
	long long B;
	cin >> N >> B;

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			cin >> tmp;
			A[i][j] = tmp;
		}
	}

	A = solve(A, B, N);

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			cout << A[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}