| 2017 JUST Programming Contest 4.0 |
|---|
| Finished |
You are given an array a consisting of n integers. A subarray (l, r) from array a is defined as non-empty sequence of consecutive elements al, al + 1, ..., ar.
The beauty of a subarray (l, r) is calculated as the bitwise AND for all elements in the subarray:
Your task is to calculate the summation of the beauty of all subarrays (l, r) (1 ≤ l ≤ r ≤ n):
The first line contains an integer T, where T is the number of test cases.
The first line of each test case contains an integer n (1 ≤ n ≤ 105), where n is the size of the array a.
The second line of each test case contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106), giving the array a.
For each test case, print a single line containing the summation of the beauty of all subarrays in the given array.
2
3
7 11 9
4
11 9 6 11
40
48
As input/output can reach huge size it is recommended to use fast input/output methods: for example, prefer to use scanf/printf instead of cin/cout in C++, prefer to use BufferedReader/PrintWriter instead of Scanner/System.out in Java.
A bitwise AND takes two equal-length binary representations and performs the logical AND operation on each pair of the corresponding bits, by multiplying them. Thus, if both bits in the compared position are 1, the bit in the resulting binary representation is 1 (1 × 1 = 1); otherwise, the result is 0 (1 × 0 = 0 and 0 × 0 = 0). This operation exists in all modern programming languages, for example in language C++ and Java it is marked as &.
In the first test case, the answer is calculated as summation of 6 subarrays as follow:
