UOJ Logo Universal Online Judge

UOJ

#213. 【UNR #1】争夺圣杯

统计

小C与 Saber 签订契约之后达成了共同争夺圣杯的目标,然而他们赢得圣杯的道路并没有这么轻易,小C需要与其他的英灵进行决战。

小C通过一些交易得知,其他的英灵已经结盟了。大决战那天,其他的英灵站成了一排,从左到右依次编号为 $1$ 到 $n$,血量依次为 $\mathrm{HP}_1, \dots, \mathrm{HP}_n$。

小C还知道,这些英灵暗自商量了一个整数 $m$ ($1 \leq m \leq n$)。Saber 和这些英灵之间的战斗将会持续 $n - m + 1$ 轮,其中第 $i$ 轮 Saber 将与编号为 $i, i + 1, \dots, i + m - 1$ 的英灵进行战斗,所需要耗费的魔力值为这些战斗的英灵中的血量的最大值。而由于人多力量大等因素,每轮战斗后英灵的血量不会有任何变化。

所有战斗结束后,Saber 耗费的总魔力值为每轮战斗耗费的魔力值之和。

小C和 Saber 必须挺过这 $n - m + 1$ 轮,之后这些英灵将一而再,再而三,三而竭,闻风丧胆,望风而逃,三十六计走为上。小C很焦虑,于是就来向您求救。小C想要知道所有可能的 $m = 1, 2, \dots, n$ 中,Saber 需要耗费的总魔力值分别是多少。

为了避免一些奇怪的原因,你只要输出所有情况的总魔力值模 $998244353$($7 \times 17 \times 2^{23} + 1$,一个质数)后,逐个按位异或起来的结果。(异或即 C/C++ 中的 ^,Pascal 中的 xor

输入格式

第一行一个正整数 $n$。

第二行包含了 $n$ 个整数 $\mathrm{HP}_1, \dots, \mathrm{HP}_n$,表示这 $n$ 个英灵的血量。

注意:由于本题目的输入可能很大,请选择较为快速的读入方式。

输出格式

输出一行,一个整数,表示所有情况的总魔力值取模后逐个按位异或起来的结果。

样例一

input

6
19 4 20 19 1 10

output

94

explanation

$m= 1, 2, 3, 4, 5, 6$ 时候的对应的每个值分别是 $73,88,79,60,40,20$。

答案是 $73 \mathbin{\mathrm{xor}} 88 \mathbin{\mathrm{xor}} 79 \mathbin{\mathrm{xor}} 60 \mathbin{\mathrm{xor}} 40 \mathbin{\mathrm{xor}} 20= 94$。

样例二

input

6
5 19 7 10 16 7

output

85

样例三

见样例数据下载,限制与约定跟第 $5$ 个测试点相同。

样例四

见样例数据下载,限制与约定跟第 $8$ 个测试点相同。

限制与约定

测试点编号$n$约定
1$\leq 10^2$
2$\leq 10^3$
3
4$\leq 10^5$$\mathrm{HP}_i$ 在 $[0,10^9]$ 均匀随机
5$\leq 2 \times 10^5$
6$\leq 5 \times 10^5$
7$\leq 10^5$
8$\leq 2 \times 10^5$
9$\leq 5 \times 10^5$
10$\leq 10^6$

对于所有数据,$0 \leq \mathrm{HP}_i \leq 10^9$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载