CF1045I Palindrome Pairs 题解【状态压缩】【字符串】【回文串】

点击量：416

    应该是比较好想的状压，回文算法虽然没怎么学过，但是要知道回文的性质呀。

目录

Description

After learning a lot about space exploration, a little girl named Ana wants to change the subject.

Ana is a girl who loves palindromes (string that can be read the same backwards as forward). She has learned how to check for a given string whether it’s a palindrome or not, but soon she grew tired of this problem, so she came up with a more interesting one and she needs your help to solve it:

You are given an array of strings which consist of only small letters of the alphabet. Your task is to find how many palindrome pairs are there in the array. A palindrome pair is a pair of strings such that the following condition holds: at least one permutation of the concatenation of the two strings is a palindrome. In other words, if you have two strings, let’s say “\(\tt aab\)” and “\(\tt abcac\)”, and you concatenate them into “aababcac”, we have to check if there exists a permutation of this new string such that it is a palindrome (in this case there exists the permutation “\(\tt aabccbaa\)”).

Two pairs are considered different if the strings are located on different indices. The pair of strings with indices \((i,j)\) is considered the same as the pair \((j,i)\).

Input

The first line contains a positive integer \(N (1\le N\le 100000)\), representing the length of the input array.

Eacg of the next \(N\) lines contains a string (consisting of lowercase English letters from ‘\(\tt a\)’ to ‘\(\tt z\)’) — an element of the input array.

The total number of characters in the input array will be less than \(1000000\).

Output

Output one number, representing how many palindrome pairs there are in the array.

Examples

input

3
aa
bb
cd

output

1

input

6
aab
abcac
dffe
ed
aa
aade

output

6

Note

The first example:

1. \(\tt aa+bb\rightarrow abba\).

The second example:

1. \(\tt aab+abcac=aababcac\rightarrow aabccbaa\)
2. \(\tt aab+aa=aabaa\)
3. \(\tt abcac+aa=abcacaa\rightarrow aacbcaa\)
4. \(\tt dffe+ed=dffeed\rightarrow fdeedf\)
5. \(\tt dffe+aade=dffeaade\rightarrow adfaafde\)
6. \(\tt ed+aade=edaade\rightarrow aeddea\)

题意：

    给定\(N(1\le N\le 100000)\)个字符串\(s_i\)，问有多少对有序数对\((i,j)(i<j)\)满足\(s_i+s_j\)得到的结果在重新组合后能得到回文串。字符串长度和不超过\(1000000\)。

题解：

    我们首先不考虑字符串的加和问题。如果单独对于一个字符串，怎么判断它能否在重新组合后得到一个回文串呢？回文串分奇串和偶串，对于奇串，有且仅有一个元素出现的次数为奇数，剩下的全为偶数，否则无法配对回文；对于偶串，所有元素出现的次数都是偶数。当问题中只出现奇数和偶数时，我们考虑状压异或。

    如果我们记录每个字母出现的次数，那么两个字符串中字母的各项加起来得到的一定至多只有一个奇数，转化为二进制则至多有\(1\)个\(1\)。因为字母只有\(26\)位，所以很容易想到状压。那么我们把当前读入的字符串转化为二进制，能和这个字符串匹配的有哪些呢？每一位单独做加法，就是异或运算，要求得到的结果至多只有一个\(1\)，那么能产生贡献的二进制数与这个数的差异一定不超过一位。此时枚举是哪一位不同，然后转移这样的数的数量即可，注意还要加上恰好相同的字符串数量。

    如果开\(2^{26}\)的\(\tt int\)是刚好会爆256M的，由于状态数只有\(O(n)\)，所以我们可以开\(\tt map\)，来用\(O(n\log n)\)的时间换取一些空间。

Code：

#include<cstdio>
#include<map>
using std::map;
map<int,int> f;
char c[1001000];
int main()
{
    int n;
    scanf("%d",&n);
    long long ans=0;
    for(int i=1;i<=n;++i)
    {
        int cnt=0;
        scanf("%s",c);
        for(int j=0;c[j]!='\0';++j)
            cnt^=(1<<(c[j]-'a'));
        ans+=f[cnt];
        for(int j=0;j<=25;++j)
            ans+=f[cnt^(1<<j)];
        ++f[cnt];//注意把自己的出现次数+1
    }
    printf("%I64d\n",ans);
    return 0;
}