본문이 매우 깁니다.
핵심 문장은 가장 마지막에 있는데,
$ \cdots $ In fact, for any given year, Y, the number of living porpoise pairs is fib(Y) mod $ 10^{9} $, where fib(Y) is the Yth value in the well-known Fibonacci sequence.
한 마디로 Y번째 피보나치 수의 mod $ 10^{9} $ 값을 출력해주면 됩니다. 이전 글과 거의 같습니다.
(2021/01/29 - [분할 정복을 이용한 거듭제곱/행렬 거듭제곱] - 백준 11444번: 피보나치 수 6)
약간 다른 점으로는 최대 1000개의 피보나치 수( mod $ 10^{9} $ )를 출력해야 하는데
N번째 피보나치 수를 대략 $ O \left ( logN \right ) $ 에 구하기 때문에 시간은 전혀 문제가 없습니다.
#include <stdio.h>
typedef struct {
long long array[2][2];
} Matrix;
Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M); // 2by2
Matrix matrix_power_modular (Matrix A, long long k, long long M);
int main() {
Matrix Base;
Base.array[0][0] = 1, Base.array[0][1] = 1, Base.array[1][0] = 1, Base.array[1][1] = 0;
long long n;
scanf("%lld", &n);
Matrix Fibonacci = matrix_power_modular (Base, n, 1000000007);
printf("%lld", Fibonacci.array[0][1]);
return 0;
}
Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) { // 2by2
Matrix result;
int i, j, k;
for (i = 0; i <= 1; i++) {
for (j = 0; j <= 1; j++) {
result.array[i][j] = 0;
}
}
for (i = 0; i <= 1; i++) {
for (j = 0; j <= 1; j++) {
for (k = 0; k <= 1; k++) {
long long temp = (A.array[i][k] * B.array[k][j] ) % M;
result.array[i][j] = (result.array[i][j] + temp) % M;
}
}
}
return result;
}
Matrix matrix_power_modular (Matrix A, long long k, long long M) { // 2by2
Matrix result;
result.array[0][0] = 1, result.array[0][1] = 0, result.array[1][0] = 0, result.array[1][1] = 1;
while (k > 0) {
if (k & 1) {
result = matrix_multiply_modular (result, A, M);
}
A = matrix_multiply_modular (A, A, M);
k >>= 1;
}
return result;
}
(C11, 1116KB, 0ms, 제출번호 25776011)
이 문제의 경우 modulo 값이 $ 10^{9} $ 이므로, 피사노 주기를 이용하기는 힘들지 않을까 싶습니다.
(주기가 아마 $ 15\times 10^{8} $ 인데, 이걸 배열에 전부 저장한다고 하면 메모리는 몰라도 시간은 초과할 듯 합니다.)
언어가 영어인데다가, 문제도 다른 문제들과 차별점이 없고, 본문의 길이가 길이라서 인기가 없을 수밖에 없는 문제였습니다.
저도 여러번 본문을 다 읽어보려다가 말았습니다...
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
백준 13075번: Fibonacci Sequence (0) | 2021.01.29 |
---|---|
백준 2749번: 피보나치 수 3 (0) | 2021.01.29 |
백준 11444번: 피보나치 수 6 (0) | 2021.01.29 |
백준 5095번: Matrix Powers (0) | 2021.01.29 |
백준 10830번: 행렬 제곱 (0) | 2021.01.27 |