Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Giải thuật] Lũy thừa ma trận và số Fibonacci

    Cho số nguyên nnn. Hãy tính số Fibonacci thứ nnn theo modulo 109+710^9+7109+7, với F1=1,F2=1,Fk=Fk−1+Fk−2F_1 = 1, F_2 = 1, F_k = F_{k-1} + F_{k-2}F1​=1,F2​=1,Fk​=Fk−1​+Fk−2​. Yêu cầu dùng lũy thừa nhanh ma trận 2×22\times22×2 để chạy O(log⁡n)O(\log n)O(logn).

    • Định dạng đầu vào:

      Một dòng chứa số nguyên nnn.

    • Ràng buộc đầu vào:

      1≤n≤10181 \le n \le 10^{18}1≤n≤1018.

    • Định dạng đầu ra:

      In Fn mod (109+7)F_n \bmod (10^9+7)Fn​mod(109+7).

    Ví dụ:

    Đầu vào:

    10

    Đầu ra:

    55

    Giải thích:

    Dãy Fibonacci: 1,1,2,3,5,8,13,21,34,55; F_10 = 55.

    Đang tải editor...