CF2268E Kia Kio and Tree of Life

After unlocking the crystal terminal, Kia and Kio discovered the blueprint for the kingdom's forgotten heart: a digital Tree of Life, seeded by the array $ a_1, a_2, \ldots, a_n $ . To restore its pulse, they had to weave every possible incarnation of the Tree together. For any continuous segment, Kia would gently select an index $ i $ to plant the root. Trusting her vision, Kio would carefully weave the branches of life — crafting the left subtree from the preceding segment $ [1, i-1] $ and the right subtree from the succeeding segment $ [i+1, n] $ . Once a Tree of Life bloomed, its vital resonance, $ f(\text{tree}) $ , was defined by its bonds. If one were to sever any of the $ n-1 $ delicate branches, the Tree would split into two disconnected halves, releasing an energy of $ X+Y $ , where $ X $ and $ Y $ are the bitwise XOR sums of the array elements remaining in the first and second halves, respectively. The total power of the Tree, $ f(\text{tree}) $ , is the sum of these released energies across all $ n-1 $ branches. Kia wanted to know the ultimate vital force they could awaken. Help them compute the total sum of $ f(\text{tree}) $ across every valid Tree of Life born from their shared bond, modulo $ 998\,244\,353 $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 2\cdot10^5 $ ) — the size of the array. The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 0 \le a_i \lt 2^{18} $ ). It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot10^5 $ .

For each test case, print a single integer — the total sum of $ f(\text{tree}) $ across all valid Trees of Life, modulo $ 998\,244\,353 $ .

For the first test case, $ n=2 $ and $ a = [1,2] $ . There are two valid trees that can be constructed: one with $ a_1 $ as the root and $ a_2 $ as the right child, and one with $ a_2 $ as the root and $ a_1 $ as the left child. In both trees, severing the single branch leaves two components with XOR sums $ X=1 $ and $ Y=2 $ . Thus, the value for each tree becomes $ 1 + 2 = 3 $ . The total energy accumulated across both Trees of Life is $ 3+3=6 $ . For the second test case, $ n=3 $ and $ a = [1,1,1] $ . There are $ 5 $ valid trees that can be constructed: - Root is $ 1 $ : $ \{(1,2), (2,3)\} $ , $ \{(1, 3), (2, 3)\} $ ; - Root is $ 2 $ : $ \{(1,2), (2,3)\} $ ; - Root is $ 3 $ : $ \{(1,3), (1,2)\} $ , $ \{(2, 3), (1, 2)\} $ . All trees are just a path with three vertices, and severing a single branch leaves two components with XOR sums $ X=1 $ and $ Y=0 $ . So the value for each tree becomes $ 2 $ . The total energy accumulated across all five Trees of Life is $ 5\cdot 2=10 $ .