CF1352E Special Elements

请注意本题的非标准内存限制。 为了区分高效解法与低效解法，本题的时间限制较为严格。建议使用编译型静态类型语言（如 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$ 个整数。 保证所有测试用例中 $n$ 的总和不超过 $8000$。

输出 $t$ 个整数，每个整数表示对应数组中特殊元素的个数。

由 ChatGPT 4.1 翻译