2053 . 費氏數列（Fibonacci）

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
Waimai∼

User's AC Ratio

88.8% (317/357)

Submission's AC Ratio

59.2% (485/819)

Tags

TOI TOI-pre 2018-TOI-pre

Description

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

Input Format

輸入只有一行，有五個正整數，依序為x1,x2,a,b,n(0≤x1,x2,a,b≤109,3≤n≤109，數值間以空白隔開。

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

Output Format

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

Sample Input 1

0 1 1 1 5

Sample Output 1

3

Sample Input 2

0 1 1 1 50

Sample Output 2

778742000

Sample Input 3

3 4 5 6 999

Sample Output 3

434708377

Sample Input 4

999999999 999999999 999999999 999999999 999999999

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 (VSS, 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
Back to Top