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] Số Pell P_n theo modulo

    Dãy Pell xác định bởi P0=0P_0=0P0​=0, P1=1P_1=1P1​=1 và truy hồi tuyến tính

    Pn=2Pn−1+Pn−2.P_n=2P_{n-1}+P_{n-2}.Pn​=2Pn−1​+Pn−2​.

    Cho nnn, in Pn mod (109+7)P_n \bmod (10^9+7)Pn​mod(109+7).

    • Đị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≤1070 \le n \le 10^70≤n≤107.

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

      Một dòng: Pn mod (109+7)P_n \bmod (10^9+7)Pn​mod(109+7).

    Ví dụ:

    Đầu vào:

    5

    Đầu ra:

    29

    Giải thích:

    Dãy Pell: $0,1,2,5,12,29$; vậy $P_5=29$.

    Đang tải editor...