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

    solution

    Đề bài: [Toán rời rạc] Fibonacci và Lucas mod nhanh

    Dãy Fibonacci: F0=0,F1=1,Fn=Fn−1+Fn−2F_0=0, F_1=1, F_n=F_{n-1}+F_{n-2}F0​=0,F1​=1,Fn​=Fn−1​+Fn−2​. Dãy Lucas: L0=2,L1=1,Ln=Ln−1+Ln−2L_0=2, L_1=1, L_n=L_{n-1}+L_{n-2}L0​=2,L1​=1,Ln​=Ln−1​+Ln−2​. Cho nnn rất lớn, hãy tính FnF_nFn​ và LnL_nLn​ modulo 109+710^9+7109+7 bằng kỹ thuật fast doubling.

    Công thức fast doubling: F2k=Fk(2Fk+1−Fk)F_{2k}=F_k(2F_{k+1}-F_k)F2k​=Fk​(2Fk+1​−Fk​), F2k+1=Fk+12+Fk2F_{2k+1}=F_{k+1}^2+F_k^2F2k+1​=Fk+12​+Fk2​, và Ln=2Fn+1−FnL_n = 2F_{n+1}-F_nLn​=2Fn+1​−Fn​.

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

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

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

      0≤n≤10180 \le n \le 10^{18}0≤n≤1018.

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

      Hai số nguyên cách nhau dấu cách: Fn mod (109+7)F_n \bmod (10^9+7)Fn​mod(109+7) và Ln mod (109+7)L_n \bmod (10^9+7)Ln​mod(109+7).

    Ví dụ:

    Đầu vào:

    10

    Đầu ra:

    55 123

    Giải thích:

    $F_{10}=55$ va $L_{10}=123$.

    Đang tải editor...