引言

题目连接：https://ac.nowcoder.com/acm/contest/75174/E

思路

随意选取一段区间，对其长度进行分类讨论：

1. 若其长度为偶数，则 0 ~ 9 这十个数字在该区间内出现的次数为偶数时，可以将该区间重构成回文。

2. 若其长度为奇数，则满足 0 ~ 9 这十个数有一个出现次数是奇数，其余数为偶数则可将该区间重构成回文。

暴力做法则是枚举 l,r，时间复杂度为 O(n^2)

然而该题并不需要知道该区间数的个数，只需要知道其奇偶性，则正确答案为与当前区间奇偶性相同的前面的区间数（偶数）和只相差一个的区间（奇数时多出来的数可以放到中间）。

例：
1 1 0
假设当前为最后一位 0，那么此时的 [1,3] 的每个数的奇偶性为：

0 奇 1 偶 2 偶 ...

那么和其奇偶性相同的偶数区间没有

奇数区间为 [0,0] ，整个区间，此时多出的奇数次 0 可以放到中间构成回文串。

代码

#include <bits/stdc++.h>
#define ll long long

std::map<int,int> mp;

int main() {
    std::string str;
    std::cin >> str;
    
    mp[0] = 1;
    
    ll ans = 0;
    int len = str.size();
    for (int i = 0, now = 0 ; i < len ; i ++ ) {
        now ^= 1 << (str[i] - '0');
        
        ans += mp[now];
        
        for (int j = 0 ; j < 10 ; j ++ ) {
            ans += mp[now ^ (1 << j)];
        }
        
        mp[now] ++ ;
    }
    
    std::cout << ans << '\n';
    
    return 0;
}