a311. 類費式數列的第n項 - 彰化精誠中學

內容

相信大家都有聽過大名鼎鼎的費波那契與他的數列：$F(n) = F(n-1) + F(n-2)$

矩政∙城法是一名高校生，他最近對費氏數列很有興趣。他想出了一種「類費氏」數列: $G(n) = G(n-1) + G(n-2) + G(n-3)$。沒過多久，他又覺得這個數列過於簡單，實在有辱於自己天才般的頭腦，於是，他列出了以下的類費式數列的推廣式：
$$S(n) = a_1S(n-1)+a_2S(n-2)+a_3S(n-3)+...+a_kS(n-k)$$
寫下了這個漂亮的數學式後，矩政∙城法默默地為自己的聰明才智點了個讚...然後他就尷尬地發現，想計算這個類費式數列十分地困難－－計算量太龐大了。

於是矩政∙城法就把這個艱鉅的任務丟給了身為程式設計師的你：

給定一個類費式數列，請寫出一個能快速計算該數列第$n$項的程式。由於數字可能很大，矩政∙城法只要求計算最終結果除以$10^9+7$的餘數。

輸入說明

輸入第一行包含兩個整數 $k$、$n$。

第二行包含 $k$ 個整數 $a_1,\ a_2,\ ...,\ a_k$，代表
$S(n)=a_1S(n-1)+a_2S(n-2)+...+a_kS(n-k)$

第三行包含 $k$ 個整數 $b_1,\ b_2,\ ...,\ b_k$，代表
$S(1)=b_1,\ S(2)=b_2,\ ...,\ S(k)=b_k$

測資範圍：

$1 \leq k \leq 20$
$1 \leq n \leq 10^9$
- 有25%測資滿足 $1 \leq n \leq 10^5$
$0 \leq a_k,\ b_k \leq 10^5$

輸出說明

輸出一個整數，代表$S(n)$除以$10^9+7$的餘數。

範例輸入 #1

2 5
1 1
1 1

範例輸出 #1

範例輸入 #2

3 12
1 1 1
2 1 3

範例輸出 #2

測資資訊：

記憶體限制： 128 MB
不公開測資點#0 (12%): 1.0s , <1K
不公開測資點#1 (13%): 1.0s , <1K
不公開測資點#2 (12%): 1.0s , <1K
不公開測資點#3 (13%): 1.0s , <1K
不公開測資點#4 (12%): 1.0s , <1K
不公開測資點#5 (13%): 1.0s , <1K
不公開測資點#6 (12%): 1.0s , <1K
不公開測資點#7 (13%): 1.0s , <1K

提示：

第一筆測資即費氏數列。

第二筆測資，$S(n)=S(n-1)+S(n-2)+S(n-3)$

標籤:

快速冪數學

出處:

[管理者：

911091@stu.c... (17莊明達 David)

]

編號	身分	題目	主題	人氣	發表日期
27	bandanhahaha (別人刷題我被題刷)	a311	題目應該有些微錯誤	145	2023-04-13 02:55