Good Subarrays

题意翻译

## 题目描述 有一个数组$a_1,a_2,\dots,a_n$，满足$\forall i \in[1,n]$ 有 $0 \le a_i \le 9$。 我们称一个子数组 $a_l,a_{l+1},a_{l+2},\dots,a_{r-1},a_r$ 是“好”的，当且仅当这个子数组中所有元素的和等于它的长度（即 $\sum_{i=l}^r a_i = r-l+1$ ）。 现在要你计算出数组 $a$ 中所有“好”的子数组的数量。 ## 输入格式 第一行，一个数 $t$ ，表示数据组数。 接下来 $2\times t$ 行，每两行代表一组数据： - 第一行，一个整数 $n$ ，表示 $a$ 数组的长度； - 接下来一行，一个长度为 $n$ 的由数字组成的字符串，其中第 $i$ 个数字的值是 $a_i$ 的值。 ## 输出格式 对于每组数据，输出 $a$ 数组中“好”的子数组的数量。 ## 数据范围与提示 ### 样例解释 第一组数据中， $a_{1\dots1},a_{2\dots3},a_{1\dots3}$ 是原数组的“好”子数组； 第二组数据中， $a_{1\dots1},a_{2\dots2},a_{1\dots2},a_{4\dots4},a_{5\dots5},a_{4\dots5}$ 这$6$个子数组是原数组的“好”子数组； 第三组数据中，只有 $a_{2\dots6}$ 是原数组的“好”子数组。 ### 数据范围 $1\le t\le 1000,1\le n\le 10^5,1\le n\cdot t \le 10^5$

题目描述

You are given an array $ a_1, a_2, \dots , a_n $ consisting of integers from $ 0 $ to $ 9 $ . A subarray $ a_l, a_{l+1}, a_{l+2}, \dots , a_{r-1}, a_r $ is good if the sum of elements of this subarray is equal to the length of this subarray ( $ \sum\limits_{i=l}^{r} a_i = r - l + 1 $ ). For example, if $ a = [1, 2, 0] $ , then there are $ 3 $ good subarrays: $ a_{1 \dots 1} = [1], a_{2 \dots 3} = [2, 0] $ and $ a_{1 \dots 3} = [1, 2, 0] $ . Calculate the number of good subarrays of the array $ a $ .

输入输出格式

输入格式

The first line contains one integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The first line of each test case contains one integer $ n $ ( $ 1 \le n \le 10^5 $ ) — the length of the array $ a $ . The second line of each test case contains a string consisting of $ n $ decimal digits, where the $ i $ -th digit is equal to the value of $ a_i $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

输出格式

For each test case print one integer — the number of good subarrays of the array $ a $ .

输入输出样例

输入样例 #1

3
3
120
5
11011
6
600005

输出样例 #1

3
6
1

说明

The first test case is considered in the statement. In the second test case, there are $ 6 $ good subarrays: $ a_{1 \dots 1} $ , $ a_{2 \dots 2} $ , $ a_{1 \dots 2} $ , $ a_{4 \dots 4} $ , $ a_{5 \dots 5} $ and $ a_{4 \dots 5} $ . In the third test case there is only one good subarray: $ a_{2 \dots 6} $ .