Zeroes

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 1G

Author:

Problem types

You are given an array of $N$ $N$ positive integers, $a_1, a_2, \dots a_N$ $a_{1}, a_{2}, \dots a_{N}$ . Let the value of an array be the number of trailing zeros in the product of all its elements. Determine the sum of the values of all subarrays of $a$ $a$ .

Constraints

$1 \le N \le 5 \times 10^5$ $1 \leq N \leq 5 \times 10^{5}$
$1 \le a_i \le 10^9$ $1 \leq a_{i} \leq 10^{9}$

Subtask 1 [20%]

$1 \le N \le 5\,000$ $1 \leq N \leq 5 000$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line contains one integer, $N$ $N$ , the length of the array.

The next line contains $N$ $N$ space-separated integers, $a_1, a_2, \dots, a_N$ $a_{1}, a_{2}, \dots, a_{N}$ , the array of positive integers.

Output Specification

Output one line containing one integer, the sum of the values of all subarrays.

Note: This number may not fit within a 32-bit integer type.

Sample Input 1

Copy

5
3 1 4 1 5

Sample Output 1

Copy

Explanation for Sample 1

The only $3$ $3$ subarrays with a nonzero value are $[4,1,5]$ $[4, 1, 5]$ , $[1,4,1,5]$ $[1, 4, 1, 5]$ , and $[3,1,4,1,5]$ $[3, 1, 4, 1, 5]$ . The products of each subarray are $20$ $20$ , $20$ $20$ , and $60$ $60$ , respectively. Each product has only $1$ $1$ trailing zero, for a total value of $1 + 1 + 1 = 3$ $1 + 1 + 1 = 3$ . All of the other subarrays have products with no trailing zeroes.

Sample Input 2

Copy

7
10 2 5 4 5 6 7

Sample Output 2

Copy

Comments

0

tofu commented 81 days ago

marcorz