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] Tổng tiền tố của truy hồi kép

    Xét hai dãy đan xen với a0=1,b0=1a_0 = 1, b_0 = 1a0​=1,b0​=1 và:

    an=an−1+2 bn−1,bn=an−1+bn−1a_n = a_{n-1} + 2\,b_{n-1}, \qquad b_n = a_{n-1} + b_{n-1}an​=an−1​+2bn−1​,bn​=an−1​+bn−1​

    Hãy tính tổng tiền tố SN=∑i=0Nai mod (109+7)S_N = \sum_{i=0}^{N} a_i \bmod (10^9+7)SN​=∑i=0N​ai​mod(109+7). Vì NNN có thể rất lớn, hãy mở rộng trạng thái thành véc-tơ (an,bn,Sn)(a_n, b_n, S_n)(an​,bn​,Sn​) và dùng lũy thừa ma trận.

    • Đị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:

      Một số nguyên là SN mod (109+7)S_N \bmod (10^9+7)SN​mod(109+7).

    Ví dụ:

    Đầu vào:

    1

    Đầu ra:

    4

    Giải thích:

    $a_0=1,b_0=1$; $a_1=1+2\cdot1=3$. Tong $S_1=a_0+a_1=1+3=4$.

    Đang tải editor...