← 返回题目列表

Codeforces · 1438/E

E. 尤里无所不能

中文机器翻译题面 查看原题

尤里确信他可以做任何事情。但他能完成这个任务吗?

他有一个由 $$$n$$$ 正整数组成的数组 $$$a$$$。如果同时满足以下条件,我们称子数组 $$$a[l...r]$$$ 为好:

- $$$l+1 \leq r-1$$$,i。 e.子数组的长度至少为 $$$3$$$;
- $$$(a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1})$$$,其中 $$$\oplus$$$ 表示按位异或运算。

换句话说,如果两个边界元素的按位异或等于其余元素的总和,则子数组是好的。

Yurii 想要计算好子数组的总数。它等于什么?

数组 $$$c$$$ 是数组 $$$d$$$ 的子数组,如果 $$$c$$$ 可以通过删除开头的几个(可能是零个或全部)元素和末尾的几个(可能是零个或全部)元素从 $$$d$$$ 获得。

输入

第一行包含一个整数 $$$n$$$ ($$$3 \leq n \leq 2\cdot 10^5$$$) — $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \lt 2^{30}$$$) — $$$a$$$ 的元素。

输出

输出一个整数——好的子数组的数量。

示例

输入 #1

8
3 1 2 3 1 2 3 15

输出 #1

6

输入 #2

10
997230370 58052053 240970544 715275815 250707702 156801523 44100666 64791577 43523002 480196854

输出 #2

2

注意

示例中有 $$$6$$$ 好的子数组:

- $$$[3,1,2]$$$(两次)因为$$$(3 \oplus 2) = 1$$$;
- $$$[1,2,3]$$$(两次)因为$$$(1 \oplus 3) = 2$$$;
- $$$[2,3,1]$$$ 因为 $$$(2 \oplus 1) = 3$$$;
- $$$[3,1,2,3,1,2,3,15]$$$ 因为 $$$(3 \oplus 15) = (1+2+3+1+2+3)$$$。