codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.