No.720 行列のできるフィボナッチ数列道場 (2)

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

No.720 行列のできるフィボナッチ数列道場 (2)

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 60
作問者 :

hirakich1048576 / テスター :

ixmel

2 ProblemId : 1634 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2017-06-25 19:28:20

問題文

数列 $F_{i}$ を以下のように定義する．
${\begin{cases} F_{0} = 0 \\ F_{1} = 1 \\ F_{i + 2} = F_{i + 1} + F_{i} \end{cases}$
与えられる整数 $N, M$ に対して， $\sum_{i = 1}^{n} F_{i m} = \overset{n}{\overset{⏞}{F_{m} + F_{2 m} + \dots + F_{n m}}}$ を計算せよ．
答えは非常に大きな数になることがあるので， $1000000007$ で割った余りを答えよ．

入力

 $N M$

$1 ≦ N ≦ 10^{10}$
$2 ≦ M ≦ 30000$

出力

$\sum_{i = 1}^{n} F_{i m} = \overset{n}{\overset{⏞}{F_{m} + F_{2 m} + \dots + F_{n m}}}$ の値を $1000000007$ で割った余りを1行に出力せよ．

サンプル

サンプル1

入力

4 3

出力

$F_{1}$ から $F_{12}$ の値は順に $1, 1, \underset{―}{2}, 3, 5, \underset{―}{8}, 13, 21, \underset{―}{34}, 55, 89, \underset{―}{144}$ なので，
$2 + 8 + 34 + 144$ の値 $188$ が答えです．

サンプル2

入力

40964976 6561

出力

639430182

サンプル3

入力

8015993433 30000

出力

563904402

入力 $N$ は32bit整数に収まらないことがあります．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。

yukicoder

No.720 行列のできるフィボナッチ数列道場 (2)

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力