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

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

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

問題一覧 > 通常問題

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

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

hirakich1048576 / テスター :

ixmel

9 ProblemId : 1240 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2018-07-27 22:49:59

問題文

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

入力

$N$

$1 ≦ N ≦ 10^{10}$

出力

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

サンプル

サンプル1

入力

出力

$1^{2} + 1^{2} + 2^{2} + 3^{2} + 5^{2} + 8^{2} + 13^{2} + 21^{2}$ の値 $714$ が答えです．

サンプル2

入力

33550336

出力

381853718

サンプル3

入力

10000000000

出力

128493982

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

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

yukicoder

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

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力

サンプル3

入力

出力