Matrix Exponentiation - Fibonacci

View as PDF
Submit solution
Points: 0.04
Time limit: 0.25s
Memory limit: 256M
Input: stdin
Output: stdout
Suggester:
toha
Problem source:
Matrix Exponentiation
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Hãy tìm phần dư của phép chia lấy dư số Fibonacci thứ ~n~ cho ~10^9+7~.

Số Fibonacci thứ ~n~ ~(F_n)~ được xác định bởi dãy truy hồi sau:

~F_0 = 0, F_1 = 1~

~F_n = F_{n-1} + F_{n-2}\ (\forall n \geq 2)~

Input

Gồm ~1~ dòng chứa số nguyên ~n~ ~(0 \leq n \leq 10^{18})~.

Output

Phần dư của phép chia ~F_n~ cho ~10^9 + 7~.

Sample 1

Input
3
Output
2

Sample 2

Input
6
Output
8

Sample 3

Input
50
Output
586268941

~F_{50} = 12586269025 \equiv 586268941~ ~(mod ~ ~10^9 + 7)~.

Note

Một vài số hạng đầu tiên của dãy số Fibonacci là ~(0,1,1,2,3,5,8,13,…)~.

Comments

Please read the guidelines before commenting.


  • 1
    vominhmanh10  commented on Nov. 26, 2025, 12:07 p.m. ← edited

    dựa vào công thức ma trận:
    [[F(n + 1), F(n)], [F(n), F(n - 1)]] = [[1, 1], [1, 0]]^n

    ta có công thức nhân đôi F(2 * n) = F(n) * (2 * F(n - 1) + F(n)) = F(n) * (2 * F(n + 1) - F(n)),
    F(2 * n + 1) = F(n) ^ 2 + F(n + 1) ^ 2

    vậy ta tính F(n), F(n + 1) chỉ lấy F(n // 2), F(n // 2 + 1) cứ như thế trong O(log n)

    import sys
input = sys.stdin.readline

def solve(n):
    if n == 0: return 0, 1
    a, b = solve(n // 2)
    c = (a * (2 * b - a)) % mod
    d = (a * a + b * b) % mod
    if n % 2 == 0: return c, d
    return d, (c + d) % mod
mod = 10**9 + 7
if __name__ == "__main__":
    n = int(input())
    print(solve(n)[0] % mod)

  • 0
    haitin9Aps  commented on July 23, 2025, 2:34 a.m.

    có cao nhân nào chỉ em với, em dùng nhân ma trận vẫn không được full AC


    • -9
      haitin9Aps  commented on July 23, 2025, 2:37 a.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • -26
    chunguyen2k8  commented on April 1, 2024, 12:25 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -64
    nogo007akapkn  commented on March 3, 2024, 4:51 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.