题目描述

Alex 认为一个数组是好的，如果存在某个元素可以表示为所有其他元素的和（如果没有其他元素，则其他元素的和为 $0$）。例如，数组 $[1,6,3,2]$ 是好的，因为 $1+3+2=6$。此外，数组 $[0]$ 也是好的。然而，数组 $[1,2,3,4]$ 和 $[1]$ 不是好的。

Alex 有一个数组 $a_1,a_2,\ldots,a_n$。请你帮助他统计数组 $a$ 的有多少个非空前缀是好的。换句话说，统计有多少个整数 $i$（$1 \le i \le n$），使得长度为 $i$ 的前缀（即 $a_1,a_2,\ldots,a_i$）是好的。

输入格式

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示数组的元素个数。

每个测试用例的第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 10^9$），表示数组的元素。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示数组 $a$ 的好的非空前缀的数量。

样例

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

1
0
3
3
4
1
2

样例说明

在第四个测试用例中，数组有五个前缀：

• 前缀 $[0]$ 是好的数组，如题目所述；
• 前缀 $[0, 1]$ 不是好的数组，因为 $0 \ne 1$；
• 前缀 $[0, 1, 2]$ 不是好的数组，因为 $0 \ne 1 + 2$，$1 \ne 0 + 2$，$2 \ne 0 + 1$；
• 前缀 $[0, 1, 2, 1]$ 是好的数组，因为 $2 = 0 + 1 + 1$；
• 前缀 $[0, 1, 2, 1, 4]$ 是好的数组，因为 $4 = 0 + 1 + 2 + 1$。

如你所见，其中有三个前缀是好的，所以答案是 $3$。

由 ChatGPT 4.1 翻译

来源

Codeforces 1985C，英文题名 Good Prefixes。