Recall the basic properties of the $$$⊕$$$ operation: $$$A⊕0=A$$$, $$$A⊕A=0$$$, $$$A⊕B=B⊕A$$$.

Consider the cases of even and odd array lengths.

Note that $$$(a_1⊕x)⊕(a_2⊕x)⊕$$$... equals $$$a_1⊕a_2⊕…⊕a_n$$$ if $$$n$$$ is even, or $$$a_1⊕a_2⊕…⊕a_n⊕x$$$ if $$$n$$$ is odd. Then, if the length of the array is odd, you must print ⊕ of the whole array. And if the length is even, we can't change the value of the expression with our operation. It turns out that if ⊕ of the whole array is 0, we can output any number, but otherwise there is no answer.

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    xor = 0
    for x in a:
        xor ^= x
    if xor == 0:
        print(0)
    else:
        if n % 2 == 1:
            print(xor)
        else:
            print(-1)

Think what happens to the bitwise OR of the array elements when you perform the allowed operation. Can the overall OR value ever decrease?

Let m = a[1] | a[2] | ... | a[n].

• This value m is the lower bound of the array sum, since: m ≤ a[1] + a[2] + ... + a[n]
• This value is also achievable using valid operations:
  • Repeatedly pick two elements a[i], a[j]
  • Replace one of them with 0, and the other with a[i] | a[j] (which preserves the total OR)
  • Keep doing this until all but one element are 0, and one element holds the total OR m.
So, no matter how you do the operations, you can always reduce the array to [0, 0, ..., m], giving you a total sum of m.

Time Complexity: O(N)

t = int(input())
for _ in range(t):
   n = int(input())
   nums = [int(i) for i in input().split()]
   
   answer = 0
   for num in nums:
      answer |= num
            
   print(answer)

Try to compute the result of ai | z for each element.
You’ll notice z only gets worse (decreases or stays the same) with every operation.

You're given an array a and an integer z. You can perform the following operation any number of times:

• Pick an index i (1 ≤ i ≤ n)
• Set a[i] = a[i] | z
• Set z = a[i] & z

The key insight lies in understanding how the value of z changes after each operation.

Observations:

1. z is Monotonically Decreasing (Bitwise)

• The operation z = a[i] & z only unsets bits in z.
• Once a bit in z becomes 0, it can never become 1 again.
• This means z is most powerful (has the most 1s) at the beginning, and gets strictly worse the more you use it.

1. Best Use of z is at the Start

• Since z weakens over time, using it even once changes its value forever.
• So the most strategic approach is to try all possible a[i] | z without modifying z, and pick the maximum.

1. Why Not Simulate All Operations?

• With the above point, it becomes clear that using z even once may prevent reaching optimal results later.
• Trying all operation sequences would be overkill and unnecessary.

Approach:

1. For each ai in the array:

• Compute ai | z
• Track the maximum value among these.

1. Output the maximum value for each test case.

Example Walkthrough:

Input:

2 3  
3 4

• 3 | 3 = 3
• 4 | 3 = 7

Max is 7 — That’s our answer.

Complexity Analysis:

• For each test case, we do a single pass through the array: O(n)
• Total operations across all test cases: O(10⁴) (within limits)

t = int(input())
for _ in range(t):
    n, z =  map(int, input().split())
    a = list(map(int, input().split()))
    max_value = 0
    for ai in a:
        max_value = max(max_value, ai | z)
    print(max_value)

Try calculating $$$f(l,r)$$$ bit by bit

Which condition has to hold true for all elements on a subsegment $$$[l,r]$$$, and for a certain bit, for that bit to be present in $$$f(l,r)$$$?

How can we check if that condition is true for a certain bit fast?

Try prefix sums.

Try binary search.

1. Calculating Prefix Sums of Bits:
   • We start by counting how many times each bit appears in the array up to a certain point. For example, how many 1s or 0s are there in the first few elements of the array.
   • We do this efficiently in $$$O(n \log(\text{max}(a)))$$$ time. Here, '$$$n$$$' is the length of the array, and '$$$\text{max}(a)$$$' is the maximum value in the array.
2. Understanding Bit Presence in a Range:
   • If the count of a particular bit (like the $$$j$$$-th bit) from index $$$l$$$ to index $$$r$$$ in the array is exactly the same as the length of that range $$$(r - l + 1)$$$, it means that bit appears in all the elements within that range.
3. Calculating $$$f(l,r)$$$:
   • Now, we want to find out for which bits this condition holds true within a certain range $$$[l, r]$$$ of the array.
   • We sum up the counts of all the bits where this condition holds true. This gives us the value of $$$f(l,r)$$$.
4. Solving Queries Efficiently:
   • For each query, given $$$l$$$ and $$$k$$$, we want to find the rightmost index $$$r$$$ such that $$$f(l,r)$$$ is greater than or equal to $$$k$$$.
   • We can use binary search to efficiently find $$$r$$$.
   • If $$$f(l,\text{mid})$$$ is greater than or equal to $$$k$$$, we move towards the right to find a larger $$$r$$$.
   • If not, we move towards the left to find a smaller $$$r$$$.
