No.194 フィボナッチ数列の理解(1)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 79
作問者 : kmjpkmjp
8 ProblemId : 381 / 出題時の順位表

問題文

yuki君はyukicoderで門松列に対しスーパーリッチ門松列というものがあることを学んだ。
フィボナッチ数列に興味を持ったyuki君は、同様にスーパーフィボナッチ数列というものを考えてみた。

スーパーフィボナッチ数列は、最初のN項\(A_1, A_2, ... , A_N\)から生成される数列であり、第k項の値\(F(k)\)は、直前のN項の和となる。
厳密に書くと、\(F(k)\)は以下のように定義される。
- \(k\le N\)ならば \(\displaystyle F(k) = A_k \)
- \(k\gt N\)ならば \(\displaystyle F(k) = F(k-1) + F(k-2) + ... + F(k-N) = \sum_{1\le i \le N} F(k-i)\)

yuki君は大きな整数\(K\)に対し、\(F(K)\)及び\(\displaystyle S(K) = \sum_{1\le k \le K} F(k)\)がどうなるか気になった。
\(F(K)\)および\(S(K)\)の値の\(10^9+7\)の剰余を答えよ。

入力

\(N\) \(K\)
\(A_1\) \(A_2\) ... \(A_N\)

\(N, K, A_i\)はいずれも整数である。
本問題はテストケースごとに以下の制限がある。
testcase01~10: \(2 \le N \le 10^4, N \lt K \le 10^6\) (難易度★★相当)
testcase11~20: \(2 \le N \le 30, N \lt K \le 10^{12}\) (難易度★★★相当)
いずれのケースも、\(0 \le A_i \le 9\)は共通である。

ヒント:両ケース群に対し、1つのアプローチで挑むのが良いとは限らない。

出力

\(F(K)\)および\(S(K)\)の値を求め、それぞれ\(10^9+7\)の剰余を取った値を空白区切りで1行で答えよ。

サンプル

サンプル1
入力
2 5
1 1
出力
5 12

このスーパーフィボナッチ数列は、通常のフィボナッチ数列と同じである。
この数列の最初の5項は1, 1, 2, 3, 5である。

サンプル2
入力
5 10
1 2 3 4 5
出力
214 438

このスーパーフィボナッチ数列の最初の10項は、1, 2, 3, 4, 5, 15, 29, 56, 109, 214である。

サンプル3
入力
30 987654321012
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7
出力
923032656 920866414

このサンプルケースの制限は、testcase11~20に相当する。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。