AT_abc295_d

很显然，满足条件的子段的异或和均为 \(0\)（因为每个数都出现了偶数次，而两个相同的数的异或值为 \(0\)）。问题转化为求异或和为 \(0\) 的子段的个数。

不难想到，可以从前往后扫一遍，并且计算异或和，可以得出起点为 \(1\) 且满足条件的子段。那么如何计算中间的子段数量？有如下可行的方案：计算异或和并不是直接异或本身 \(a_i\)，而是异或 \(2^{a_i}\)（把每个数的状态用二进制表示，不同数字的位置是唯一的，效率高），然后令答案加上当前异或和在前面出现的次数即可（异或和不变，则说明中间一段的异或和为 \(0\)，为符合要求的子段）。

具体实现见代码：

#include <iostream>
#include <cstdio>
#define int long long

using namespace std;

int cnt[1000001],len,ans,k,d;

signed main()
{
	cnt[0] = 1;
	string s;
	cin >> s;
	len = s.size();
	for( int i = 0 ; i < len ; i ++ )
	{
		k = s[i] - '0';
		k = 1 << k;//等同于 2^k
		d ^= k;
		ans += cnt[d];
		cnt[d] ++;
	}
	cout << ans;
	return 0;
}