No.1268 Fruit Rush 2
タグ : / 解いたユーザー数 127
作問者 : stoq / テスター : hanyu
問題文
フィボナッチ数列 $\{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もしくは右上の雲マークをクリックしてアカウントを作成してください。