GESP 题解库 / 7 级题解 / [GESP202503 七级] 等价消除 · 第 9 / 24 题
GESP202503 七级 · P11965 · 中等

等价消除

统计可被等价消除的子串数:每种字符出现偶数次 ⟺ 前缀奇偶掩码相同。

📊
|S| ≤ 2 × 10⁵
字符串长度
🎭
26 位掩码
状态编码
⚡
O(|S|)
时间复杂度
🎯
前缀异或 + 组合计数
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

小 A 有一个仅包含小写英文字母的字符串 S。

对于一个字符串,如果能通过每次删去其中两个相同字符的方式,把它变为空串,则称这个字符串是可以被等价消除的(注意:两个字符不要求相邻)。

小 A 想知道 S 有多少个子串是可以被等价消除的。

💡
一句话结论:一个字符串可被等价消除 ⟺ 每种字符出现的次数都是偶数。
于是问题变成:数一数有多少个子串,其中每个字母都恰好出现偶数次。
怎么快速判断"每个字母都出现偶数次"?给 26 个字母各配一个奇偶位,扫一遍字符串得到前缀奇偶掩码:子串 (l+1 … r) 合法 ⟺ mask[l] = mask[r]。
最后把下标按掩码值分组,同组任取两个下标就是一段合法子串 → 答案 = Σ C(cnt[m], 2)。

🔍 关键词提取

前缀异或奇偶掩码状态压缩组合计数哈希表

已知条件

项目说明
输入第一行 |S|;第二行字符串 S(仅小写英文字母)
输出可被等价消除的子串数量
数据范围1 ≤ |S| ≤ 2 × 10⁵
部分分20%:只含 a、b 两种字符;另 20%:|S| ≤ 2000
操作特点每次删两个相同字符,不要求相邻
答案规模上界 C(200001, 2) ≈ 2 × 10¹⁰(全为同一字母时约 10¹⁰),必须 long long

需要解决的问题

02
思维导图
整理解题思路的全貌
🧩 偶数次 ⟺ 前缀掩码相同
🔁 条件化简
删除两个相同字符:奇偶性不变
能消空 ⟺ 每种字母出现偶数次
等价于"26 个字母的奇偶向量 = 全 0"
不要求相邻 ⇒ 充分性成立
🎭 掩码编码
第 k 个字母 → 二进制的第 k 位
每读一个字符就"翻转"它的位
mask[i] = 前 i 个字符的奇偶状态
状态共 2²⁶ 种,但只出现 |S|+1 个
🧮 计数公式
子串 (l+1 … r) 合法 ⟺ mask[l] = mask[r]
把下标 0…|S| 按 mask 值分组
同组任取两个下标 → C(cnt, 2)
答案 = 对所有掩码求和 C(cnt, 2)
⚠️ 易错点
忘记把 mask[0] = 0 计入(空前缀)
用 int 存答案(可达 2 × 10¹⁰)
误读成"删相邻的两个相同字符"
开 2²⁶ 的计数数组导致内存爆炸
03
样例手算推导
样例的完整推演

🧮 样例 1:S = "aaaaabb",答案 9

先扫一遍前缀掩码(这里只用到字母 a、b,记 mask 的第 0 位为 a、第 1 位为 b)。

下标 i前缀a 的奇偶b 的奇偶mask[i]
0(空)000
1a101
2aa000
3aaa101
4aaaa000
5aaaaa101
6aaaaab113
7aaaaabb101
1
按 mask 值分组并计数

mask = 0:下标 {0, 2, 4} → C(3, 2) = 3 段子串

mask = 1:下标 {1, 3, 5, 7} → C(4, 2) = 6 段子串

mask = 3:下标 {6} → C(1, 2) = 0

合计 3 + 6 = 9

✅ 9

2
直接枚举核对(另一条路)

不含 b 的合法子串:全在 "aaaaa" 里,长度必须是偶数

长度 2:"aa" 共 4 段;长度 4:"aaaa" 共 2 段 → 6 段

含两个 b 的合法子串:必须包含末尾的 "bb",且 a 的个数为偶数

[2…7] = "aaaabb"(4 个 a)✓ [4…7] = "aabb"(2 个 a)✓ [6…7] = "bb"(0 个 a)✓

合计 6 + 3 = 9

✅ 与公式一致

🔑
体会一下这个"巧合":mask = 1 出现了 4 次(下标 1、3、5、7),说明这些位置之后"a 是奇数个、b 是偶数个"的状态反复出现——每取两个这样的下标就能夹出一段合法子串。
注意 mask[0] = 0 必须计入:它代表"空前缀"。如果漏掉它,mask = 0 的下标只剩 {2, 4},答案会从 9 变成 1 + 6 = 7,白丢两段。

🧮 样例 2:S = "babacabab",答案 2

这次出现了 a、b、c 三种字符,把每一位分别看成 a、b、c 的奇偶。

