CF 1996 E. Decode(*1600) 思维+前缀和

showball / 2024-09-02 / 原文

CF 1996 E. Decode(*1600) 思维+前缀和

题目链接

题意：

给你一个长度为 $n$ 的二进制字符串，求出所有的子区间的所有满足 $0$ 的个数等于 $1$ 的个数的子区间个数之和。

思路：

首先，求一段区间是否满足 $0$ 的数量是否等于 $1$ 的个数，是非常经典的做法，我们只需要维护一个数组，遇到 $0$ ，就赋值 $-1$ ,否则赋值 $1$ 。那么只要这段区间的区间和为0，即可满足条件，那么只需要前缀和数组的两个值相同即可。

对于本题，我们可以直接去考虑每个满足条件区间的贡献，很简单的乘法原理，左端点可选位置 $\times$ 右端点可选位置，求和即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   string s;
   cin>>s;
   int n=s.size();
   s="?"+s;
   vector<int> a(n+1);
   for(int i=1;i<=n;i++){
      a[i]=a[i-1];
      if(s[i]=='1') a[i]++;
      else a[i]--;
   } 
   map<int,int> suf;
   LL ans=0;
   for(int i=n;i>=1;i--){
    suf[a[i]]+=(n-i+1);
    ans=(ans+1LL*i*suf[a[i]]%mod)%mod;
   }
   cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}