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

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

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

Subscribe

/* */