307939: CF1438E. Yurii Can Do Everything

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Yurii Can Do Everything

题意翻译

给定一个序列 $a$ ,我们称他的一个子串 $a[l...r]$ 是“好的”,当且仅当其满足以下两个条件: - 这个串的长度 $\geq 3$ 。 - $a_l\oplus a_r=\sum_{i=l+1}^{r-1} a_i$ 求这个序列的“好的”子串有多少个。 ------------ ### 样例解释 样例一中,有以下几个串是“好的”: $2$ 个 $[3,1,2]$ ,因为 $3\oplus 2=1$ ; $2$ 个 $[1,2,3]$ ,因为 $1\oplus 3=2$ ; $1$ 个 $[2,3,1]$ ,因为 $2\oplus 1=3$ ; $1$ 个 $[3,1,2,3,1,2,3,15]$ ,因为 $3\oplus 15=(1+2+3+1+2+3)$ ; 共 $6$ 个。 ------------ ### 数据范围 $3\leq n\leq 2\cdot 10^5$ , $1\leq a_i <2^{30}$

题目描述

Yurii is sure he can do everything. Can he solve this task, though? He has an array $ a $ consisting of $ n $ positive integers. Let's call a subarray $ a[l...r] $ good if the following conditions are simultaneously satisfied: - $ l+1 \leq r-1 $ , i. e. the subarray has length at least $ 3 $ ; - $ (a_l \oplus a_r) = (a_{l+1}+a_{l+2}+\ldots+a_{r-2}+a_{r-1}) $ , where $ \oplus $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR). In other words, a subarray is good if the bitwise XOR of the two border elements is equal to the sum of the rest of the elements. Yurii wants to calculate the total number of good subarrays. What is it equal to? An array $ c $ is a subarray of an array $ d $ if $ c $ can be obtained from $ d $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

输入输出格式

输入格式


The first line contains a single integer $ n $ ( $ 3 \leq n \leq 2\cdot 10^5 $ ) — the length of $ a $ . The second line contains $ n $ integers $ a_1,a_2,\ldots,a_n $ ( $ 1 \leq a_i \lt 2^{30} $ ) — elements of $ a $ .

输出格式


Output a single integer — the number of good subarrays.

输入输出样例

输入样例 #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

说明

There are $ 6 $ good subarrays in the example: - $ [3,1,2] $ (twice) because $ (3 \oplus 2) = 1 $ ; - $ [1,2,3] $ (twice) because $ (1 \oplus 3) = 2 $ ; - $ [2,3,1] $ because $ (2 \oplus 1) = 3 $ ; - $ [3,1,2,3,1,2,3,15] $ because $ (3 \oplus 15) = (1+2+3+1+2+3) $ .

Input

题意翻译

给定一个序列 $a$ ,我们称他的一个子串 $a[l...r]$ 是“好的”,当且仅当其满足以下两个条件: - 这个串的长度 $\geq 3$ 。 - $a_l\oplus a_r=\sum_{i=l+1}^{r-1} a_i$ 求这个序列的“好的”子串有多少个。 ------------ ### 样例解释 样例一中,有以下几个串是“好的”: $2$ 个 $[3,1,2]$ ,因为 $3\oplus 2=1$ ; $2$ 个 $[1,2,3]$ ,因为 $1\oplus 3=2$ ; $1$ 个 $[2,3,1]$ ,因为 $2\oplus 1=3$ ; $1$ 个 $[3,1,2,3,1,2,3,15]$ ,因为 $3\oplus 15=(1+2+3+1+2+3)$ ; 共 $6$ 个。 ------------ ### 数据范围 $3\leq n\leq 2\cdot 10^5$ , $1\leq a_i <2^{30}$

加入题单

上一题 下一题 算法标签: