位运算与哈希表：2025 GESP 七级等价消除问题详解

一、问题理解与算法思路

等价消除问题要求我们统计字符串中所有满足"字符出现次数均为偶数"的子串数量。这类问题通常需要使用位运算和前缀和的思想来解决。

二、完整代码实现（带详细注释）

#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; // 初始状态：所有字符出现0次（偶数次）
    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;
}

三、算法核心解析

1. 位掩码设计：

• 使用26位整数表示26个字母的奇偶状态

• 每位0表示偶数次，1表示奇数次

• 异或运算(^)切换状态

2. 前缀和思想：

• 利用哈希表记录各状态出现位置

• 相同状态间的子串满足条件

3. 数学原理：

• 子串s[i..j]满足条件等价于mask[i] == mask[j+1]

• 通过组合数学计算相同状态的对数

四、复杂度分析

• 时间复杂度：O(n)

• 空间复杂度：O(n)

• 适用于字母数量有限的情况

五、实际应用场景

1. DNA序列分析

2. 数据校验

3. 密码学中的奇偶校验

4. 文本压缩算法

参考：位运算