Problem6035--好糖

6035: 好糖

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

给你 $n$ 颗糖,每颗糖有一个甜度。
一颗糖是好糖当且仅当,去掉这颗糖之后剩下的糖如果从前到后每天吃一个的话,奇数天吃的糖的甜度和与偶数天吃的糖的甜度和相等。
问这 $n$ 颗糖中有多少颗好糖。

Input

第一行一个正整数 $n\ (1 \leq n \leq 200,000)$。
第二行 $n$ 个数表示从前到后每颗糖的甜度 $a_i\ (0 \leq a_i \leq 10,000)$。

Output

一个数表示好糖个数。

Constraints

$50\%$ 的数据,$n \leq 10,000$;
$100\%$ 的数据,$n \leq 200,000$。

Sample 1 Input

7
5 5 4 5 5 5 6

Sample 1 Output

2
去掉第 $1$ 颗糖。糖变为 $5\ 4\ 5\ 5\ 5\ 6$,偶数的糖为$4\ 5\ 6$,甜度总和为 $4+5+6=15$;奇数的糖为 $5\ 5\ 5$,甜度总和为 $5+5+5=15$。
去掉第 $2$ 颗糖。糖变为 $5\ 4\ 5\ 5\ 5\ 6$,偶数的糖为$4\ 5\ 6$,甜度总和为 $4+5+6=15$;奇数的糖为 $5\ 5\ 5$,甜度总和为 $5+5+5=15$。
因此答案为 $2$。

Sample 2 Input

9
2 3 4 2 2 3 2 2 4

Sample 2 Output

3
去掉第 $4$ 颗糖。糖变为 $2\ 3\ 4\  2\ 3\ 2\ 2\ 4$,偶数的糖为$3\ 2\ 2\ 4$,甜度总和为 $3+2+2+4=11$;奇数的糖为 $2\ 4\ 3\ 2$,甜度总和为 $2+4+3+2=11$。
去掉第 $5$ 颗糖。糖变为 $2\ 3\ 4\  2\ 3\ 2\ 2\ 4$,偶数的糖为$3\ 2\ 2\ 4$,甜度总和为 $3+2+2+4=11$;奇数的糖为 $2\ 4\ 3\ 2$,甜度总和为 $2+4+3+2=11$。
去掉第 $9$ 颗糖。糖变为 $2\ 3\ 4\  2\ 2\ 3\ 2\ 2$,偶数的糖为$3\ 2\ 3\ 2$,甜度总和为 $3+2+3+2=10$;奇数的糖为 $2\ 4\ 2\ 2$,甜度总和为 $2+4+2+2=10$。
因此答案为 $3$。

HINT

题目来源:51Nod 2541

Source/Category

基础算法 4.2.前缀和