c012. 費氏數列 - TCFSH CIRC Judge

內容

有一個數列，頭兩個數是 $0$ 和 $1$，接下來的每一個數 $x_n$，都是兩個數的和，例如第三個數是 $0 + 1 = 1$，第四個數是 $1 + 1 = 2$，第五個數是 $1 + 1 = 2$。我們知道這個數列是有名的費氏數列。
現在我們仿照費氏數列的生成方式來生成某個數列、該數列的頭兩個數是$ 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	$x_1 = 0, x_2 = 1, a = b = 1, n\leq 30$	10
2	$x_1 = 0, x_2 = 1, a = b =1, n\leq 100$	10
3	$n \leq 1000$	10
4	無	70

輸出說明

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

範例輸入 #1

0 1 1 1 5

範例輸出 #1

範例輸入 #2

0 1 1 1 50

範例輸出 #2

778742000

範例輸入 #3

3 4 5 6 999

範例輸出 #3

434708377

範例輸入 #4

999999999 999999999 999999999 999999999 999999999

範例輸出 #4

302734374

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1K
公開測資點#2 (10%): 1.0s , <1K
公開測資點#3 (10%): 1.0s , <1K
公開測資點#4 (10%): 1.0s , <1K
公開測資點#5 (10%): 1.0s , <1K
公開測資點#6 (10%): 1.0s , <1K
公開測資點#7 (10%): 1.0s , <1K
公開測資點#8 (10%): 1.0s , <1K
公開測資點#9 (10%): 1.0s , <1K

提示：

本題出自 2018 TOI Pre (TIOJ 2053)

標籤:

Matrix 快速冪

出處:

2018 TOI Pre TIOJ 2053 [管理者：

nevikw39 ($\mathscr{nevikw}\pmb{39}\in\mathbf{37}^{th}$)

]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」