构成回文串的数目

#include<iostream>
#include<map>
#include<string>
using namespace std;

const int N=1e5+10;
typedef long long ll;

int n;
map<int,int> mp;
int sum[N];
ll ans;

int lowbit(int x)
{
    return -x&x;
}
int main()
{
    scanf("%d",&n);
    
    for(int i=0;i<n;i++)
    {
        string str;
        cin>>str;
        int a[30]={0};
        for(int j=0;j<str.size();j++)
        a[str[j]-'a']++;
        for(int j=0;j<26;j++)
        if(a[j]&1) sum[i]+=1<<j;
        mp[sum[i]]++;
    }
    //配对成功后，回文串中最多只能有一个字符的数量是奇数
    for(int i=0;i<n;i++)//该字符串与其他字符串能否成功配对
    {
        int x=sum[i];
        while(x)
        {
            int y=sum[i]-lowbit(x);//减去最后一个1，x和y配对，最多会有一个奇数
            if(mp[y]) ans+=1ll*mp[y];
            x-=lowbit(x);
        }
    }
    
    for(auto p:mp) //自身与自身配对
    ans+=p.second*1ll*(p.second-1)/2;
    
    cout<<ans;
    
    return 0;
}