Equal bitwise operations

★★★★★

3.2

25 votes

Basic Programming, Basics of Implementation, Bit Manipulation, Implementation, Permutation and combination

Details

Submissions

Discussion

Editorial

Problem

A sequence of integers is said to be beautiful if the bitwise AND, OR, and XOR of its elements are pairwise equal to each other.

You are given a sequence $A$ of size $N$ . Find the number of non-empty subsequences of $A$ that are beautiful. Print the answer modulo $10^9 + 7$ .

Input format

The first line contains an integer $N$ representing the number of elements in the sequence.
The second line contains $N$ space-separated integers $A_1,\ A_2,\ ...,\ A_N$ representing the sequence.

Output format

In a single line, print the number of non-empty subsequences of $A$ that are beautiful.

Constraints

$1 \leq N \leq 2 \cdot 10^5\\ 0 \leq A_i \leq 10^{9}$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Here the subsequence $\{A_1,A_3,A_5\}$ is not beautiful. This is because:

$A_1 \& A_3 \& A_5 = 1 \& 2 \& 2 = 0$

$A_1 | A_3 | A_5 = 1 | 2 | 2 = 3$

$A_1 ⊕ A_3 ⊕ A_5 = 1 ⊕ 2 ⊕ 2 = 1$

For a subsequence to be beautiful, these three values should be equal to each other.

( $\&$ represents bitwise AND, $|$ represents bitwise OR, $⊕$ represents bitwise XOR)