补题Codeforces Round 962 (Div. 3) Decode

题意：

我们需要算所有l，r组合区间中的x，y组合使得0的数量等于1的数量。

思路：

1.暴力显然不可得，容易想到计算（x，y）的贡献，最后乘上所在区间即可；
2.这里我们将0视为-1，只要前后前缀和的值相等即可判断01数量相等，即sum[x-1] == sum[y]; (用哈希表即可
3.现在来求被包含多少个区间内，l的范围是[0, x]，r的范围是[y, n]，因此就是(x + 1) * (n - y + 1)
4.至于在更新时，我们不断对哈希表加上i + 1，因为这表示我们在下一次找到y时，我们可以选择[0, x]作为左边界，共有i+1个数，而之前的也有贡献，自然就是加上而不是等于。

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N = 1e5 + 10, mod = 1e9 + 7;
int n, x, k;

void solve() 
{
    string s;
    cin >> s;
    n = s.size();
    s = ' ' + s;
    vector<int> sum(n + 1, 0);
    for (int i = 1; i <= n; i ++) {
        sum[i] = sum[i - 1] + (s[i] == '1' ? 1: -1);
    }
    int ans = 0;
    map<int, int> mp;
    mp[0] = 1; // 在遇到第一个前缀和为0时我们需要保证x为1
    for (int i = 1; i <= n; i ++) {
        ans += mp[sum[i]] * (n - i + 1) % mod;
        mp[sum[i]] += i + 1;
    }

    cout << ans % mod << endl;    
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}