백준 12987번: Matrix Again

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

12987번: Matrix Again

---

 

이 문제 지문을 잘 읽어보면 이미 블로그에서 다룬 문제와 거의 똑같다는 걸 알 수 있습니다.

2021.02.19 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 13246번: 행렬 제곱의 합

 

13246번과 동일한 풀이이므로 자세한 설명은 생략하겠습니다.

 

단, 음수에 대한 modular operation과 modulo 값이 주어지는 것에 주의하면 충분합니다.

 

제 코드는 아래와 같습니다.

/*
 * Author : thdtjdals3
 * Date : 2021-12-17
 * Description : BOJ 12987
 * Link : https://www.acmicpc.net/problem/12987
 */

#include <stdio.h>

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

Matrix matrix_multiply_modular (Matrix A, Matrix B, int size, int M);
Matrix matrix_power_modular (Matrix Base, int size, int power, int M);
Matrix matrix_power_sum_modular (Matrix Base, int size, int power, int M);

int main() {

	int N, K, M;
	scanf("%d %d %d", &N, &K, &M);
	
	Matrix Base = { {{0}} };
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			scanf("%d", &Base.array[i][j]);
			Base.array[i][j] = ((Base.array[i][j] % M) + M) % M;
		}
	}
	
	Base = matrix_power_sum_modular (Base, N, K, M);
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			printf("%d ", (Base.array[i][j] + M) % M);
		}
		printf("\n");
	}
	
	return 0;
}

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

Matrix matrix_power_modular (Matrix Base, int size, int power, int M) {
	Matrix result = { {{0}} };
	for (int i = 0; i < size; i++)
	{
		result.array[i][i] = 1;
	}
	while(power > 0)
	{
		if (power % 2)
		{
			result = matrix_multiply_modular (result, Base, size, M);
		}
		Base = matrix_multiply_modular (Base, Base, size, M);
		power /= 2;
	}
	return result;
}

Matrix matrix_power_sum_modular (Matrix Base, int size, int power, int M) {
	if (power == 1)
	{
		return Base;
	}
	else if (power % 2)
	{
		Matrix result = matrix_power_modular (Base, size, power, M);
		Matrix temp = matrix_power_sum_modular (Base, size, power - 1, M);
		for (int j = 0; j < size; j++)
		{
			for (int i = 0; i < size; i++)
			{
				result.array[i][j] = (result.array[i][j] + temp.array[i][j]) % M;
			}
		}
		return result;
	}
	else
	{
		Matrix result = matrix_power_modular (Base, size, power/2, M);
		Matrix temp = matrix_power_sum_modular (Base, size, power/2, M);
		for (int i = 0; i < size; i++)
		{
			result.array[i][i] = (result.array[i][i] + 1) % M;
		}
		result = matrix_multiply_modular (temp, result, size, M);
		return result;
	}
}

(C11, 132ms, 3028KB, 제출번호 36401790)

---