题目描述

难度分:$939$

输入长度$\leq 5 \times 10^5$的字符串$s$，只包含数字字符。

如果某个子串可以重排成AA这样的模式（即某个字符串重复两遍），则称为happy串。求$s$的所有非空happy串数量。

输入样例$1$

20230322

输出样例$1$

4

输入样例$2$

0112223333444445555556666666777777778888888889999999999

输出样例$2$

185

输入样例$3$

3141592653589793238462643383279502884197169399375105820974944

输出样例$3$

9

算法

前綴和

如果要形成happy串，每个数字必须出现偶数次，这种只跟奇偶性相关的就很容易想到异或操作。对于以$s[r]$结尾的某个串，如果前面存在一个$l$，使得$[1,l)$中所有数字的频数与$[1,r]$中所有数字的频数奇偶性相同，则$[l,r]$所有数字的频数都是偶数。前面有多少个符合题意的$l$，$s[r]$结尾对应的happy串就有多少个，累加到答案上即可。

而最多一共只有$10$种数字，因此用一个$10$位的二进制数来状压就可以，用前缀异或和来表示$[1,i]$中每个数字的频数奇偶性。前缀异或和用一个哈希表$mp$来存储，$mp[eor]$表示某个异或和$eor$的数量。

复杂度分析

时间复杂度

遍历了一遍$s$串就求得了答案，每次循环中的计算只涉及哈希表的查找操作，是$O(1)$的，因此算法总的时间复杂度为$O(n)$。

空间复杂度

仅开辟了一个哈希表来存储前缀异或和，由于$s$串最多只有$10$种数字，因此哈希表最多只有$2^{10}$个键值对。因此，看成个很大的常数也可以（相比$n \leq 5 \times 10^5$已经很小了），额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
typedef long long LL;
const int N = 500010;
char s[N];

int main() {
    scanf("%s", s + 1);
    int n = strlen(s + 1);
    unordered_map<LL, int> mp;
    mp[0] = 1;
    int eor = 0;
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        eor ^= 1<<(s[i] - '0');
        ans += mp.count(eor)? mp[eor]: 0;
        mp[eor]++;
    }
    printf("%lld\n", ans);
    return 0;
}