统计可被等价消除的子串数:每种字符出现偶数次 ⟺ 前缀奇偶掩码相同。
小 A 有一个仅包含小写英文字母的字符串 S。
对于一个字符串,如果能通过每次删去其中两个相同字符的方式,把它变为空串,则称这个字符串是可以被等价消除的(注意:两个字符不要求相邻)。
小 A 想知道 S 有多少个子串是可以被等价消除的。
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 |
mask[l] = mask[r],于是从"枚举 O(|S|²) 个子串"变成了"同状态下标两两配对"先扫一遍前缀掩码(这里只用到字母 a、b,记 mask 的第 0 位为 a、第 1 位为 b)。
| 下标 i | 前缀 | a 的奇偶 | b 的奇偶 | mask[i] |
|---|---|---|---|---|
| 0 | (空) | 0 | 0 | 0 |
| 1 | a | 1 | 0 | 1 |
| 2 | aa | 0 | 0 | 0 |
| 3 | aaa | 1 | 0 | 1 |
| 4 | aaaa | 0 | 0 | 0 |
| 5 | aaaaa | 1 | 0 | 1 |
| 6 | aaaaab | 1 | 1 | 3 |
| 7 | aaaaabb | 1 | 0 | 1 |
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
不含 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
✅ 与公式一致
这次出现了 a、b、c 三种字符,把每一位分别看成 a、b、c 的奇偶。
| 下标 i | 前缀 | a | b | c | mask[i] |
|---|---|---|---|---|---|
| 0 | (空) | 0 | 0 | 0 | 0 |
| 1 | b | 0 | 1 | 0 | 2 |
| 2 | ba | 1 | 1 | 0 | 3 |
| 3 | bab | 1 | 0 | 0 | 1 |
| 4 | baba | 0 | 0 | 0 | 0 |
| 5 | babac | 0 | 0 | 1 | 4 |
| 6 | babaca | 1 | 0 | 1 | 5 |
| 7 | babacab | 1 | 1 | 1 | 7 |
| 8 | babacaba | 0 | 1 | 1 | 6 |
| 9 | babacabab | 0 | 0 | 1 | 4 |
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
(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
✅ 与公式一致
扫一遍得到所有前缀掩码,用哈希表统计每种掩码出现多少次
cnt[0] = 1 必须先计入(空前缀);② 每读一个字符用 mask ^= 1 << k 翻转奇偶位;③ 答案 Σ C(cnt, 2) 用 long long,上界约 2 × 10¹⁰(全为同一字母时约 10¹⁰)。把 |S| + 1 个掩码排序,相同值连成一段,段长 L 贡献 C(L, 2)
| 方案 | 复杂度 | 代码量 |
|---|---|---|
| 前缀掩码 + 哈希表 | O(|S|) | 约 20 行 |
| 前缀掩码 + 排序 | O(|S| log |S|) | 约 18 行 |
| 枚举所有子串逐个检查 | O(|S|² × 26) ≈ 10¹² | ❌ 超时 |
第一行输入 |S|,第二行输入字符串 S(仅小写字母)。程序展示前缀奇偶掩码、同状态分组与答案;|S| ≤ 300 时还会用暴力枚举所有子串交叉验证。
点按钮开始 →
#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; }
mask[l] = mask[r]。把两段前缀"异或抵消":子串 (l+1 … r) 的奇偶状态 = mask[r] ⊕ mask[l] = 0,也就是每个字母都是偶数次 ✓。| 代码 | 作用 | 为什么这样写 |
|---|---|---|
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)——用哈希表或排序即可。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
7 | 9 | 题面样例 1 |
9 | 2 | 题面样例 2 |
1 | 0 | 单字符无法成对,无合法子串 |
2 | 1 | 整串即可消空 |
2 | 0 | 两个不同字符都只出现 1 次 |
4 | 1 | 只有整串合法 |
4 | 3 | aa、bb、aabb 三段 |
6 | 6 | aa、bb、cc、aabb、bbcc、aabbcc |
3 | 0 | 任何子串都有字母出现奇数次 |
cnt[0] = 1 了吗?② 用 long long 吗?③ 复杂度 O(|S|) 吗?④ 转移是"异或翻转奇偶位"吗?cnt[0] = 1,否则所有"从开头开始"的合法子串都会丢。哈希表最多存 |S| + 1 = 200001 个不同掩码,每个键值对约 16 B,总计几 MB。
✅ 线性时间。相比枚举所有子串的 O(|S|² × 26) ≈ 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 存状态 → 次数 | 状态种类多但总量可控的计数问题 |