UTS Open '21 P7 - April Fools

View as PDF

Submit solution

Points: 30 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Inaba is running her own competitive programming website called UTSOJ (UTSOJ: The Splendid Online Judge). As an April Fool's joke, she is planning to give everyone's rating graph a downwards trend! However, she does not want to anger her users too much, so she decides that their rating graph must be stably decreasing. She defines a stably decreasing rating graph as a rating graph where each subsequent rating is either lower than the previous rating, or the left-most bit of the current rating is one position off from the left-most bit of the previous rating. Formally, define \text{MSB}(x) as the index of the most significant bit in the binary representation of x. Given a 1-indexed array A with N elements, a permutation of A is defined as stably decreasing if for all i > 1, A_{i-1} > A_i or |\text{MSB}(A_{i-1}) - \text{MSB}(A_i)| = 1. Since Inaba wants to know how creative she can get, please help her find the number of different stably decreasing permutations of a given array A. Two permutations are considered different if at any index i, the value at index i of the two permutations are different.


For this problem, you will NOT be required to pass the sample cases in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N \le 500

1 \le A_i \le 10^9

All A_i are pairwise distinct.

Subtask 1 [10%]

1 \le N \le 10

Subtask 2 [30%]

1 \le N \le 50

Subtask 3 [20%]

1 \le N \le 100

Subtask 4 [40%]

No further constraints.

Input Specification

The first line contains an integer N, the length of A.

The next line contains N integers A_i (1 \le i \le N), representing the elements of array A.

Output Specification

Output one integer, representing the number of different stably decreasing permutations of A. Since this value may be large, output it modulo 10^9 + 7.

Sample Input 1

1 3 2

Sample Output 1


Explanation for Sample 1

The four stably decreasing permutations are:

[1, 3, 2] - valid because |\text{MSB}(A_1) - \text{MSB}(A_2)| = 1 and A_2 > A_3.
[2, 1, 3] - valid because A_1 > A_2 and |\text{MSB}(A_2) - \text{MSB}(A_3)| = 1.
[3, 1, 2] - valid because A_1 > A_2 and |\text{MSB}(A_2) - \text{MSB}(A_3)| = 1.
[3, 2, 1] - valid because A_1 > A_2 and A_2 > A_3.

And the two other permutations are:

[1, 2, 3] - invalid because A_2 < A_3 and |\text{MSB}(A_2) - \text{MSB}(A_3)| \ne 1.
[2, 3, 1] - invalid because A_1 < A_2 and |\text{MSB}(A_1) - \text{MSB}(A_2)| \ne 1.

Sample Input 2

1133 1010 1043 1289 1463 1587 1664 1769 1834 1915 1897 1951 1978 2014 2111 2133 2206 2267 2298

Sample Output 2


Explanation for Sample 2

Be sure to output your answer modulo 10^9 + 7.


There are no comments at the moment.