A50248.午枫的字符串制造 题解

显而易见的，回文串最多只有一个字符出现次数是奇数。

奇偶性我们可以简单地用 $0/1$ 代替。所以，我们有 $26$ 个字母，每个字母有 $0/1$ 两种状态。所以我们可以使用状态压缩！（题目1024MB也是一种提醒）

所以，$dp_{mask}$ 表示当目前前缀状态为 $mask$ 的时候的合法子串数量（目前，是指目前处理到了哪一位）。

首先记录一下目前的前缀 $p$，然后将答案加上 $dp_p$。

同时，我们知道，有可能会有一个字母出现奇数次。枚举这个字母，并记录答案。

最后，记得用 $p$ 更新 $dp_p$ 的值。

注意下，一开始 $dp_0=1$，因为任何字母都出现 $0$ 次。

时间复杂度：$O(n)$

空间复杂度：$O(n+2^{26})$

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,cnt,ans;
string s;
int dp[1<<26];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>s;
    dp[0]=1;
    for(ll i=0;i<n;i++){
        cnt^=1<<(s[i]-'a');
        ans+=dp[cnt];
        for(ll j=0;j<26;j++) ans+=dp[cnt^(1<<j)];
        dp[cnt]++;
    }
    cout<<ans;
    return 0;
}