AND Sequences (Codeforces 1513B)
Tags: Math, bitmasks

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

Input: 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: Output $$$t$$$ lines, where the $$$i$$$-th line contains the number of good permutations in the $$$i$$$-th test case modulo $$$10^9 + 7$$$.

Note: 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]$$$.In the second test case, it can be proved that no permutation exists for which the sequence is good.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   $$$ s_1 = s_2 \: \& \: s_3 \: \& \: s_4 \: \& \: s_5 = 0$$$,  $$$ s_1 \: \& \: s_2 = s_3 \: \& \: s_4 \: \& \: s_5 = 0$$$,  $$$ s_1 \: \& \: s_2 \: \& \: s_3 = s_4 \: \& \: s_5 = 0$$$,  $$$ s_1 \: \& \: s_2 \: \& \: s_3 \: \& \: s_4 = s_5 = 0$$$.  

Sample Inputs:
4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1

Sample Outputs:
6
0
36
4

Solution (Python):
import sys
input = sys.stdin.readline
t = 1
mod = int(1000000000.0 + 7)
t = int(input())
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    mi = min(a)
    for i in a:
        if i == mi:
            ans += 1
        elif mi & i != mi:
            print('0')
            break
    else:
        fact = 1
        for i in range(1, n - 1):
            fact = fact * i % mod
        res = ans * (ans - 1) % mod
        res = res * fact % mod
        print(res)

Solution (Python):
from __future__ import division, print_function

def main():
    from sys import stdin
    input = stdin.readline
    mod = 10 ** 9 + 7
    for test in range(int(input())):
        n = int(input())
        lst = list(map(int, input().split()))
        bit = lst[0]
        for i in lst[1:]:
            bit &= i
        x = lst.count(bit)
        fact = 1
        for i in range(2, n - 1):
            fact = fact * i % mod
        print(x * (x - 1) * fact % mod)
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
    newlines = 0

    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = 'x' in file.mode or 'w' in file.mode
        self.write = super(FastIO, self).write if self.writable else None

    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
        return s

    def read(self):
        while self._fill():
            pass
        return super(FastIO, self).read()

    def readline(self):
        while self.newlines == 0:
            s = self._fill()
            self.newlines = s.count(b'\n') + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            (self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s: self.buffer.write(s.encode('ascii'))
            self.read = lambda : self.buffer.read().decode('ascii')
            self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import sys

class ostream:

    def __lshift__(self, a):
        sys.stdout.write(str(a))
        return self
cout = ostream()
endl = '\n'

def readnumbers(zero=0):
    conv = ord if py2 else lambda x: x
    A = []
    numb = zero
    sign = 1
    i = 0
    s = sys.stdin.buffer.read()
    try:
        while True:
            if s[i] >= b'0'[0]:
                numb = 10 * numb + conv(s[i]) - 48
            elif s[i] == b'-'[0]:
                sign = -1
            elif s[i] != b'\r'[0]:
                A.append(sign * numb)
                numb = zero
                sign = 1
            i += 1
    except:
        pass
    if s and s[-1] >= b'0'[0]:
        A.append(sign * numb)
    return A
if __name__ == '__main__':
    main()

Solution (Python):
def cf1513B():
    MOD = 10 ** 9 + 7
    n = int(input())
    nums = list(map(int, input().split()))
    res = nums[0]
    for x in nums:
        res &= x
    cnt = 0
    for x in nums:
        if x == res:
            cnt += 1
    ans = cnt * (cnt - 1)
    for i in range(2, n - 1):
        ans = ans * i % MOD
    print(ans)
    return
if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        cf1513B()