下标 i前缀abcmask[i]
0(空)0000
1b0102
2ba1103
3bab1001
4baba0000
5babac0014
6babaca1015
7babacab1117
8babacaba0116
9babacabab0014
1
分组计数

mask = 0:下标 {0, 4} → C(2, 2) = 1 段

mask = 4:下标 {5, 9} → C(2, 2) = 1 段

mask = 1、2、3、5、6、7:各只有 1 个下标 → 0 段

合计 1 + 1 = 2

✅ 2

2
把这两段子串还原出来

(l = 0, r = 4) → 子串 S[1…4] = "baba":a 出现 2 次、b 出现 2 次 ✓

(l = 5, r = 9) → 子串 S[6…9] = "abab":a 出现 2 次、b 出现 2 次 ✓

其它位置都没有重复的掩码值,凑不出合法子串

所以答案正好是 2

✅ 与公式一致

⚠️
别被"看起来重复"的片段骗了:"babacabab" 里有 "bab"、"aba" 等回文似的结构,但它们内部都有字母出现奇数次,不能消空。
掩码法只认"奇偶状态是否回到过同一个值",不看字符排列的对称性——这也是它能做到 O(|S|) 的原因:把"能不能消空"这个组合条件,翻译成了一个纯粹的"状态相等"判断。
04
解法对比
前缀掩码 + 哈希表 vs 排序 / 枚举子串

⚔️ 解法对比

🟢 前缀掩码 + 哈希表(推荐) 推荐

扫一遍得到所有前缀掩码,用哈希表统计每种掩码出现多少次

  • 时间 O(|S|) 期望
  • 空间 O(|S|):最多 |S| + 1 种状态
  • 代码约 20 行
  • 一遍扫描即得答案
💡
三个关键点:① cnt[0] = 1 必须先计入(空前缀);② 每读一个字符用 mask ^= 1 << k 翻转奇偶位;③ 答案 Σ C(cnt, 2) 用 long long,上界约 2 × 10¹⁰(全为同一字母时约 10¹⁰)。

🟠 前缀掩码 + 排序

把 |S| + 1 个掩码排序,相同值连成一段,段长 L 贡献 C(L, 2)

  • 时间 O(|S| log |S|) ≈ 3.6 × 10⁶
  • 不存在哈希冲突风险
  • 代码约 18 行
  • 可直接用 int 数组排序
⚠️
排序法更"稳":unordered_map 在极端数据下可能被卡常数,而排序是确定性的。两者都对,选你写起来更顺手的那个。

📈 性能对比

方案复杂度代码量
前缀掩码 + 哈希表O(|S|)约 20 行
前缀掩码 + 排序O(|S| log |S|)约 18 行
枚举所有子串逐个检查O(|S|² × 26) ≈ 10¹²❌ 超时
05
算法流程图
一遍扫描 + 同状态配对
开始mask = 0;前缀计数 cnt[0] = 1(空前缀)读入字符 c,翻转它的奇偶位:mask ^= 1 << (c − 97)cnt[mask]++|S| 个字符都处理完了吗?遍历每种掩码的计数:ans += cnt × (cnt − 1) ÷ 2为什么"两个下标配一对"就是一段合法子串?掩码相同 ✓这段区间里每种字母都出现偶数次,可以消空掩码不同 ✗至少有一种字母出现奇数次,不可能消空输出 ans(long long)继续读下一个字符
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🧩 可被等价消除的子串数

第一行输入 |S|,第二行输入字符串 S(仅小写字母)。程序展示前缀奇偶掩码、同状态分组与答案;|S| ≤ 300 时还会用暴力枚举所有子串交叉验证。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码(前缀异或掩码 + 哈希表计数)

#include <bits/stdc++.h>
using namespace std;

char s[200005];

int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", s);

    // cnt[mask] = 前缀奇偶状态为 mask 的位置个数
    unordered_map<int, long long> cnt;
    cnt.reserve(n * 2 + 10);      // 预留空间,避免反复 rehash
    cnt[0] = 1;                   // 空前缀:mask = 0(必须计入!)

    int mask = 0;
    for (int i = 0; i < n; i++) {
        mask ^= 1 << (s[i] - 'a');   // 翻转该字母的"奇偶位"
        cnt[mask]++;                 // 统计这个前缀状态出现的次数
    }

    long long ans = 0;               // 答案上界约 2 × 10¹⁰,必须 long long
    for (auto &p : cnt) {
        long long c = p.second;
        ans += c * (c - 1) / 2;      // 同状态任取两个下标 → 一段合法子串
    }

    printf("%lld\n", ans);
    return 0;
}
🔑
为什么"两个相同掩码的下标"就对应一段可消除子串?设下标 l < r 满足 mask[l] = mask[r]。把两段前缀"异或抵消":子串 (l+1 … r) 的奇偶状态 = mask[r] ⊕ mask[l] = 0,也就是每个字母都是偶数次 ✓。
反过来,若子串里每种字母都是偶数次,则 mask[r] 必然等于 mask[l]。于是"判定子串"变成了"找相同的两个前缀状态"。

