1513B.md (2316B)
1 Source: https://codeforces.com/problemset/problem/1513/B 2 3 B. AND Sequences 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 A sequence of $n$ non-negative integers ($n \ge 2$) $a_1, a_2, \dots, a_n$ is called good if for all $i$ from $1$ to $n-1$ the following condition holds true: $$a_1 \: \& \: a_2 \: \& \: \dots \: \& \: a_i = a_{i+1} \: \& \: a_{i+2} \: \& \: \dots \: \& \: a_n,$$ where $\&$ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). 22 23 You are given an array $a$ of size $n$ ($n \geq 2$). Find the number of permutations $p$ of numbers ranging from $1$ to $n$, for which the sequence $a_{p_1}$, $a_{p_2}$, ... ,$a_{p_n}$ is good. Since this number can be large, output it modulo $10^9+7$. 24 25 Input 26 27 The first line contains a single integer $t$ ($1 \leq t \leq 10^4$), denoting the number of test cases. 28 29 The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the size of the array. 30 31 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) — the elements of the array. 32 33 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2 \cdot 10^5$. 34 35 Output 36 37 Output $t$ lines, where the $i$-th line contains the number of good permutations in the $i$-th test case modulo $10^9 + 7$. 38 39 Example 40 41 Input 42 43 ``` 44 4 45 3 46 1 1 1 47 5 48 1 2 3 4 5 49 5 50 0 2 0 3 0 51 4 52 1 3 5 1 53 ``` 54 55 Output 56 57 ``` 58 6 59 0 60 36 61 4 62 ``` 63 64 Note 65 66 In the first test case, since all the numbers are equal, whatever permutation we take, the sequence is good. There are a total of $6$ permutations possible with numbers from $1$ to $3$: $[1,2,3]$, $[1,3,2]$, $[2,1,3]$, $[2,3,1]$, $[3,1,2]$, $[3,2,1]$. 67 68 In the second test case, it can be proved that no permutation exists for which the sequence is good. 69 70 In the third test case, there are a total of $36$ permutations for which the sequence is good. One of them is the permutation $[1,5,4,2,3]$ which results in the sequence $s=[0,0,3,2,0]$. This is a good sequence because 71 72 * $ s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0$, 73 * $ s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0$, 74 * $ s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0$, 75 * $ s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0$.