← 返回题目列表

Codeforces · 1352/E

E. 特殊元素

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

注意这个问题中的非标准内存限制。

为了在这个问题中切断高效解和低效解,时间限制相当严格。更喜欢使用编译的静态类型语言(例如 C++)。如果您使用 Python,请在 PyPy 上提交解决方案。尝试编写一个有效的解决方案。

给出数组$$$a=[a_1, a_2, \ldots, a_n]$$$ ($$$1 \le a_i \le n$$$)。如果存在一对索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l < r \le n$$$) 使得 $$$a_i = a_l + a_{l+1} + \ldots + a_r$$$,则其元素 $$$a_i$$$ 被称为特殊元素。换句话说,如果一个元素可以表示为数组中两个或多个连续元素的总和(无论它们是否特殊),则该元素被称为特殊元素。

打印给定数组 $$$a$$$ 的特殊元素的数量。

例如,如果 $$$n=9$$$ 且 $$$a=[3,1,4,1,5,9,2,6,5]$$$,则答案为 $$$5$$$:

- $$$a_3=4$$$ 是一个特殊元素,因为 $$$a_3=4=a_1+a_2=3+1$$$;
- $$$a_5=5$$$ 是一个特殊元素,因为 $$$a_5=5=a_2+a_3=1+4$$$;
- $$$a_6=9$$$ 是一个特殊元素,因为 $$$a_6=9=a_1+a_2+a_3+a_4=3+1+4+1$$$;
- $$$a_8=6$$$ 是一个特殊元素,因为 $$$a_8=6=a_2+a_3+a_4=1+4+1$$$;
- $$$a_9=5$$$ 是一个特殊元素,因为 $$$a_9=5=a_2+a_3=1+4$$$。

请注意,数组 $$$a$$$ 的某些元素可能相等 - 如果多个元素相等且特殊,则所有这些元素都应计入答案中。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以两行给出。第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 8000$$$) — 数组 $$$a$$$ 的长度。第二行包含整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$)。

保证输入中所有测试用例的 $$$n$$$ 值的总和不超过 $$$8000$$$。

输出

打印 $$$t$$$ 数字 — 每个给定数组的特殊元素的数量。

示例

输入 #1

5
9
3 1 4 1 5 9 2 6 5
3
1 1 2
5
1 1 1 1 1
8
8 7 6 5 4 3 2 1
1
1

输出 #1

5
1
0
4
0