2053 . 費氏數列（Fibonacci）

Submit
Status
Ranklist
Back to Problems List

TopCoder

Thumb 1800
weyryafjnm;
erfvjuaweikm

User's AC Ratio

88.6% (187/211)

Submission's AC Ratio

59.3% (277/467)

Tags

TOI 2018-TOI-pre

Description

有一個數列，頭兩個數是0和1，接下來的每一個數$x_n$，都是兩個數的和，例如第三個數是$0 + 1 = 1$，第四個數是$1 + 1 = 2$，第五個數是$1 + 2 = 3$。我們知道這個數列是有名的費氏數列。
現在我們仿照費氏數列的生成方式來生成某個數列、該數列的頭兩個數是$x_1$和$x_2$，接下來的每一個數，都是$x_n = bx_{n - 1} + ax_{n - 2}$。給定$x_1, x_2, a, b$，請你寫一個程式計算指定的第$n$個數$x_n$。

Input Format

輸入只有一行，有五個正整數，依序為$x_1, x_2, a, b, n(0\leq x_1, x_2, a, b \leq 10^ 9, 3\leq n \leq 10^ 9$，數值間以空白隔開。

子任務（測資） 額外限制 分數
1 (0~4) $x_1 = 0, x_2 = 1, a = b = 1, n\leq 30$ 10
2 (5~12) $x_1 = 0, x_2 = 1, a = b =1, n\leq 100$ 10
3 (13~26) $n \leq 1000$ 10
4 (27~49) 無 70

Output Format

由於$x_n$的數值可能很大，請輸出$x_n$除以$1000000007$的餘數。

Sample Input

Sample Input #1
0 1 1 1 5

Sample Input #2
0 1 1 1 50

Sample Input #3
3 4 5 6 999

Sample Input #4
999999999 999999999 999999999 999999999 999999999

Sample Output

Sample Output #1
3

Sample Output #2
778742000

Sample Output #3
434708377

Sample Output #4
302734374

Hints

Problem Source

2018 TOI入營考pC

Subtasks

No. Testdata Range Score
1 0~4 10
2 5~12 10
3 13~26 10
4 27~49 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 262144 262144 1
1 1000 262144 262144 1
2 1000 262144 262144 1
3 1000 262144 262144 1
4 1000 262144 262144 1
5 1000 262144 262144 2
6 1000 262144 262144 2
7 1000 262144 262144 2
8 1000 262144 262144 2
9 1000 262144 262144 2
10 1000 262144 262144 2
11 1000 262144 262144 2
12 1000 262144 262144 2
13 1000 262144 262144 3
14 1000 262144 262144 3
15 1000 262144 262144 3
16 1000 262144 262144 3
17 1000 262144 262144 3
18 1000 262144 262144 3
19 1000 262144 262144 3
20 1000 262144 262144 3
21 1000 262144 262144 3
22 1000 262144 262144 3
23 1000 262144 262144 3
24 1000 262144 262144 3
25 1000 262144 262144 3
26 1000 262144 262144 3
27 1000 262144 262144 4
28 1000 262144 262144 4
29 1000 262144 262144 4
30 1000 262144 262144 4
31 1000 262144 262144 4
32 1000 262144 262144 4
33 1000 262144 262144 4
34 1000 262144 262144 4
35 1000 262144 262144 4
36 1000 262144 262144 4
37 1000 262144 262144 4
38 1000 262144 262144 4
39 1000 262144 262144 4
40 1000 262144 262144 4
41 1000 262144 262144 4
42 1000 262144 262144 4
43 1000 262144 262144 4
44 1000 262144 262144 4
45 1000 262144 262144 4
46 1000 262144 262144 4
47 1000 262144 262144 4
48 1000 262144 262144 4
49 1000 262144 262144 4
Submit
Status
Ranklist
Back to Top