📖 关键几行怎么看

代码作用为什么这样写
cnt[0] = 1;空前缀漏掉它就会少算所有"从第 1 个字符开始"的合法子串
mask ^= 1 << (s[i] − 97);翻转奇偶位异或 1 就是"奇偶互换",加两次等于没加
cnt[mask]++;统计同状态每种掩码出现了几次
ans += c * (c − 1) / 2;组合计数同状态的 c 个下标任取 2 个
long long ans类型上界约 2 × 10¹⁰,超出 int
⚠️
四个坑:① 忘记 cnt[0] = 1(样例 1 的答案会从 9 变成 7);② 用 int 存答案(|S| = 2 × 10⁵ 全为同一字母时约 10¹⁰);③ 把题目读成"删相邻的两个相同字符"(那变成另一个问题,与本题完全不同);④ 直接开 cnt[1 << 26] 的数组(约 6.7 × 10⁷ 个 long long ≈ 536 MB,会 MLE)——用哈希表或排序即可。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
7
aaaaabb
9题面样例 1
9
babacabab
2题面样例 2
1
a
0单字符无法成对,无合法子串
2
aa
1整串即可消空
2
ab
0两个不同字符都只出现 1 次
4
abab
1只有整串合法
4
aabb
3aa、bb、aabb 三段
6
aabbcc
6aa、bb、cc、aabb、bbcc、aabbcc
3
aba
0任何子串都有字母出现奇数次
✅
自查清单:① cnt[0] = 1 了吗?② 用 long long 吗?③ 复杂度 O(|S|) 吗?④ 转移是"异或翻转奇偶位"吗?

🚨 易错点清单

⚠️
漏掉空前缀:必须 cnt[0] = 1,否则所有"从开头开始"的合法子串都会丢。
⚠️
int 溢出:|S| = 2 × 10⁵ 全为 a 时答案约 10¹⁰,必须 long long。
⚠️
读错题:题目删的是"两个相同字符"且不要求相邻,不要理解成删相邻相同字符对。
⚠️
内存爆炸:2²⁶ 大小的计数数组约 536 MB,用哈希表或排序代替。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(|S|) 期望
空间复杂度
O(|S|)
|S| 最大
2 × 10⁵
答案上界
C(200001, 2) ≈ 2 × 10¹⁰

时间怎么算的?

空间都用在哪?

哈希表最多存 |S| + 1 = 200001 个不同掩码,每个键值对约 16 B,总计几 MB。

✅ 线性时间。相比枚举所有子串的 O(|S|² × 26) ≈ 10¹²,前缀状态把"区间问题"变成了"两点配对问题",这是字符串计数题最常用的降维套路。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 核心四步
int mask = 0;
unordered_map<int, long long> cnt;
cnt[0] = 1;                                  // ① 空前缀一定要计入
for (int i = 0; i < n; i++) {
    mask ^= 1 << (s[i] - 'a');               // ② 翻转该字母的奇偶位
    cnt[mask]++;                             // ③ 统计同状态的出现次数
}
long long ans = 0;
for (auto &p : cnt) ans += p.second * (p.second - 1) / 2;   // ④ C(cnt, 2)

// 不想用哈希表?排序法同样正确:
// vector<int> ms(n + 1, 0);
// for (int i = 0; i < n; i++) { mask ^= 1 << (s[i] - 'a'); ms[i + 1] = mask; }
// sort(ms.begin(), ms.end());
// 然后扫描相邻相等的段,每段长度 L 贡献 C(L, 2)

// 【同类套路】"区间是否满足某种状态" → "两个前缀状态是否相同"
//   前缀和相同   → 区间和为 0
//   前缀异或相同 → 区间异或为 0
//   前缀奇偶掩码相同 → 区间内每种元素都出现偶数次

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
状态压缩26 个字母的奇偶 → 26 位整数集合状态、开关状态、奇偶约束
前缀状态配对mask[l] = mask[r] ⟺ 区间合法前缀和/前缀异或/前缀 gcd 统计子区间
组合计数同状态下标两两配对 → C(cnt, 2)统计"和相等/同余"的下标对
哈希表计数unordered_map 存状态 → 次数状态种类多但总量可控的计数问题
🌟
思考题:如果把操作改成"每次删去两个不同的字符",判定条件会变成什么?(提示:先看最简单的反例——"ab" 在本题里不可消除,但在新规则下一次就能清空,说明"每种字符偶数次"不再是充要条件。可以从"出现次数最多的字符 ≤ 其余字符数之和"这个方向想一想,于是判定条件变成了关于"最大值与总和"的不等式。)