Sum of XOR Functions - Titan Online Assessment

Problem Preview

"Level : Codeforces Div-2 D You are given an array `a` containing `n` non-negative integers. For every subarray `[l, r]`, define its XOR value as: `f(l, r) = a_l ⊕ a_{l+1} ⊕ ... ⊕ a_r` where `⊕` represents the bitwise XOR operation. Your task is to compute the following weighted sum over **all possible subarrays**: `Σ(l=1 to n) Σ(r=l to n) f(l, r) × (r - l + 1)` In other words, the XOR of each subarray is multiplied by the length of that subarray, and all such values are added together. Since the resulting value can be extremely large, output the answer modulo `998244353`. ## Input The first line contains a single integer `n` — the size of the array. The second line contains `n` integers: `a_1, a_2, ..., a_n` representing the elements of the array. ### Constraints * `1 ≤ n ≤ 3 × 10^5` * `0 ≤ a_i ≤ 10^9` ## Output Print a single integer — the required weighted sum of XOR values over all subarrays, taken modulo `998244353`. ## Examples ### Example 1 **Input** ```text 3 1 3 2 ``` **Output** ```text 12 ``` ### Example 2 **Input** ```text 4 39 68 31 80 ``` **Output** ```text 1337 ``` ### Example 3 **Input** ```text 7 313539461 779847196 221612534 488613315 633203958 394620685 761188160 ``` **Output** ```text 257421502 ``` ## Explanation For the first example, consider every subarray and multiply its XOR value by its length: * `[1]` → XOR = `1`, contribution = `1 × 1` * `[1, 3]` → XOR = `2`, contribution = `2 × 2` * `[1, 3, 2]` → XOR = `0`, contribution = `0 × 3` * `[3]` → XOR = `3`, contribution = `3 × 1` * `[3, 2]` → XOR = `1`, contribution = `1 × 2` * `[2]` → XOR = `2`, contribution = `2 × 1` Their total is: `1 + 4 + 0 + 3 + 2 + 2 = 12` Hence, the answer is `12`."