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] Truy hồi tuyến tính bằng lũy thừa ma trận

    Cho dãy truy hồi tuyến tính bậc kkk:

    f(n)=c1f(n−1)+c2f(n−2)+⋯+ckf(n−k)f(n) = c_1 f(n-1) + c_2 f(n-2) + \dots + c_k f(n-k)f(n)=c1​f(n−1)+c2​f(n−2)+⋯+ck​f(n−k)

    với các giá trị khởi tạo f(0),f(1),…,f(k−1)f(0), f(1), \dots, f(k-1)f(0),f(1),…,f(k−1). Hãy tính f(N) mod (109+7)f(N) \bmod (10^9+7)f(N)mod(109+7) bằng kỹ thuật lũy thừa ma trận (companion matrix), với NNN có thể rất lớn.

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

      Dòng đầu chứa kkk và NNN. Dòng thứ hai chứa kkk hệ số c1,…,ckc_1, \dots, c_kc1​,…,ck​. Dòng thứ ba chứa kkk giá trị f(0),…,f(k−1)f(0), \dots, f(k-1)f(0),…,f(k−1).

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

      1≤k≤501 \le k \le 501≤k≤50, 0≤N≤10180 \le N \le 10^{18}0≤N≤1018, các hệ số và giá trị khởi tạo trong [0,109][0, 10^9][0,109].

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

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

    Ví dụ:

    Đầu vào:

    2 10
1 1
0 1

    Đầu ra:

    55

    Giải thích:

    Truy hoi Fibonacci $f(n)=f(n-1)+f(n-2)$, $f(0)=0,f(1)=1$. $f(10)=55$.

    Đang tải editor...