Decode

 计数问题。

考虑纯暴力写法：

    string s; cin>>s; 
    int n=s.size(); s=' '+s; 
    int ans=0; 
    for(int l=1;l<=n;l++)
    for(int r=l;r<=n;r++)
    for(int i=l;i<=r;i++)
    for(int j=i;j<=r;j++)
    if(count(begin(s)+i,begin(s)+j+1,'1')==count(begin(s)+i,begin(s)+j+1,'0'))
    ans++; 
    cout<<ans<<endl; 

O(n^5)的复杂度，复杂上天。

考虑L=1，R=n时，满足条件的（x，y)对数的优化写法：

vector<int>pre(n+10); 
for(int i=1;i<=n;i++)
pre[i]=(pre[i-1]+(s[i]=='1'?1:-1)); 
map<int,int>cnt; 
int ans=0; 
for(int i=1;i<=n;i++){
    ans+=cnt[pre[i]]; 
    cnt[pre[i]]++;
}

复杂度O(nlogn)。

再根据乘法原理 ，可以进一步处理所有[L,R]下（x，y）的对数。

#include<bits/stdc++.h>
using namespace std;
void __p(int x) {cerr<<x;}
void __p(long long x){cerr<<x;}
void __p(long double x){cerr<<x;}
void __p(double x){cerr<<x;}
void __p(string s){cerr<<s;}
void __p(char s){cerr<<s;}
void _print(){cerr<<"]\n";}
template<typename T,typename... V>//定义类模版
void _print(T t,V... v){__p(t);if(sizeof...(v))cerr<<",";_print(v...);}
#define debug(x...) cerr<<"["<<#x<<"] = ["; _print(x);
#define see1 cout<<"-------------\n";
#define see2 cerr<<"-------------\n";
#define io ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long 
#define double long double
#define sqrt sqrtl
/*

1.进行移位运算时, 1ll<<n ,1后面不要忘了ll否则会溢出
2.数组开太大放到外面,作为全局数组
3.dfs递归深度超过几千层可能会溢出
4.accumulate(begin(a),end(a),0LL); 
*/
const int p=1e9+7; 

void solve()
{
    string s; cin>>s; 
    int n=s.size(); 
    s=' '+s; 
    vector<int>pre(n+10); 
    for(int i=1;i<=n;i++)
    pre[i]=pre[i-1]+(s[i]=='1'?1:-1); 
    int ans=0; 
    map<int,int>cnt; 
    for(int i=0;i<=n;i++){
        ans=(ans+cnt[pre[i]]*(n-i+1))%p;
        cnt[pre[i]]=(cnt[pre[i]]+i+1)%p; 
    }
    cout<<ans<<endl; 
}  

signed main()
{
    io
    int t=1;
    cin>>t; 
    while(t--){
        solve();
    }
}


for(int i=1;i<=n;i++)
pre[i]=(pre[i-1]+(s[i]=='1'?1:-1)); 
int ans=0; 
for(int i=0;i<=n;i++){
    ans=(ans+cnt[pre[i]]*(n-i+1))%p;
    cnt[pre[i]]=(cnt[pre[i]]+i+1)%p;
}
cout<<ans<<endl; 

25/4/30