Sum of XOR Functions
Contest: Educational Codeforces Round 155 (Rated for Div. 2)
Difficulty rating: 1700
Tags: bitmasks, combinatorics, divide and conquer, dp, math

You are given an array $$$a$$$ of length $$$n$$$ consisting of non-negative integers.

You have to calculate the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, where $$$f(l, r)$$$ is $$$a_l \oplus a_{l+1} \oplus \dots \oplus a_{r-1} \oplus a_r$$$ (the character $$$\oplus$$$ denotes bitwise XOR).

Since the answer can be very large, print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the array $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9)$$$.

Output format:
Print the one integer — the value of $$$\sum_{l=1}^{n} \sum_{r=l}^{n} f(l, r) \cdot (r - l + 1)$$$, taken modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the answer is equal to $$$f(1, 1) + 2 \cdot f(1, 2) + 3 \cdot f(1, 3) + f(2, 2) + 2 \cdot f(2, 3) + f(3, 3) = $$$ $$$= 1 + 2 \cdot 2 + 3 \cdot 0 + 3 + 2 \cdot 1 + 2 = 12$$$.

Example input:
3
1 3 2

Example output:
12

Example input:
4
39 68 31 80

Example output:
1337

Editorial:
Let's solve this problem for each bit separately.
When we fix a bit (let's denote it as $$$b$$$), all we have to do is solve the original problem for a binary string (let's denote this string as $$$s$$$). Note that if there is an odd number of $$$1$$$'s on a segment, the value of XOR on the segment is $$$1$$$, otherwise it's $$$0$$$. So, for a fixed bit $$$b$$$, we have to calculate $$$\sum_{l=1}^{n} \sum_{r=l}^{n} g(l, r) \cdot (r - l + 1)$$$, where $$$g(l, r) = 1$$$ if the number of character 1 in substring $$$s_l, s_{l + 1}, \dots, s_r$$$ is odd, otherwise $$$g(l, r) = 0$$$.
Now let's figure out how to solve this problem if the right border of substrings is fixed (let's denote it as $$$r$$$). Let's denote a function (which we call $$$pref(x)$$$) that is equal to the number of $$$1$$$'s on the prefix of length $$$x$$$ modulo $$$2$$$. So, if there is an even number of $$$1$$$'s among the first $$$x$$$ characters, then $$$pref(x) = 0$$$, otherwise $$$pref(x) = 1$$$.
If we fix the right border of a substring $$$r$$$ is fixed, we need to consider such left borders $$$l$$$ that $$$l < r$$$ and $$$pref(l) + pref(r) = 1$$$. We have to maintain the number of such left borders (let it be $$$cnt_i$$$ for borders which have $$$pref(l) = i$$$) and their total sum (let it be $$$sumOfL_i$$$ for borders which have $$$pref(l) = i$$$). These values can be easily maintained as we iterate on $$$r$$$.
Why do we need these values? We can calculate the value of $$$\sum_{l=1}^{r} g(l, r) \cdot (r - l + 1)$$$ for a fixed right border $$$r$$$, if we denote the length of the segment $$$(r - l + 1)$$$ as the difference between the right border and the left border (we can discard $$$1$$$ from this formula if we treat $$$l$$$ as an inclusive border, and $$$r$$$ as an exclusive border). So, $$$\sum_{l=1}^{r} g(l, r) \cdot (r - l + 1)$$$ can be rephrased as the difference between the sum of right borders of those segments (which is equal to $$$r$$$ multiplied by the number of different left borders) and the sum of left borders of these segments (which is maintained in $$$sumOfL$$$).
Now we just need to iterate on the right border and sum this up while maintaining the values of $$$cnt_i$$$ and $$$sumOfL_i$$$. Don't forget that we solved the problem only for the bit $$$b$$$, we need to combine the results for every bit later (and make sure that we multiply the result for the $$$b$$$-th bit by $$$2^b$$$).
Overall complexity is $$$O(n \log A)$$$, where $$$A$$$ is the constraint on the values in the array.