백준 13075번 문제 링크
문제 이름 : Fibonacci Sequence
주 언어 : Python
태그 : 수학 / 분할 정복을 이용한 거듭제곱
solved.ac 등급 : Gold II (2023/03/28 확인)
문제 보기
문제 :
Your job is to take an integer x as the input and compute f(x) mod $10^9$, where f(x) is the x-th value in the well-known Fibonacci sequence.
Note that Fibonacci sequence is defined as follows:
f(1) = f(2) = 1
f(k) = f(k-1) + f(k-2) for any k > 2
(축약 & 번역) - 정수 x가 주어지면, 피보나치 수열 $F_{n}$에 대하여 $F_{x} \pmod{10^9}$를 구하여라.
입력 :
The first line of the input includes the number of test cases, 1 ≤ t ≤ 1000. Each test case is a line containing an integer 1 ≤ x ≤ $2^(48)$.
출력 :
For each test case, print one line containing f(x) mod $10^9$
피보나치 수열 의 성질 (해당 노트에서 기본 성질 참고) 2번에서 $$ \left[ \begin{matrix} F_{n+1} & F_{n} \\ F_{n} & F_{n-1} \\ \end{matrix} \right] = \left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]^{n} $$ 이므로, 행렬의 빠른 거듭제곱을 이용해 문제를 풀 수 있습니다.
혹은 피보나치 수열의 성질에 따라 계산할 수도 있습니다. (성질 6번, 7번)
입력된 수 $n$에 대해서, $F_{n} \pmod{10^{9}}$의 값을 구해줍니다.
성질 6번, 7번을 이용하면 재귀적으로 시간복잡도 $O(\lg n)$에 풀 수 있습니다.
백준 11444번 - 피보나치 수 6 랑 굉장히 비슷한데, 다른 거라고는 여러번 계산 한다는 점과, 제한이 약간 다르다는 점, 나누는 수가 다르다는 점 뿐입니다.
-번째 푼 문제 (2022/--/--)