5. Overall Time Complexity:
   • This entire approach takes $$$O(Q \log(N) \log(\text{max}(a)))$$$ time to process all the queries, where $$$Q$$$ is the number of queries, $$$N$$$ is the length of the array, and $$$\text{max}(a)$$$ is the maximum value in the array.
   • For typical values, this works out to about $$$4 \times 10^7$$$ operations, which is pretty efficient.

So, by using this method, we efficiently handle queries about the presence of certain bits in specific ranges of the array.

t = int(input())
for _ in range(t):
    n = int(input()) 
    nums = list(map(int, input().split()))  
    q = int(input()) 

    arr = [0] * 32
    prefix = [arr]  # Initialize prefix array with zeros

    # Calculate prefix sums of bits
    for num in nums:
        arr = prefix[-1].copy()
        for i in range(32):
            # If the i-th bit is set in num, increment the corresponding count in arr
            if num & (1 << i) != 0:
                arr[i] += 1
        prefix.append(arr)

    # Function to find the bitwise AND of all numbers within a range
    def rangeAnd(l, r):
        ans = 0
        for i in range(32):
            bit_count = prefix[r][i] - prefix[l - 1][i] if l > 0 else prefix[r][i]
            if bit_count == (r - l + 1):
                ans |= (1 << i)
        return ans

    # Binary search to find the rightmost index satisfying the condition
    def bin_search(l, k):
        left = l
        right = n
        while left <= right:
            mid = (right + left) // 2
            if rangeAnd(l, mid) >= k:
                left = mid + 1
            else:
                right = mid - 1

        if right < l:
            return -1
        return right

    ans = []
    # Process queries
    for _ in range(q):
        l, k = map(int, input().split())
        ans.append(bin_search(l, k))

 
    print(*ans)

The formula given in this task looks difficult to calculate, so we can rewrite it:

$$$\sum_{i=1}^n \sum_{j=1}^n \sum_{k=1}^n (x_i \, \& \, x_j) \cdot (x_j \, | \, x_k) = \sum_{j=1}^n \sum_{i=1}^n (x_i \, \& \, x_j) \sum_{k=1}^n (x_j \, | \, x_k) = \sum_{j=1}^n \left[ \sum_{i=1}^n (x_i \, \& \, x_j) \right] \cdot \left[ \sum_{k=1}^n (x_j \, | \, x_k) \right]$$$

We fix the element $$$x_j$$$. Now the task is to calculate two sums $$$\sum_i (x_i \, \& \, x_j)$$$ and $$$\sum_k (x_j \, | \, x_k)$$$, and multiply them by each other.

Let's define function $$$f(x, c)$$$ as the value of $$$c$$$-th bit in $$$x$$$. For example $$$f(13, 1) = 0$$$, because $$$13 = 11\underline{0}1_2$$$, and $$$f(12, 2) = 1$$$, because $$$12 = 1\underline{1}00_2$$$. Additionally, define $$$M$$$ as the smallest integer such that $$$\forall_i \, x_i \lt 2^M$$$. Note that in this task $$$M \leq 60$$$.

We can rewrite our sums using function $$$f$$$:

$$$\sum_i (x_i \, \& \, x_j) = \sum_{c = 0}^{M} 2^c \sum_i f(x_i, c) \cdot f(x_j, c) = \sum_{c = 0}^{M} 2^c f(x_j, c) \sum_i f(x_i, c)$$$

$$$\sum_k (x_j \, | \, x_k) = \sum_{c = 0}^{M} 2^c \sum_k 1 - (1 - f(x_j, c)) \cdot (1 - f(x_k, c)) = \sum_{c = 0}^{M} 2^c \left[ n - (1 - f(x_j, c)) \sum_k (1 - f(x_k, c)) \right]$$$

In other words, we just split elements $$$x_i$$$, $$$x_j$$$, $$$x_k$$$ into the powers of two.

If we memorize the values of $$$\sum_i f(x_i, c)$$$, for each $$$c \in {0, 1, \ldots, M }$$$, then we can calculate the desired sums in $$$\mathcal{O}(M)$$$ for fixed $$$x_j$$$ using the above equations.

So the final solution is to iterate over all elements in the array and fix them as $$$x_j$$$, and sum all of the results obtained. Complexity is $$$\mathcal{O}(nM) = \mathcal{O}(n \log \max_i(x_i))$$$

from sys import stdin


def input(): return stdin.readline().strip()

T = int(input())

for _ in range(T):
    N = int(input())
    x = list(map(int, input().split()))

    MOD = 1000_000_007
    bit_counts = [0]*60
    for xi in x:
        for i in range(60):
            if xi&(1<<i):
                bit_counts[i] += 1
    ans = 0
    for xi in x:
        tot_or = tot_and = 0
        for i in range(60):
            if xi&(1<<i):
                tot_or += (1<<i)%MOD*N
                tot_or %= MOD
                tot_and += (1<<i)%MOD*bit_counts[i]
                tot_and %= MOD
            else:
                tot_or += (1<<i)%MOD*bit_counts[i]
                tot_or %= MOD
        ans += tot_or*tot_and
        ans %= MOD

    print(ans)