問題一覧 > 通常問題

No.1268 Fruit Rush 2

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 102
作問者 : 👑 stoqstoq / テスター : hanyuhanyu
9 ProblemId : 4447 / 出題時の順位表
問題文最終更新日: 2020-10-23 23:44:15

問題文

フィボナッチ数列 $\{F_i\}$ は、 $F_0 = F_1 = 1, \ F_{i+2} = F_{i+1} + F_i \ (i \geq 0)$ で定義される数列です。 フィボナッチ数列に含まれる数をフィボナッチ数と言います。

$N$ 個の果物があり、 $i$ 個目の果物の新鮮さは $F_{A_i}$ です。
ここで $A_i$ は正の整数で、特に $A_i \neq 0$ です。 また、 $i \neq j$ ならば $A_i \neq A_j$ です。

はにゅさんはここから $1$ 個以上 $N$ 個以下の果物を選んでミックスジュースを作ります。
はにゅさんはフィボナッチ数が大好きなので、選んだ果物の新鮮さの総和が再びフィボナッチ数となるように果物を選びたいです。
このような果物の選び方の総数を求めてください。(解はこの制約下で $10^{18}$ を超えないことが証明できます。)

2つの果物の選び方が異なるとは、一方では選ばれているがもう一方では選ばれていない果物が存在することを指します。

入力

$N$
$A_1\ A_2\ \dots \ A_N$

  • 入力は全て整数
  • $1 \leq N \leq 2 \times 10^5$
  • $1 \leq A_i \leq 10^{18}$
  • $i \neq j$ ならば $A_i \neq A_j$

出力

新鮮さの総和がフィボナッチ数となる果物の選び方の総数を出力してください。

サンプル

サンプル1
入力
3
3 4 5
出力
5

果物の新鮮さはそれぞれ $F_3=3,F_4=5,F_5=8$ で、条件を満たす選び方は次の5通りです。(2020/10/23 23:43 誤植を修正しました。)

  • $3 = F_3$
  • $5 = F_4$
  • $8 = F_5$
  • $3+5 = F_5$
  • $5+8 = F_6$

サンプル2
入力
4
1 10 100 1000
出力
4

サンプル3
入力
8
3 1 4 15 9 2 6 5
出力
17

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