Dãy truy hồi bậc ba bằng lũy thừa ma trận

Buổi 59 — Lũy thừa ma trận Buổi 69-70 — Mock Tổng hợp Mathematics
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho dãy số $(F_n)$ được định nghĩa như sau:

  • $F_0 = x_0, F_1 = x_1, F_2 = x_2$
  • $F_n = (a \cdot F_{n-1} + b \cdot F_{n-2} + c \cdot F_{n-3}) \bmod (10^9 + 7)$ với mọi $n \ge 3$.

Cho $N, x_0, x_1, x_2, a, b, c$. Hãy tính $F_N \bmod (10^9 + 7)$.

Dữ liệu vào
  • Dòng đầu tiên chứa số nguyên $N$.
  • Dòng thứ hai chứa ba số nguyên $x_0, x_1, x_2$.
  • Dòng thứ ba chứa ba số nguyên $a, b, c$.
Dữ liệu ra

In ra một số nguyên duy nhất là $F_N \bmod (10^9 + 7)$.

Ví dụ
Input Output
5
0 1 1
1 1 1
7
Giới hạn

$0 \le N \le 10^{18}$, $0 \le x_0, x_1, x_2, a, b, c < 10^9 + 7$.

Draft saved