自动搬运

查看原文

来自洛谷，原作者为

	xxy_free_ioi ​博观而约取，厚积而薄发 | 最后在线时间: 2025/8/22 17:05

搬运于2025-08-24 23:11:43，当前版本为作者最后更新于2025-03-25 21:17:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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;
}