사용자 도구

사이트 도구


ps:problems:boj:11440

피보나치 수의 제곱의 합

ps
링크acmicpc.net/…
출처BOJ
문제 번호11440
문제명피보나치 수의 제곱의 합
레벨플래티넘 5
분류

피보나치

시간복잡도O(logn)
인풋사이즈n<=10^18
사용한 언어Python 3.11
제출기록31388KB / 44ms
최고기록36ms
해결날짜2023/02/13

풀이

  • 제목 그대로 피보나치 수의 제곱의 합을 구하면 된다.
  • 피보나치 수 (Fibonacci numbers)에서 언급했듯이 F(0)^2+F(1)^2+…+F(n)^2 = F(n)*F(n+1)이 성립한다.
  • 따라서, n번째와 n+1번째 피보나치 수를 구해서 곱한 값을 출력하면 끝. 시간복잡도는 O(logn)

코드

"""Solution code for "BOJ 11440. 피보나치 수의 제곱의 합".

- Problem link: https://www.acmicpc.net/problem/11440
- Solution link: http://www.teferi.net/ps/problems/boj/11440

Tags: [Fibonacci]
"""

from teflib import combinatorics

MOD = 1_000_000_007


def main():
    n = int(input())
    print(
        combinatorics.fibonacci(n, MOD)
        * combinatorics.fibonacci(n + 1, MOD)
        % MOD
    )


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X Y I N Y
 
ps/problems/boj/11440.txt · 마지막으로 수정됨: 2023/02/13 08:49 저자 teferi