Reach-Top OJ

问题 6605 --龙哥的好序列

6605: 龙哥的好序列★★

时间限制: 1 Sec 内存限制: 128 MB
提交: 15 解决: 11
[提交][状态][命题人:]

题目描述

一个序列是好的定义如下：

该序列中存在一数字，使得该序列中除该数字以外的所有数的和等于该数字。

如序列 [1,6,3,2]是好序列，因为1+3+2=6；[0]也是好序列；而[1,2,3,4]与[1]则不是好序列。
现在请你帮忙计算一下，在一个长度为n的序列a，存在多少个非空前缀序列是好的。

输入

第一行包含一个整数T（1≤T≤10000），表示测试数据组数。
每组测试样例的第一行为整数n(1≤n≤200000)，表示序列的长度。
第二行包含有n个整数 a1,a2,…,an (0≤ai≤1e9)，表示序列中的每个元素。
测试样例保证所有n之和不超过200000。

输出

每组测试样例输出一个整数，表示好的非空前缀序列的数量。

样例输入

Copy

7
1
0
1
1
4
1 1 2 0
5
0 1 2 1 4
7
1 1 0 3 5 2 12
7
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296
10
0 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592

样例输出

Copy

提示

在第4组测试样例中，非空前缀序列如下：
前缀序列[0]是好的。
前缀序列[0,1]不是好的，因为0≠1;
前缀序列[0,1,2]不是好的，因为0≠1+2,1≠0+2，2≠0+1；
前缀序列[0,1,2,1]是好的，因为2=0+1+1;
前缀序列[0,1,2,1,4]是好的，因为4=0+1+2+1。

来源

[提交][状态]