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] Dãy truy hồi tuyến tính bậc hai

    Cho dãy xác định bởi công thức truy hồi tuyến tính bậc hai:

    an=p an−1+q an−2(n≥2),a_n = p\, a_{n-1} + q\, a_{n-2} \quad (n \ge 2),an​=pan−1​+qan−2​(n≥2),

    với hai số hạng đầu a0,a1a_0, a_1a0​,a1​ cho trước. Hãy tính an mod (109+7)a_n \bmod (10^9+7)an​mod(109+7).

    Ví dụ: với p=1,q=1,a0=0,a1=1p=1, q=1, a_0=0, a_1=1p=1,q=1,a0​=0,a1​=1 ta được dãy Fibonacci; a6=8a_6 = 8a6​=8.

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

      Dòng 1: ppp và qqq. Dòng 2: a0a_0a0​ và a1a_1a1​. Dòng 3: nnn.

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

      0≤p,q,a0,a1≤1090 \le p, q, a_0, a_1 \le 10^90≤p,q,a0​,a1​≤109, 0≤n≤1070 \le n \le 10^70≤n≤107.

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

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

    Ví dụ:

    Đầu vào:

    1 1
0 1
6

    Đầu ra:

    8

    Giải thích:

    Dãy Fibonacci 0,1,1,2,3,5,8 nên $a_6=8$.

    Đang tải editor...