백준 14289번: 본대 산책 3

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

14289번: 본대 산책 3

---

이 문제는 저번 문제를 확장한 것입니다. ( 백준 12850번: 본대 산책2 )

 

풀이 방법도 똑같습니다.

 

저번 문제와 마찬가지로, 간선에 방향이 없어서 인접행렬이 symmetric 해야 합니다.

 

그렇게 구성한 인접행렬을 $D$ 제곱하면 문제가 해결됩니다.

#include <stdio.h>
#define mod 1000000007

typedef struct {
	long long array[50][50];
} 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, M;
	scanf("%d %d", &size, &M);
	
	Matrix Base = { {{0}} };
	while(M--) {
		int a, b;
		scanf("%d %d", &a, &b);
		Base.array[a-1][b-1] = 1;
		Base.array[b-1][a-1] = 1;
	}
	
	int power;
	scanf("%d", &power);
	
	Base = matrix_power_modular (Base, size, power);
	
	printf("%lld", Base.array[0][0]);
	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;
	for (int i = 0; i < size; i++) {
		result.array[i][i] = 1;
	}
	while(power) {
		if (power % 2) {
			result = matrix_multiply_modular (result, Base, size);
		}
		Base = matrix_multiply_modular (Base, Base, size);
		power /= 2;
	}
	return result;
}

(C11, 1152KB, 12ms, 제출번호 31680752)

---