BSSPC '22 P5 - Derrick and Orz Trees

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

Derrick is cultivating a garden of N Orz Trees, planted in a line. Derrick's garden can be represented by a sequence of positive integers H_1, H_2, \dots, H_N, with H_i representing the height of the i^\text{th} Orz Tree in the line.

Derrick wants to grow more Orz Trees in his garden, but he ran out of Orz Seedlings to plant. Fortunately, Orz Trees aren't like other trees. When an Orz Tree with even height is cut down, two Orz Trees with exactly half the height of the tree appear side-by-side in its place! Note that it is impossible to cut down an Orz Tree with odd height.

Derrick wants to know, after cutting down 0 or more Orz Trees with even height, how many distinct gardens can he make? Two gardens are distinct if and only if the sequences representing the heights of the trees in the gardens are distinct. Since the answer may be very large, output it modulo 10^9+7.


1 \le N \le 2 \times 10^5

1 \le H_i \le 10^{18}

Subtask 1 [50%]

1 \le N \le 10^3

1 \le H_i \le 10^3

Subtask 2 [50%]

No additional constraints.

Input Specification

The first line contains an integer N, the initial number of Orz Trees in Derrick's garden.

The second line contains N integers H_i, the height of the i^\text{th} tree in Derrick's garden.

Output Specification

Output a single integer, the number of distinct gardens Derrick can make by cutting down 0 or more Orz Trees with even height, modulo 10^9+7.

Sample Input 1

6 5 2

Sample Output 1


Explanation for Sample Output 1

Derrick can choose to cut down the first and/or last Orz Trees, or to cut down nothing. The 4 possible gardens he can make are [6, 5, 2], [3, 3, 5, 2], [6, 5, 1, 1], and [3, 3, 5, 1, 1].

Sample Input 2


Sample Output 2


Explanation for Sample Output 2

If Derrick cuts down the tree of height 4, his garden becomes [2, 2]. From there, he can choose to cut down either, both, or neither of the trees of height 2. So, the 5 possible gardens he can make are [4], [2, 2], [1, 1, 2], [2, 1, 1], and [1, 1, 1, 1].


There are no comments at the moment.