time limit per test
2 seconds
memory limit per test
256 megabytes
You are given an array a1,a2,…,ana1,a2,…,an consisting of integers from 00 to 99. A subarray al,al+1,al+2,…,ar−1,aral,al+1,al+2,…,ar−1,ar is good if the sum of elements of this subarray is equal to the length of this subarray (∑i=lrai=r−l+1∑i=lrai=r−l+1).
For example, if a=[1,2,0]a=[1,2,0], then there are 33 good subarrays: a1…1=[1],a2…3=[2,0]a1…1=[1],a2…3=[2,0] and a1…3=[1,2,0]a1…3=[1,2,0].
Calculate the number of good subarrays of the array aa.
Input
The first line contains one integer tt (1≤t≤10001≤t≤1000) — the number of test cases.
The first line of each test case contains one integer nn (1≤n≤1051≤n≤105) — the length of the array aa.
The second line of each test case contains a string consisting of nn decimal digits, where the ii-th digit is equal to the value of aiai.
It is guaranteed that the sum of nn over all test cases does not exceed 105105.
Output
For each test case print one integer — the number of good subarrays of the array aa.
Example
Input
Copy
3 3 120 5 11011 6 600005
Output
Copy
3 6 1
Note
The first test case is considered in the statement.
In the second test case, there are 66 good subarrays: a1…1a1…1, a2…2a2…2, a1…2a1…2, a4…4a4…4, a5…5a5…5 and a4…5a4…5.
In the third test case there is only one good subarray: a2…6a2…6.
解题说明：此题是一道数列题，确保区间内每个元素的和为区间长度。因为区间和等于前缀和相减即sum[i]−sum[j−1]。所以由题意可以得到：sum[i]−sum[j−1]=i−j+1。移项后得：sum[i]−i=sum[j−1]−j+1。统计 sum[i]−i的个数即可。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string.h>
#include<map>
#include<queue>
#include<vector>
#include<set>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
const ll mm = 1e5 + 60;
ll s[mm], n, ans;
map<ll, ll>mp;int main()
{int t;cin >> t;while (t--){memset(s, 0, sizeof(s));ans = 0;mp.clear();mp[0] = 1;cin >> n;for (int i = 1; i <= n; i++){char c;cin >> c;s[i] = s[i - 1] + c - '0';ans += mp[s[i] - i]++;}cout << ans << endl;}return 0;
}
