一、题目解读
2025年GESP七级考试中的“等价消除（洛谷P11965）”问题要求统计给定字符串中满足等价条件的子串数量。所谓“等价子串”，是指子串中所有字符出现的次数均相同。题目需要高效算法解决，考验对字符串处理和状态压缩的掌握。
二、解题思路
采用位运算+哈希表的核心思想：
1. 将字符映射为二进制位：每个字符（如'a'-'z'）对应一位（如1<<('a'-'a')到1<<('z'-'a')），子串状态为各字符位异或结果。
2. 统计等价子串：若当前状态已存在，说明存在前缀与该子串等价，其子串数量计入答案；同时更新哈希表记录当前状态出现次数。
三、解题步骤
1. 初始化：定义哈希表stateCount，初始状态mask=0（空串）计数为1。
2. 遍历处理：
对每个字符，通过mask ^= (1 << (s[i] - 'a'))更新状态（异或操作实现字符添加/删除）。
查询stateCount[mask]获取当前状态的出现次数，累加到答案。
更新哈希表stateCount[mask]++。
3. 结果输出：返回累计的等价子串总数。
四、代码与注释
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
// 核心函数：统计等价子串数量
long long countEquivalentSubstrings(const string& s) {
int n = s.size();
long long count = 0; // 答案计数器
unordered_map<int, int> stateCount; // 记录状态出现次数
stateCount[0] = 1; // 空串状态初始化为1
int mask = 0; // 当前子串状态（二进制位表示）
for (int i = 0; i < n; ++i) {
mask ^= (1 << (s[i] - 'a')); // 异或更新状态（字符转位操作）
count += stateCount[mask]; // 累加已有状态的子串数
stateCount[mask]++; // 更新状态计数
}
return count;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s;
cin >> n >> s; // 输入（题目可能有多组数据，但此处简化）
cout << countEquivalentSubstrings(s) << endl;
return 0;
}