백준 10830번: 행렬 제곱

www.acmicpc.net/problem/10830

10830번: 행렬 제곱

---

2021/01/23 - [분할 정복을 이용한 거듭제곱/이론] - 기본 이론2

 

이 글에서 다룬 것과 같은 방식으로 진행하면 됩니다.

 

행렬의 각 원소가 1000 이하의 숫자이므로, 오버플로우 걱정할 필요 없이 int 내에서 해결 가능합니다.

 

#include <stdio.h>

typedef struct {
	int array[5][5];
} Matrix;

Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, int M);
Matrix matrix_power_modular (Matrix A, long long K, int N, int M);

int main() {
	
	int N;
	long long B;
	scanf("%d %lld", &N, &B);
	
	Matrix Base;
	
	int i, j;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &Base.array[i][j]);
		}
	}
	
	Base = matrix_power_modular (Base, B, N, 1000);
	
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			printf("%d ", Base.array[i][j]);
		}
		printf("\n");
	}
	
	return 0;
}

Matrix matrix_multiply_modular (Matrix A, Matrix B, int N, int M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			result.array[i][j] = 0;
			for (k = 0; k < N; k++) {
				int temp = A.array[i][k] * B.array[k][j];
				result.array[i][j] += temp % M;
			}
			result.array[i][j] %= M;
		}
	}
	return result;
}

Matrix matrix_power_modular (Matrix A, long long K, int N, int M) {
	Matrix result;
	int i, j, k;
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (i == j) {
				result.array[i][j] = 1;
			}
			else {
				result.array[i][j] = 0;
			}
		}
	}
	while (K > 0) {
		if (K & 1) {
			result = matrix_multiply_modular (result, A, N, M);
		}
		A = matrix_multiply_modular (A, A, N, M);
		K >>= 1;
	}
	return result;
}

(C11, 1116KB, 0ms, 제출번호 25752286)

---

47번째 줄의 코드는 45번째 줄에서 이렇게 처리했다면 쓸 일이 없었을 텐데, 그게 조금 아쉬운 감이 있습니다.

 

result.array[i][j] = (result.array[i][j] + temp) % M;