abc295D题解
lsz_
·
·
题解
题目链接（atcoder 版）
题目链接（洛谷版）
更好的阅读体验
写在前面
这题记得开 long long！！！
题目大意
给定一个序列 S，求出有多少 S 的字串为“开心序列”。
“开心序列”的定义：当一个由数字组成的字符串可以被重新排列为（或已经是）某个字符串的重复两次时，该序列便为“开心序列”。
解决思路
这题 打个表 观察一下就很容易发现任何一个“开心序列”都有这个性质：
结合样例（`20230322`）看一下：
`202303` 为开心序列，其中 `0`，`3`，`2` 都出现了两次。
`20230322` 为开心序列，其中 `0`，`3` 都出现了两次，`2` 出现了四次。
`023032` 为开心序列，其中 `0`，`3`，`2` 都出现了两次。
`202303` 为开心序列，其中 `0`，`3`，`2` 都出现了两次。
所以只需要统计每个时刻各个 $x_i$ 的奇偶性，在加一下之前奇偶性一样的序列即可。
值得一提的是在操作前要先把 `mp[0000000000]` 初始化为 1，因为左端点可以为 1（这里指下标）。
再看一遍样例：
状态可以用二进制移位存，操作用异或。~~当然你也可以开 10 维数组。~~
### 代码
```
#include<bits/stdc++.h>
#define LL long long
using namespace std;
char c[500010];
int i,n,now,len;
LL ans;
map<int,int>mp;
int main()
{
mp[0]=1;
cin>>c;
len=strlen(c);
for(i=0;i<len;i++)
{
now^=(1<<(c[i]-48));
ans+=mp[now];
mp[now]++;
}
cout<<ans;
return 0;
}
```