10830번
백준 문제풀이
10830번
분할 정복
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <stdio.h>
#include <string.h>
#define NMAX 5
#define MOD 1000
// 행렬 곱셈 함수
void multiply(int a[][NMAX], int b[][NMAX], int result[][NMAX], int n) {
int temp[NMAX][NMAX] = { 0 };
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int k = 0; k < n; k++) {
temp[i][j] += (a[i][k] * b[k][j]) % MOD;
temp[i][j] %= MOD;
}
}
}
// 결과를 result로 복사
memcpy(result, temp, sizeof(temp));
}
// 분할 정복을 이용한 행렬 제곱 함수
void matrix_power(int matrix[][NMAX], int result[][NMAX], int n, long long power) {
int temp[NMAX][NMAX];
// 단위 행렬 초기화
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
result[i][j] = (i == j) ? 1 : 0;
}
}
// 분할 정복 계산
/*
^5 = ^1 * ^4
^4 = ^2 * ^2
^2 = ^2 * ^2
^1 = matrix
*/
while (power > 0) {
if (power % 2 == 1) { // 홀수 거듭제곱일 경우
multiply(result, matrix, temp, n);
memcpy(result, temp, sizeof(temp));
}
multiply(matrix, matrix, temp, n); // 행렬 제곱
memcpy(matrix, temp, sizeof(temp));
power /= 2;
}
}
int main() {
int N;
long long B;
int matrix[NMAX][NMAX], result[NMAX][NMAX];
// 입력
scanf("%d %lld", &N, &B);
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
scanf("%d", &matrix[i][j]);
matrix[i][j] %= MOD; // 모듈러 연산으로 미리 값을 줄임
}
}
// 행렬 제곱 계산
matrix_power(matrix, result, N, B);
// 출력
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", result[i][j]);
}
printf("\n");
}
return 0;
}