DP - Hàm số
Point: 100.0
Time limit: 1.0s
Memory limit: 586 M
Input:
stdin
Output:
stdout
Author:
Problem type
Quy hoạch động: Nhân ma trận
Ngôn ngữ cho phép
C, C#, C++, Java, Pascal, Python, Text
Ta định nghĩa hàm số
\[ f(x) =
\begin{cases}
a & \quad \text{nếu } x = 1\\
b & \quad \text{nếu } x = 2\\
(a \times f(x-1) + b \times f(x-2)) \pmod{MOD}\ & \quad \text{nếu } x \ge 3
\end{cases}
\]
Dữ liệu
Một dòng duy nhất ghi \(4\) số nguyên dương \(a,\ b,\ N,\ MOD\ (a,\ b,\ N,\ MOD \le 10^{18})\)
Kết quả
In ra một số nguyên duy nhất là giá trị của \(f(N).\)
Ví dụ
| INPUT | OUTPUT |
|---|---|
| \(2\ 3\ 7\ 10005\) | \(912\) |
Giải thích
Với \(a = 2,\ b = 3,\ N = 7\) và \(MOD = 10005\), ta có:
-
\(i = 1, f(1) = 2\)
-
\(i = 2, f(2) = 3\)
-
\(i = 3, f(3) = 12\)
-
\(i = 4, f(4) = 33\)
-
\(i = 5, f(5) = 102\)
-
\(i = 6, f(6) = 303\)
-
\(i = 7, f(7) = 912\)
Giới hạn
- Subtask \(1\ (20\%\) số test\():\) \(a, b, N \le 10^5; MOD \le 10^{9}\)
- Subtask \(2\ (20\%\) số test\():\) \(a, b, N \le 10^5\)
- Subtask \(3\ (30\%\) số test\():\) \(a, b, N \le 10^9; MOD \le 10\)
- Subtask \(4\ (10\%\) số test\():\) \(a, b, N \le 10^9; MOD \le 10^{9}\)
- Subtask \(5\ (20\%\) số test\():\) Không có ràng buộc gì thêm.