UTS Open '21 P7 - April Fools - DMOJ: Modern Online Judge

UTS Open '21 P7 - April Fools

View as PDF

Submit solution

All submissions

Best submissions

Points: 30 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

4fecta

Problem type

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)$ $MSB (x)$ as the index of the most significant bit in the binary representation of $x$ $x$ . Given a $1$ $1$ -indexed array $A$ $A$ with $N$ $N$ elements, a permutation of $A$ $A$ is defined as stably decreasing if for all $i > 1$ $i > 1$ , $A_{i-1} > A_i$ $A_{i - 1} > A_{i}$ or $|\text{MSB}(A_{i-1}) - \text{MSB}(A_i)| = 1$ $| MSB (A_{i - 1}) - 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$ $A$ . Two permutations are considered different if at any index $i$ $i$ , the value at index $i$ $i$ of the two permutations are different.

Constraints

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 \leq N \leq 500$

$1 \le A_i \le 10^9$ $1 \leq A_{i} \leq 10^{9}$

All $A_i$ $A_{i}$ are pairwise distinct.

Subtask 1 [10%]

$1 \le N \le 10$ $1 \leq N \leq 10$

Subtask 2 [30%]

$1 \le N \le 50$ $1 \leq N \leq 50$

Subtask 3 [20%]

$1 \le N \le 100$ $1 \leq N \leq 100$

Subtask 4 [40%]

No additional constraints.

Input Specification

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

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

Output Specification

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

Sample Input 1

Copy

3
1 3 2

Sample Output 1

Copy

Explanation for Sample 1

The four stably decreasing permutations are:

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

And the two other permutations are:

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

Sample Input 2

Copy

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

Sample Output 2

Copy

994855688

Explanation for Sample 2

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

Comments

There are no comments at the moment.