Dãy truy hồi bậc ba bằng lũy thừa ma trận
Points
50
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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$.
Community Discussion