Subsomas de Fibonacci
#186
Made by: Crazynds
1000MB
1s
Dado um array $A$ de $N$ inteiros positivos, conte o número de pares $(l, r)$ com $1 \le l \le r \le N$ tal que
$$A[l] + A[l+1] + \cdots + A[r]$$
é um número de Fibonacci.
Considere a sequência de Fibonacci como $F(1)=1,\ F(2)=1,\ F(3)=2,\ F(4)=3,\ F(5)=5,\ \ldots$
Input
A primeira linha contém um inteiro $N$.
A segunda linha contém $N$ inteiros $A_i$.
$$1 \le N \le 3 \times 10^5, \quad 1 \le A_i \le 10^6$$
Output
Imprima um único inteiro: o número de subarrays cuja soma é um número de Fibonacci.
Input Example
Output Example
1 1
1
5 1 1 2 3 5
9
4 3 1 4 1
6
5 1 1 1 1 1
13