Truy Hồi Kèm Đa Thức Bậc Hai

Buổi 59 — Lũy thừa ma trận
Points
75
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho dãy số $(a_n)$ xác định với $a_0, a_1$ cho trước và với mọi $n \ge 2$: \[a_n = c_1 a_{n-1} + c_2 a_{n-2} + p n^2 + q n + r\] Hãy tính $a_N \bmod (10^9 + 7)$.

Dữ liệu vào
  • Dòng đầu chứa số nguyên $N$ ($0 \le N \le 10^{18}$).
  • Dòng thứ hai chứa hai số $a_0, a_1$ và hai hệ số $c_1, c_2$.
  • Dòng thứ ba chứa ba hệ số $p, q, r$. Tất cả các hệ số và giá trị ban đầu là số nguyên không âm nhỏ hơn $10^9 + 7$.
Dữ liệu ra

Một số nguyên duy nhất là $a_N \bmod (10^9 + 7)$.

Ví dụ
Input Output
4
1 2 1 1
1 0 0
41
10
0 1 2 3
1 2 3
125437
Giới hạn
  • $0 \le N \le 10^{18}$
Draft saved