题解：P11965 [GESP202503 七级] 等价消除

· · 题解

P11965 [GESP202503 七级] 等价消除

好题。。。

解法

因为只有 26 个字母，所以考虑状压。设转态 dp_{i,j}，表示字符串的 i \sim j 位中，二进制下每位所对应字母数量（第一位对应 a，第二位对应 b，以此类推）是否为奇数（奇数为 1，偶数为 0）。那么，我们可以显而易见的得出两个结论：

  1. 若 dp_{i,j} = 0，则方案数 + 1。
  2. 若 dp_{1,i-1} = dp_{1,j}，则 dp_{i, j} = dp_{1,i-1} - dp_{1,j} = 0。
  3. dp_{1, i} = dp_{1,i} \oplus 2^{S_i-'a'}

所以，我们发现 dp 只需要递推即可。同时用一个数组 f_{dp} 记录当状态为 dp 时，可行子串数量，每次方案数加上 f_{dp}（若 dp = 0，则还需 + 1），最后再将 f_{dp} 加 1 即可。

代码

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int S = 1 << 26;

ll n, res, dp;
ll f[S];
string s;

int main() {
    cin >> n >> s;

    for (int i = 0; i < n; i++) {
        dp ^= (1 << (s[i] - 'a'));
        if (dp == 0) res++;
        res += f[dp];
        f[dp]++;
    }

    cout << res << '\n';

    return 0;
}