Codeforces Round 952 (Div. 4) |
---|
Закончено |
Алекс считает, что некоторый массив является хорошим, если существует элемент, который является суммой всех других элементов (сумма всех других элементов равна $$$0$$$, если других элементов нет). Например, массив $$$[1,6,3,2]$$$ является хорошим, так как $$$1+3+2=6$$$. Кроме того, массив $$$[0]$$$ также является хорошим. Однако массивы $$$[1,2,3,4]$$$ и $$$[1]$$$ не являются хорошими.
У Алекса есть массив $$$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$$$.
7101141 1 2 050 1 2 1 471 1 0 3 5 2 1271000000000 1000000000 1000000000 1000000000 1000000000 1000000000 294967296100 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 589934592
1 0 3 3 4 1 2
В четвертом примере массив имеет пять префиксов:
Как видно, три из них являются хорошими, поэтому ответ равен $$$3$$$.
Название |
---|