P14522 【MX-S11-T3】空之碎物

[カラノワレモノ - ヒトリエ](https://music.163.com/song?id=26526290) >咲きたいな　笑いたいなあ > >好想綻放啊　好想大笑啊

定义 $\ominus$ 是一种二进制上的位运算，它每一位的运算表如下： |$x$|$y$|$x\ominus y$| |:-:|:-:|:-:| |$0$|$0$|$0$| |$0$|$1$|$0$| |$1$|$0$|$1$| |$1$|$1$|$0$| 这个运算同时是二进制不退位减法。 现在你有一个无序的多重集 $S$。你可以进行若干次操作。若 $S$ 的大小不少于 $2$，则你可以选择 $S$ 中任意两个数，记这两个数是 $x,y$。然后将这两个数合并成 $x\ominus y$ 或 $y\ominus x$。 最后请你将 $S$ 合并至剩下一个数，试求出这个数的最大值。 你有一个长度为 $n$ 的非负整数序列 $a_1, \ldots, a_n$。定义 $f(l,r)$ 表示将序列 $a$ 中 $[l,r]$ 这个区间内的数作为多重集 $S$ 中的元素时上述问题的答案。 试求出 $$ \sum_{i=1}^n \sum_{j=i}^n f(i,j) $$ 对 $998244353$ 取模后的值。

第一行，一个正整数 $n$。 第二行，$n$ 个非负整数 $a_1, \ldots, a_n$。

输出一行一个非负整数，表示答案对 $998244353$ 取模后的值。

**【样例解释 #1】** 考虑 $f(1,3)$ 的计算过程： 多重集 $S=\{1,2,3\}$。 先将 $1$ 和 $2$ 合并成 $1\ominus 2=1$。 再将 $3$ 和 $1$ 合并成 $3\ominus 1=2$。 可以证明，你无法得到 $>2$ 的最终结果。所以 $f(1,3)=2$。 类似的计算得到： $f(1,1)=1$，$f(1,2)=2$，$f(2,2)=2$，$f(2,3)=1$，$f(3,3)=3$。 总和为 $11$。 **【样例 #2】** 见选手目录下的 $\textbf{\textit{heal/heal2.in}}$ 与 $\textbf{\textit{heal/heal2.ans}}$。 该样例满足测试点 $1\sim 5$ 的约束条件。 **【样例 #3】** 见选手目录下的 $\textbf{\textit{heal/heal3.in}}$ 与 $\textbf{\textit{heal/heal3.ans}}$。 该样例满足测试点 $6\sim 8$ 的约束条件。 **【样例 #4】** 见选手目录下的 $\textbf{\textit{heal/heal4.in}}$ 与 $\textbf{\textit{heal/heal4.ans}}$。 该样例满足测试点 $9\sim 11$ 的约束条件。 **【样例 #5】** 见选手目录下的 $\textbf{\textit{heal/heal5.in}}$ 与 $\textbf{\textit{heal/heal5.ans}}$。 该样例满足测试点 $14\sim 18$ 的约束条件。 **【样例 #6】** 见选手目录下的 $\textbf{\textit{heal/heal6.in}}$ 与 $\textbf{\textit{heal/heal6.ans}}$。 该样例满足测试点 $19$ 的约束条件。 **【样例 #7】** 见选手目录下的 $\textbf{\textit{heal/heal7.in}}$ 与 $\textbf{\textit{heal/heal7.ans}}$。 该样例满足测试点 $23\sim 25$ 的约束条件。 **【数据范围】** 本题共 $25$ 个测试点，每个 $4$ 分。 对于所有测试数据，保证： - $1\le n\le 2\times 10^5$； - $0\le a_i < 2^{25}$。 ::cute-table{tuack} | 测试点编号 | $n\le$ | 特殊性质 | |:-:| :-: | :-: | | $1\sim 5$ | $4$ | B | | $6\sim 8$ | $10^3$ | AB | | $9\sim 11$ | ^ | B | | $12, 13$ | $2\times 10^4$ | AB | | $14\sim 18$ | ^ | 无 | | $19$ | $10^5$ | AB | | $20\sim 22$ | ^ | 无 | | $23\sim 25$ | $2\times 10^5$ | ^ | 特殊性质 A：对于所有 $1 \le i \le n$ 均存在非负整数 $k$ 使得 $a_i=2^k$。 特殊性质 B：保证 $a$ 序列中的每个元素都从所有满足条件的元素中等概率随机选取。