백준 5095번: Matrix Powers

www.acmicpc.net/problem/5095

5095번: Matrix Powers

---

이전글 (2021/01/27 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 10830번: 행렬 제곱)과 거의 동일한 문제입니다.

 

대신 N이 100까지 커질 수 있는 점, 그리고 한 테스트 케이스 당 여러 problem이 있을 수 있는 점에 주의해야 했습니다.

(The input consists of a number of problems.)

 

특이 사항으로는 본문과는 다르게 M이 1인 데이터가 존재하는 것으로 보입니다. 물론 아주 큰 문제는 아니지만...

 

#include <stdio.h>

typedef struct {
	long long array[100][100];
} Matrix;

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

int main() {
	
	Matrix Base;
	
	int N, M, P;
	
	while(1) {
		scanf("%d %d %d", &N, &M, &P);
		if (N == 0 && M == 0 && P == 0) {
			break;
		}
		int i, j;
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				scanf("%lld", &Base.array[i][j]);
			}
		}
		Base = matrix_power_modular (Base, P, N, M);
		for (i = 0; i < N; i++) {
			for (j = 0; j < N; j++) {
				printf("%lld", Base.array[i][j]);
				if (j < N - 1) {
					printf(" ");
				}
			}
			printf("\n");
		}
		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, int K, int N, int M) {
	Matrix result;
	int i, j;
	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, 1616KB, 152ms, 제출번호 25746707)

---

M이 최대 32000이므로, 배열을 long long으로 선언하여 오버플로우를 피했습니다.

 

출력 형식에도 주의를 기울여야하는 문제였습니다. 예를 들어 다음과 같은 인풋 아웃풋이 나와야합니다.

 

Input:
2 17 2 1 2 3 4
2 17 2 1 2 3 4
0 0 0

Output:
7 10
15 5

7 10
15 5

---

locality 와 관련하여 코드 수정이 있었습니다. (2021/4/4)

 

수정된 코드는 다음과 같습니다.

 

#include <stdio.h>

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

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

int main() {
	
	Matrix Base;
	
	int N, M, P;
	
	while(1) {
		scanf("%d %d %d", &N, &M, &P);
		if (N == 0 && M == 0 && P == 0) {
			break;
		}
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				scanf("%d", &Base.array[i][j]);
			}
		}
		Base = matrix_power_modular (Base, P, N, M);
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				printf("%d ", Base.array[i][j]);
			}
			printf("\n");
		}
		printf("\n");
	}
	
	return 0;
}

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

Matrix matrix_power_modular (Matrix A, int K, int N, int M) {
	Matrix result = { {{0}} };
	for (int i = 0; i < N; i++) {
		result.array[i][i] = 1;
	}
	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, 1304KB, 140ms, 제출번호 28022852)

---