フィボナッチ数列の性質②

2 secs 1024 MB
Aozora_Kotori_A's icon Aozora_Kotori_A

問題文

以下,フィボナッチ数列の第 nn 項を FnF_n とする。

与えられた自然数 nn に対して,フィボナッチ数列の第1項から第 nn 項までの平方和 SnS_n を出力せよ。

すなわち,

Sn=F12+F22++Fn2S_n={F_1}^2+{F_2}^2+\cdots+{F_n}^2

を出力すればよい。 ただし,必要であれば問題「フィボナッチ数列の性質①」で作成した関数 Fibonacci を利用しても構わない。

一般に

k=1nFk2=Fn×Fn+1\displaystyle\sum_{k=1}^n {F_k}^2= \underline{\phantom{F_n\times F_{n+1}}}

であることが知られている。(下線部は何が入るか考えてみよう)

制約

  • 入力はすべて自然数
  • 1n231\leqq n\leqq 23

 

入力

入力は以下の形式で標準入力から与えられます。

標準入力

nn

出力

SnS_n を以下の形式で出力してください。

標準出力

SnS_n

 

サンプル1

入力
8
出力
714

F1=1, F2=1, F3=2, F4=3, F5=5, F6=8, F7=13, F8=21F_1=1,\ F_2=1,\ F_3=2,\ F_4=3,\ F_5=5,\ F_6=8,\ F_7=13,\ F_8=21なので,

S8=12+12+22+32+52+82+132+212=714S_8=1^2+1^2+2^2+3^2+5^2+8^2+13^2+21^2=714

です。

 

サンプル2

入力
18
出力
10803704

Submit


Go (1.21)