Bitwise AND sum

3.4

24 votes
Data Structures, Implementation, C++, Arrays, Basics of bit manipulation, Bit manipulation, 1-D
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$$.
Editor Image

?