等价消除 题解

题目分析

题目中定义了一个字符串“可被等价消除”：每次可以选择字符串中的两个相同字符并删除它们。如果能够通过若干次这样的操作使字符串变为空串，则该字符串是可被等价消除的。

关键观察：
由于每次删除的都是两个相同的字符，而且与字符的位置无关，因此一个字符串能否被完全消除，只与每种字符的出现次数有关。
一个字符能够被完全删除，当且仅当它的出现次数为偶数。
因此，一个字符串是可被等价消除的 当且仅当字符串中每种字符的出现次数均为偶数。

题目要求我们统计字符串 $S$ 的所有子串中，满足这一条件的子串个数。

解题思路

我们可以在原字符串上求前缀信息。
设原字符串长度为 $n$，定义前缀 $i$ 的状态为一个 $26$ 位的二进制数 $mask_i$：

• 第 $k$ 位（对应字母 'a'+k）为 $1$，表示从第 $1$ 个字符到第 $i$ 个字符中，字母 'a'+k 出现了奇数次；
• 为 $0$ 表示出现了偶数次。

对于一个子串 $S[l..r]$，其中每种字符出现次数均为偶数，等价于：

因为 $mask_r$ 异或 $mask_{l-1}$ 的结果就反映了子串内各字母出现次数的奇偶性。二者相等说明子串内所有位均为 $0$，即全部为偶数次。

因此问题转化为：
统计有多少对 $(i, j)$，满足 $0\le i<j\le n$ 且 $mask_i = mask_j$。
即前缀状态相同的对数。

算法说明

1. 用一个变量 $v$ 表示当前的前缀状态（初始为 $0$）。
2. 使用哈希表（或 C++ 中的 map）记录每个状态在之前的前缀中出现的次数。初始时，将状态 $0$ 的计数设为 $1$（代表空前缀）。
3. 从左到右遍历字符串 $S$ 的每个字符：
   • 将该字符对应的二进制位翻转：v ^= 1 << (s[i] - 'a')。
   • 将当前答案累加之前该状态出现的次数 ans += cnt[v]。
   • 更新该状态的出现次数 cnt[v]++。
4. 遍历结束后输出 ans。

正确性：
对于当前前缀 $i$，所有与它状态相同的更早的前缀都会与它形成一个满足条件的子串。由于我们每次更新前先累加答案，恰好可以统计完所有以 $i$ 结尾的合法子串。

时间复杂度分析

• 遍历字符串：$O(n)$。
• 每次状态翻转与查询/更新哈希表：map 操作复杂度为 $O(\log M)$，其中 $M$ 为不同状态数。由于最多出现 $n+1$ 个不同状态，整体复杂度为 $O(n \log n)$。
• 空间复杂度：$O(n)$，用于存储哈希表。

在 $n \le 2\times 10^5$ 的范围内，该算法可以轻松通过所有测试点。
实际上也可以用 unordered_map 将平均复杂度优化至 $O(n)$，但需要考虑哈希冲突带来的常数影响。参考代码使用的是 map，已足够高效。

参考代码及解释

cpp
复制
1#include <cstdio>
2#include <map>
3using namespace std;
4const int N = 2e5 + 5;
5
6int n;
7char s[N];
8map<int, int> m;   // 记录每种前缀状态出现的次数
9long long ans;     // 答案可能较大，使用 long long
10
11int main() {
12    scanf("%d", &n);
13    scanf("%s", s + 1);  // 字符串从下标 1 开始存储
14
15    int v = 0;           // 当前前缀状态
16    m[v]++;              // 空前缀状态 0 出现1次
17
18    for (int i = 1; i <= n; i++) {
19        v ^= 1 << (s[i] - 'a');   // 翻转当前字符对应位
20        ans += m[v];              // 累加之前出现过的相同状态数
21        m[v]++;                   // 更新当前状态出现次数
22    }
23
24    printf("%lld\n", ans);
25    return 0;
26}

代码解析：

• v 是一个 int 类型的变量，低 $26$ 位分别表示 a~z 每个字母出现次数的奇偶性（1 为奇，0 为偶）。
• m[v] 用 map 存储每个前缀状态已经出现的次数。
• 初始时，空前缀状态为 $0$，出现 $1$ 次。
• 遍历字符串，每步更新 v 并将 m[v] 累加到答案中，表示当前前缀与之前所有同状态前缀所构成的子串数量。
• 最终输出总对数 ans。

总结

本题的关键在于将“每种字符出现偶数次”这一条件转化为前缀异或和相等。通过状态压缩与哈希表统计，我们可以在 $O(n \log n)$ 的时间内求出所有合法子串的数量。这种“前缀状态相等”的套路在字符串奇偶性相关计数问题中非常常见，值得熟练掌握。