https://www.acmicpc.net/problem/14289
이 문제는 저번 문제를 확장한 것입니다. ( 백준 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)
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
백준 11767번: Squawk Virus (0) | 2021.08.01 |
---|---|
백준 14559번: Protocol (0) | 2021.08.01 |
백준 12850번: 본대 산책2 (0) | 2021.08.01 |
백준 2099번: The game of death (0) | 2021.07.31 |
백준 12916번: K-Path (0) | 2021.07.31 |