308402: CF1513B. AND Sequences
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
AND Sequences
题意翻译
一个 $n$ 个数的非负数组如果 $\forall i\in\left[1,n\right)$ ,有 $a_1$ & $a_2$ & $……$ & $a_i = a_{i+1}$ & $a_{i+2}$ & $……$ & $a_n$ ,那么这个数组叫做 $“$ 好的数组 $”$ 。其中&表示按位与。 给定一个长度为 $n$ 的数组,求这个数组有多少种排列是 $“$ 好的数组 $”$ 。因为这个数字可能很大,所以输出结果模 $10^9+7$ 即可。 两个排列不同,指这个排列有一个位置的数与其他排列的这一位置的数的下表不同。 例如: 如果原数组是 $1,1$ ,那么这个数组有 $2$ 个排列; 如果原数组是 $1,1,1$ ,那么这个数组有 $6$ 个排列。 **输入格式** 第一行输入一个整数 $t\left(1\le t\le10^4\right)$ ,表示数据组数。 每一组数据包含两行,第一行输入一个整数 $n\left(1\le\sum n\le2\times10^5\right)$ ,表示数组大小;第二行输入 $n$ 个整数 $a_1,a_2,……,a_n\left(1\le a_i\le10^9\right)$ ,表示数组中的数。 **输出格式** 对于每一组数据,输出 $1$ 个整数有多少种排列是 $“$ 好的数组 $”$ 。题目描述
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 <a href="https://en.wikipedia.org/wiki/Bitwise_operation#AND">bitwise AND operation</a>.</p><p>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$.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ), denoting the number of test cases. 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. 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. It is guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 2 \cdot 10^5 $ .
输出格式
Output $ t $ lines, where the $ i $ -th line contains the number of good permutations in the $ i $ -th test case modulo $ 10^9 + 7 $ .
输入输出样例
输入样例 #1
4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1
输出样例 #1
6
0
36
4