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()
{ioint 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