1864E - Guess Game - CodeForces Solution

'''
CF 1864E
For each a, consider prefix of a's bits matching
prefix of b's bits and then having a difference in bit.
'''

class Node:
    def __init__(self):
        self.L = None
        self.R = None
        self.subtree_cnts = 0

def main():
    
    mod = 998244353

    t = int(input())
    allans = []
    for _ in range(t):
        n = int(input())
        s = readIntArr()

        trie_address = [-1, -1]          subtree_cnts = [0, 0]
        for v in s:
            u = 0
            for i in range(29, -1, -1):
                if (v & (1 << i)) == 0:
                    if trie_address[u] == -1:
                        trie_address.extend([-1, -1])
                        trie_address[u] = len(trie_address) - 2
                        subtree_cnts.extend([0, 0])
                    u = trie_address[u]
                else:
                    if trie_address[u + 1] == -1:
                        trie_address.extend([-1, -1])
                        trie_address[u + 1] = len(trie_address) - 2
                        subtree_cnts.extend([0, 0])
                    u = trie_address[u + 1]
                subtree_cnts[u] += 1
        
        ans = 0
        for v in s:
            a_turn = True
            n_turns = 1
            u = 0
            for i in range(29, -1, -1):
                if (v & (1 << i)) == 0:
                    if trie_address[u + 1] != -1:                          if a_turn:
                            ans += (n_turns * subtree_cnts[trie_address[u + 1]]) % mod
                            ans %= mod
                        else:
                            ans += ((n_turns + 1) * subtree_cnts[trie_address[u + 1]]) % mod
                            ans %= mod
                    u = trie_address[u]
                else:
                    if trie_address[u] != -1:                          if a_turn:
                            ans += ((n_turns + 1) * subtree_cnts[trie_address[u]]) % mod
                            ans %= mod
                        else:
                            ans += (n_turns * subtree_cnts[trie_address[u]]) % mod
                            ans %= mod
                    a_turn = not a_turn
                    n_turns += 1
                    u = trie_address[u + 1]
                                    ans += (n_turns * subtree_cnts[u]) % mod
            ans %= mod
        denominator = (n * n) % mod
        ans = (ans * pow(denominator, mod - 2, mod)) % mod
        allans.append(ans)
    multiLineArrayPrint(allans)

    return

import sys
input=sys.stdin.buffer.readline  
def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr):     dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(a, b):
    print('? {} {}'.format(a, b))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
 
inf=float('inf')
 
from math import gcd,floor,ceil
import math
 
for _abc in range(1):
    main()