[R4E]区间异或和 - 代码源竞赛平台

时空限制

1S/512M

题目描述

给定一个长度为 $n$ 的整数数组 $A$，定义区间 $[l,r]$ 的异或和 $XORsum(l,r)=A_l\oplus A_{l+1}\oplus\dots\oplus A_r$。这里的 $\oplus$ 表示按位异或运算。

求 $\sum_{i=1}^n\sum_{j=i}^n XORsum(i,j)$。

格式

输入格式

第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $A_i$。

输出格式

输出一个整数表示 $\sum_{i=1}^n\sum_{j=i}^n XORsum(i,j)$。

样例

样例输入 #1

3
1 3 5

样例输出 #1

24

样例解释 #1

$XORsum(1,1)=1$；

$XORsum(1,2)=1\oplus3=2$；

$XORsum(1,3)=1\oplus3\oplus5=7$；

$XORsum(2,2)=3$

$XORsum(2,3)=3\oplus5=6$；

$XORsum(3,3)=5$；

$\sum_{i=1}^3\sum_{j=i}^3 XORsum(i,j)=1+2+7+3+6+5=24$。

数据规模

对于 $20\%$ 的数据， $n\leq 100$。

对于 $60\%$ 的数据， $n\leq 5000$。

对于 $100\%$ 的数据， $1\leq n\leq10^5$， $1\leq A_i\leq10^9$。