https://atcoder.jp/contests/abc295/tasks/abc295_d

好题，本来以为需要从区间问题上考虑，奈何算法世界无奇不有。

大意是求一个0-9的子串中区间内的所有元素是成双成对出现的，串的长度为5e5.

很明显我们可以前缀和维护然后去暴力n^2一下。但是数据不允许。

考虑状压每个位置的前缀关系，将状态计数，如果之后又遇到此状态，那么一定存在之前的所有状态的位置到现在位置是一个合法的区间。

本质上还是个思维问题。

code：

const int nn = 5e5+10;
ll s[nn][10];
string st;
map<string,int> mp;
ll ans = 0;
void work(int i){
	for(int j=0;j<10;j++) st[j] = s[i][j]%2+'0';
	ans+=mp[st];
	mp[st]++;
}
void solve()
{
	string str;
	cin>>str;
	str = "@"+str;
	int n = str.size()-1;
	
	st.resize(10);
	for(int i=0;i<10;i++) st[i] = '0';
	mp[st]++;
	
	for(int i=1;i<=n;i++){
		int t = str[i] - '0';
		for(int j=0;j<10;j++){
			s[i][j] = s[i-1][j]+(j==t);
		}
		work(i);
	}
	cout<<ans<<endl;
}