이 문제에서 요구하는 피보나치 수의 성질은 사실 다른 문항에 소개되어 있습니다.
즉, $ \sum_{i = 1}^{n}F_{i}=F_{n+2}-1 $ 입니다. (증명은 수학적 귀납법으로 간단하게 가능합니다.)
이 식을 조금 변형하여 다음과 같이 우리가 원하는 바를 얻을 수 있습니다.
$ \sum_{i=a}^{b}F_{i}=\sum_{i=1}^{b}F_{i}-\sum_{i=1}^{a-1}F_{i}=F_{b+2}-F_{a+1} $
이때 주의해야할 점이 있는데,
만약 $ F_{b+2} < F_{a+1} $ (mod $ 10^{9} $) 인 경우 양수로 출력해야 하기 때문에 결과에 $ 10^{9} $ 를 더해야 정답이 나옵니다.
결과적으로 코드는 다음과 같습니다.
#include <stdio.h>
typedef struct {
long long array[2][2]; // 2x2 square matrix
} Matrix;
Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M); // AB , 2x2 square matrix
Matrix matrix_power_modular (Matrix A, long long K, long long M); // A^K , 2x2 square matrix
long long Get_Fibonacci (long long N); // Nth Fibonacci number
int main() {
long long a, b;
scanf("%lld %lld", &a, &b);
long long result = Get_Fibonacci(b+2) - Get_Fibonacci(a+1);
if (result < 0) {
result += 1000000000;
}
printf("%lld", result); // F(1) + F(2) + .. + F(n) = F(n+2) - 1
return 0;
}
Matrix matrix_multiply_modular (Matrix A, Matrix B, long long M) { // AB, 2x2 square matrix
Matrix result;
int i, j, k;
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++) {
result.array[i][j] = 0;
for (k = 0; k < 2; 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) {
Matrix result;
result.array[0][0] = result.array[1][1] = 1;
result.array[0][1] = result.array[1][0] = 0;
while (K > 0) {
if (K & 1) {
result = matrix_multiply_modular (result, A, M);
}
A = matrix_multiply_modular (A, A, M);
K >>= 1;
}
return result;
}
long long Get_Fibonacci (long long N) {
Matrix Base;
Base.array[0][0] = Base.array[0][1] = Base.array[1][0] = 1;
Base.array[1][1] = 0;
int i, j;
Matrix Fibonacci = matrix_power_modular (Base, N, 1000000000);
return Fibonacci.array[0][1];
}
(C11, 1116KB, 0ms, 제출번호 25591685)
피보나치 수의 성질에 대해 알아가는 문제로 활용하면 충분하다고 생각합니다.
하지만 다른 비슷한 문제들은 골드2를 받았는데 이 문제만 골드1인 건 조금 이질감이 드는 것 같습니다.
'분할 정복을 이용한 거듭제곱 > 행렬 거듭제곱' 카테고리의 다른 글
백준 11443번: 짝수번째 피보나치 수의 합 (0) | 2021.01.29 |
---|---|
백준 11442번: 홀수번째 피보나치 수의 합 (0) | 2021.01.29 |
백준 11238번: Fibo (0) | 2021.01.29 |
백준 11778번: 피보나치 수와 최대공약수 (0) | 2021.01.29 |
백준 13075번: Fibonacci Sequence (0) | 2021.01.29 |