백준 12916번: K-Path

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

12916번: K-Path

---

글에서 제공하는 건 정확히 인접행렬의 정의와 같습니다.

 

따라서 행렬을 입력 받아 $K$ 제곱해주고, 각 요소의 값들을 전부 더해주면 길이가 $K$ 인 경로의 수가 됩니다.

( 기본 이론 3 )

 

제 코드는 다음과 같습니다.

#include <stdio.h>
#define mod 1000000007

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

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

int main() {
	
	int size, power;
	scanf("%d %d", &size, &power);
	
	Matrix Base;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			scanf("%lld", &Base.array[i][j]);
		}
	}
	Base = matrix_power_modular (Base, size, power);
	
	long long count = 0;
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			count += Base.array[i][j];
		}
	}
	
	printf("%lld", count % mod);
	return 0;
}

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

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

(C11, 1620KB, 80ms, 제출번호 31669642)

---