题目大意

给定一个由数字组成字符串\(S\),求\(S\)中每个数字均出现偶数次的子串个数

思路

考虑到每个数字的状态非奇即偶，可以用01串来表示状态。

即：二进制状态压缩，用0来表示这位数字出现次数为偶数次，用1来表示这位数字出现次数为奇数次。然后考虑如何转移即可。

我们从左到右扫描字符串，用一个变量\(tmp\)储存当前的状态，那么每扫到一个新的字符当前的状态变为：\(tmp\) xor \((1<<s[i])\),当前状态的第\((1<<s[i])\)位就是\(s[i]\)的状态。

接下来思考一下什么时候符合题目条件，可以对我们的结果做出贡献？不难想到，当前的状态如果在之前出现过，

即：之前的一个字符串的奇偶性（每个字符的奇偶状态）和当前的串是相同的，那么将之前的串从当前的串中去除，所有字符就都出现了偶数次，满足题目条件了。因为我们是从左到右扫描的整个字符串，所以之前出现过的状态均为当前状态的子串，符合要求的串就是从上一个状态到当前的状态的一个子串。

至此，本题迎刃而解。用一个map数组\(f\)来存储每个状态出现的次数，特别的：\(f_{0}=0\)。每扫到一个状态\(tmp\)，令\(ans+=f_{tmp}\)，然后把当前状态的出现次数加一。

代_码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
using namespace std;
#define ll long long
//miku miku miku miku miku
void mikufan_114514(){
	cout<<"MIKUMIKUMIKUMIKU";
	cout<<"39C5BB";
}
inline ll read();
string s;
map<ll,ll> f;
ll ans=0,tmp=0;
int main()
{
	cin>>s;
	ll n=s.size();
	f[0]=1;
	for(int i=0;i<n;i++){
		tmp ^= (1<<(s[i]-'0'));
		ans+=f[tmp]; //答案加上之前出现过的当前状态的次数
		f[tmp]++;//当前状态出现过的次数加一
	}
	cout<<ans;
	return 0;
}
ll read(){ll w=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0' && ch<='9'){x=x*10+(ch-'0');ch=getchar();}return x*w;}