前缀免费获得桃子问题

n 个人在摘桃子, n 个人从左到右每个人拥有的桃子数是 ai， 有一个免费获得桃子的规则，如果连续 x 个人的桃子总数除以 k 的余数正好是 x, 那么这 x 个人就可以免费获得桃子，算出一共有多少种不同的方案可以使有人免费获得桃子
所有数据保证 1≤n≤2×105,1≤k≤109,1≤ai≤109

数据范围很大，双重for循环应该是过不了全部，一重for循环又该怎么解决 x个数和%k==x 呢

这题就是说，给你一个数组，每个数组代表一个数，如果连续的x个数加起来等于x，这个子数组就是好的，问你有多少个这样的子数组。
通过这题我们可以知道，好数组的判断标准是：r∑i=l a[i] == r-l+1。我们可以将此等式变为r∑i=l (a[i]-1) == 0，（因为r-l+1等于数组长度，而左边是数组的数相加，左边减去右边就相当于数组中每个数都-1了）此时问题就变成了，看有多少个子数组的区间合为0。我们计算前缀和，这样可以快速的得到两个端点间区间和，我们用哈希表记录每个相同前缀和值的数量，如果有n个相同的前缀和，那么就一共有1+2+3+……+n-1个好数组，因为如果两个端点的前缀和相同，说明它们中间这一段的区间和为0。要注意的是，如果前缀和为0的数量有n个，啧是由1+2+3+……+n-1+n个好数组，因为前缀和为0不光是两个端点间区间和为0，它自身的前缀和也是0，也是满足条件的。记录下所有的结果并输出即可。

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<unordered_map>
#include<stack>
 
typedef long long ll;
typedef pair<ll, ll>PII;
const int N = 200010;
ll f[N], s[N], e[N];
 
 
int main()
{
    int n;
    cin >> n;
    while (n--)
    {
        map<int, int>mymap;
        ll m, res = 0,sum=0;
        string str;
        cin >> m;
        cin >> str;
        vector<int>v(m + 1), s(m + 1);
        for (int i = 1; i <= m; i++)
        {
            v[i] = str[i-1] - '0' -1;
            s[i] = s[i - 1] + v[i];
            if (s[i] == 0)res++;
            res += mymap[s[i]];
            mymap[s[i]]++;
        }
        cout << res << endl;
    }
 
    
    return 0;
}