Submission #75270715

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n;
ll a[200005],b[200005],c[200005];
ll ab[200005],ac[200005],bc[200005];
ll _ab,_ac,_bc,_abc;
string s;
map<ll,ll> tab,tac,tbc;
map<pair<ll,pair<ll,ll>>,ll> tabc;
void AB(){
	int x;
	for(int i=0;i<=n;i++) tab[ab[i]]++;
	for(auto a:tab) x=a.second,_ab+=1ll*x*(x-1)/2;
}
void AC(){
	int x;
	for(int i=0;i<=n;i++) tac[ac[i]]++;
	for(auto a:tac) x=a.second,_ac+=1ll*x*(x-1)/2;
}
void BC(){
	int x;
	for(int i=0;i<=n;i++) tbc[bc[i]]++;
	for(auto a:tbc) x=a.second,_bc+=1ll*x*(x-1)/2;
}
void ABC(){
	int x;
	for(int i=0;i<=n;i++) tabc[{ab[i],{ac[i],bc[i]}}]++;
	for(auto a:tabc) x=a.second,_abc+=1ll*x*(x-1)/2;
}
int main(){
	cin>>n>>s,s=" "+s;
	for(int i=1;i<=n;i++) a[i]=a[i-1]+(s[i]=='A'),b[i]=b[i-1]+(s[i]=='B'),c[i]=c[i-1]+(s[i]=='C');
	for(int i=1;i<=n;i++) ab[i]=a[i]-b[i],ac[i]=a[i]-c[i],bc[i]=b[i]-c[i];
	AB(),AC(),BC(),ABC();
	cout<<1ll*n*(n+1)/2-_ab-_ac-_bc+2*_abc;
}

Submission Info

Judge Result