Bitwise AND sum

★★★★★

3.5

23 votes

Data Structures, Implementation, C++, Arrays, Basics of bit manipulation, Bit manipulation, 1-D

Details

Submissions

Discussion

Editorial

Problem

You are given an array $A$ consisting of $N$ positive integers. Here, $f(i, j)$ is defined as the bitwise AND of all elements of the array $A$ after replacing all elements of $A$ in range $[i, j]$ (both inclusive) with $(2^{25} - 1)$ . Your task is to find:
$-f(1, N) + \sum\limits_{i=1}^{N} \sum\limits_{j=i}^{N} f(i, j)$

Note that after calculating the value $f(i, j)$ for some $(i, j)$ , the array is restored back to its original form. Therefore, calculating $f(i, j)$ for each $(i, j)$ pair is independent.

You are given $T$ test cases.

Warning: Use FAST I/O Methods.

Input format

The first line contains a single integer $T$ denoting number of test cases.
For each test case:
- The first line contains a single integer $N$ denoting the length of the array.
- The second line contains $N$ space-separated integers denoting the integer array $A$ .

Output format

For each test case, print the required sum in a separate line.

Constraints

$1 \le T \le 1000 \\ 1 \le N \le 5 \times 10^5 \\ 0 \le A_i < 2^{25} \\ \text{Sum of N over all test cases does not exceed } 10^6$

Time Limit: 1

Memory Limit: 256

Source Limit:

Explanation

Consider the first test case, $N = 3$ , $A = [3, 4, 1]$ . We want to evaluate $f(1, 1) + f(1, 2) + f(2, 2) + f(2, 3) + f(3, 3)$ . Calculations are shown below:

$f(1, 1)$ : Replace $A_1$ with $(2^{25} - 1)$ , we get $A = [33554431, 4, 1]$ , Bitwise AND of elements is 0.
$f(1, 2)$ : Replace $A_1, A_2$ with $(2^{25} - 1)$ , we get $A = [33554431, 33554431, 1]$ , Bitwise AND of elements is 1.
$f(2, 2)$ : Replace $A_2$ with $(2^{25} - 1)$ , we get $A = [3, 33554431, 1]$ , Bitwise AND of elements is 1.
$f(2, 3)$ : Replace $A_2, A_3$ with $(2^{25} - 1)$ , we get $A = [3, 33554431, 33554431]$ , Bitwise AND of elements is 3.
$f(3, 3)$ : Replace $A_3$ with $(2^{25} - 1)$ , we get $A = [3, 4, 33554431]$ , Bitwise AND of elements is 0.
The sum is $0 + 1 + 1 + 3 + 0 = 5$ .

Consider the second test case, $N = 2$ , $A = [4, 2]$ . We want to evaluate $f(1, 1) + f(2, 2)$ . Calculations are shown below:

$f(1, 1)$ : Replace $A_1$ with $(2^{25} - 1)$ , we get $A = [33554431, 2]$ , Bitwise AND of elements is 2.
$f(2, 2)$ : Replace $A_2$ with $(2^{25} - 1)$ , we get $A = [4, 33554431]$ , Bitwise AND of elements is 4.
The sum is $2 + 4 = 6$ .