题目链接:https://atcoder.jp/contests/abc295/tasks/abc295_d
题意:
给定一个字符串，字符串中仅包含数字字符，问其中有多少个子串，满足条件：通过重新排列以后，得到的新的字符串是某个字符串重复两次的结果。
Sample:
20230322
4
样例说明：满足题意的子串有[1, 6], [1, 8], [2, 7], [7, 8]。
input:
一个字符串。
output
一个整数，表示符合题意的子串的总数。
Solution:
因为子串要能够在通过重新排列后形成某个字符串重复两次的结果，所以很明显地，每个符合题意的子串，它里面每种字符的数目都是偶数。而且只要它里面每种字符的数目是偶数次，那么一定符合题意，反之，一定不合题意。
定义Ri：在字符串的前i个字符中，每个字符出现的次数mod2。
对于样例有：
i = 0 0000000000
i = 1 0010000000
i = 2 1010000000
i = 3 1000000000
i = 4 1001000000
i = 5 0001000000
i = 6 0000000000
i = 7 0010000000
i = 8 0000000000
那么满足题意的子串[i, j]，有且仅有Rj - 1 = Ri这一种情况， 因为只有这种情况子串中每个字符出现的次数是偶数次。
Code:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);
string s; cin >> s;
vector<int> cnt(10, 0);
map<vector<int>, LL> mp;
mp[cnt] ++;
for(int i = 0; i < s.size(); i ++) {
cnt[s[i] - '0'] ++;
cnt[s[i] - '0'] %= 2;
mp[cnt] ++;
}
LL ans = 0;
for(auto[x, y] : mp) {
ans += (LL)(y) * (y - 1) / 2;
}
cout << ans;
}