有一個數列,頭兩個數是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$。
輸入只有一行,有五個正整數,依序為$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 |
由於$x_n$的數值可能很大,請輸出$x_n$除以$1000000007$的餘數。
2018 TOI入營考pC
No. | Testdata Range | Score |
---|---|---|
1 | 0~4 | 10 |
2 | 5~12 | 10 |
3 | 13~26 | 10 |
4 | 27~49 | 70 |
No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
---|---|---|---|---|
0 | 1000 | 262144 | 262144 | |
1 | 1000 | 262144 | 262144 | |
2 | 1000 | 262144 | 262144 | |
3 | 1000 | 262144 | 262144 | |
4 | 1000 | 262144 | 262144 | |
5 | 1000 | 262144 | 262144 | |
6 | 1000 | 262144 | 262144 | |
7 | 1000 | 262144 | 262144 | |
8 | 1000 | 262144 | 262144 | |
9 | 1000 | 262144 | 262144 | |
10 | 1000 | 262144 | 262144 | |
11 | 1000 | 262144 | 262144 | |
12 | 1000 | 262144 | 262144 | |
13 | 1000 | 262144 | 262144 | |
14 | 1000 | 262144 | 262144 | |
15 | 1000 | 262144 | 262144 | |
16 | 1000 | 262144 | 262144 | |
17 | 1000 | 262144 | 262144 | |
18 | 1000 | 262144 | 262144 | |
19 | 1000 | 262144 | 262144 | |
20 | 1000 | 262144 | 262144 | |
21 | 1000 | 262144 | 262144 | |
22 | 1000 | 262144 | 262144 | |
23 | 1000 | 262144 | 262144 | |
24 | 1000 | 262144 | 262144 | |
25 | 1000 | 262144 | 262144 | |
26 | 1000 | 262144 | 262144 | |
27 | 1000 | 262144 | 262144 | |
28 | 1000 | 262144 | 262144 | |
29 | 1000 | 262144 | 262144 | |
30 | 1000 | 262144 | 262144 | |
31 | 1000 | 262144 | 262144 | |
32 | 1000 | 262144 | 262144 | |
33 | 1000 | 262144 | 262144 | |
34 | 1000 | 262144 | 262144 | |
35 | 1000 | 262144 | 262144 | |
36 | 1000 | 262144 | 262144 | |
37 | 1000 | 262144 | 262144 | |
38 | 1000 | 262144 | 262144 | |
39 | 1000 | 262144 | 262144 | |
40 | 1000 | 262144 | 262144 | |
41 | 1000 | 262144 | 262144 | |
42 | 1000 | 262144 | 262144 | |
43 | 1000 | 262144 | 262144 | |
44 | 1000 | 262144 | 262144 | |
45 | 1000 | 262144 | 262144 | |
46 | 1000 | 262144 | 262144 | |
47 | 1000 | 262144 | 262144 | |
48 | 1000 | 262144 | 262144 | |
49 | 1000 | 262144 | 262144 |