Link Sub: http://www.spoj.com/PTIT/problems/P155PROF/
Người Gửi: Dương Lee
- Problem:
Bạn được cho 1 dãy số được định nghĩa như sau:
F1 = x; F2 = y; Fi = Fi-1 + Fi+1.
Cho trước x, y. Hãy tính Fn % 1000000007 (109 + 7).
Input
Dòng đầu tiên gồm 2 số x, y (|x|, |y| ≤ 109)..
Dòng thứ 2 gồm số nguyên dương n (1 ≤ n ≤ 2·109).
Output
In ra một số nguyên duy nhất là đáp án của bài toán.
Example:
In ra một số nguyên duy nhất là đáp án của bài toán.
Input
2 3
3
Output:
1
Input
0 -1
2
Output:
1000000006
Input
0 -1
2
Output:
1000000006
- Solution:
Giải thích test 2: F2 = -1, -1 % (1000000007) = 1000000006.- Quy luật của bài này là cứ 6 số lại lặp lại F_n.
Vậy nên chỉ cần biết quy luật thì độ phức tạp chỉ còn là O(n%6); Chỉ cần chú ý thêm về nến nó là số âm thì cộng thêm 1000000007 là được.