官方题解

T6 午枫的字符串制造

题目大意

给定一个长度为 $n$ 的字符串，求有多少个连续子串可以通过重新排列得到回文串。

题解思路

首先，如果用 $O(n^2)$ 暴力枚举所有区间肯定是不可行的。于是我们需要考虑优化。

我们如何可以快速判断一个子串能否通过重新排列得到一个回文串？

不难发现，如果这个子串的长度是偶数，那么所有的字母的个数都是偶数就可以排列成回文串；如果这个子串的长度是奇数，那么只能有一个字母的个数是奇数，才可以排列成回文串。

那么我们可以用长度为 $26$ 的二进制状态表示每一个字母个数的奇偶。

奇偶性可以通过异或来表达。记 $State_i$ 为前 $i$ 个字母的奇偶状态，定义 $State_0=0$ ，$cnt_{State}$ 为 $State$ 这种状态的数量。我们可以通过枚举区间右端点 $i$ ，得到 $State_i$ ，那么我们可以考虑分回文串的奇偶长度分两个情况考虑：

• 回文串的长度为偶数，此时有 $cnt_{State_j}$ 个左端点 $j$ 可以形成回文串，其中 $0\leq j\leq i-1$ 且 $State_i=State_j$ 。
• 回文串的长度为奇数，此时我们可以枚举 $26$ 个字母为奇数状态的情况，设第 $k$ 个字母的个数是奇数的状态为 $mask=State_i\oplus (1<<k)$ ，那么有 $cnt_{mask}$ 个左端点 $j$ 可以形成回文串，其中 $0\leq j\leq i-1$ 且 $mask=State_j$ 。

字符串的长度为 $n$ 且每个状态最多延申出 $26$ 个状态，空间复杂度最大为 $O(26n)$ ，此题空间限制给了 $1GB$ ，因此是可以通过的。

时间复杂度为 $O(26n)$ 。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'

void solve(){
    int n;cin>>n;
    string s;cin>>s;s=' '+s;

    vector<int>cnt((1ll<<26)+1);
    cnt[0]=1;
    int S=0;
    int res=0;
    for(int i=1;i<=n;i++){
        int x=s[i]-'a';
        S^=(1ll<<x);
        res+=cnt[S];
        
        for(int j=0;j<26;j++){
            int tmp=S^(1ll<<j);
            res+=cnt[tmp];
        }

        cnt[S]++;
    }
    cout<<res<<endl;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    solve();
}