Dasha and Nightmares Dasha 和噩梦

time limit per test
4 seconds
memory limit per test

5
12 megabytes
Dasha, an excellent student, is studying at the best mathematical lyceum in the country. Recently, a mysterious stranger brought nn words consisting of small latin letters s1,s2,…,sns1,s2,…,sn to the lyceum. Since that day, Dasha has been tormented by nightmares.
Consider some pair of integers 〈i,j〉〈i,j〉 (1≤i≤j≤n1≤i≤j≤n). A nightmare is a string for which it is true:

• It is obtained by concatenation sisjsisj;
  
• Its length is odd;
  
• The number of different letters in it is exactly 2
  5
  2
  5
  ;
  
• The number of occurrences of each letter that is in the word is odd.
  

For example, if si=si= "abcdefg" and sj=sj= "ijklmnopqrstuvwxyz", the pair 〈i,j〉〈i,j〉 creates a nightmare.
Dasha will stop having nightmares if she counts their number. There are too many nightmares, so Dasha needs your help. Count the number of different nightmares.
Nightmares are called different if the corresponding pairs 〈i,j〉〈i,j〉 are different. The pairs 〈i1,j1〉〈i1,j1〉 and 〈i2,j2〉〈i2,j2〉 are called different if i1≠i2i1≠i2 or j1≠j2j1≠j2.
Input
The first line contains a single integer nn (1≤n≤2⋅10
5
1≤n≤2⋅10
5
) — the number of words.
The following nn lines contain the words s1,s2,…,sns1,s2,…,sn, consisting of small latin letters.
It is guaranteed that the total length of words does not exceed 
5
⋅106
5
⋅106.
Output
Print a single integer — the number of different nightmares.
Example
Input
Copy

1. [/code]10
2. ftl
3. abcdefghijklmnopqrstuvwxy
4. abcdeffghijkllmnopqrsttuvwxy
5. ffftl
6. aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
7. thedevid
8. bcdefghhiiiijklmnopqrsuwxyz
9. gorillasilverback
10. abcdefg
11. ijklmnopqrstuvwxyz
12. Output
13. Copy
14. [code]
15. 5

复制代码

Note
In the first test, nightmares are created by pairs 〈1,3〉〈1,3〉, 〈2,
5
〉〈2,
5
〉, 〈3,4〉〈3,4〉, 〈6,7〉〈6,7〉, 〈9,10〉〈9,10〉.
每次测试时间限定 4 秒
每次测试内存限定
5
12 兆字节
Dasha 是一名良好的门生，正在天下最好的数学学院学习。近来，一位秘密的陌生人将 n
个由小写拉丁字母 s1、s2、…、sn
构成的单词带到了学院。从那天起，Dasha 就不绝被噩梦折磨。
思量一对整数 〈i,j〉
(1≤i≤j≤n
)。噩梦是一个字符串，它为真：
它由毗连 sisj 得到
它的长度是奇数；
此中差异字母的数目恰恰是 2
5

单词中每个字母出现的次数是奇数。
比方，假如 si=
“abcdefg” 和 sj=
“ijklmnopqrstuvwxyz”，则对 〈i,j〉
会造成噩梦。
假如 Dasha 能数出噩梦的数目，她就不会再做噩梦了。噩梦太多了，以是 Dasha 必要你的资助。数一数差异噩梦的数目。
假如对应的对 〈i,j〉
差异，则称噩梦差异。假如 i1≠i2
或 j1≠j2
，则对 〈i1,j1〉
和 〈i2,j2〉
差异。
输入
第一行包罗一个整数 n
(1≤n≤2⋅10
5

) — 单词数。
接下来的 n
行包罗单词 s1,s2,…,sn
，由小写拉丁字母构成。
包管单词的总长度不凌驾
5
⋅106
。
输出
打印一个整数——差异噩梦的数目。
示例
输入副本
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz
输出副本

5

注意
在第一个测试中，噩梦是由〈1,3〉
、〈2,
5
〉
、〈3,4〉
、〈6,7〉
、〈9,10〉
构成的。
代码：
 

2. #include <iostream>
3. #include <vector>
4. #include <unordered_map>
5. #include <string>
6. using namespace std;
8. const long long MAX_N = 200010;
9. const long long FULL_MASK = (1 << 26) - 1;
11. unordered_map<long long, long long> count_map;
13. long long solve() {
14.     long long n;
15.     cin >> n;
17.     vector<string> strings(n + 1);
18.     vector<long long> bitmask(n + 1), all_chars(n + 1);
20.     for (long long i = 1; i <= n; ++i) {
21.         cin >> strings[i];
22.         for (char c : strings[i]) {
23.             bitmask[i] ^= (1 << (c - 'a'));
24.             all_chars[i] |= (1 << (c - 'a'));
25.         }
26.     }
28.     long long ans = 0;
30.     for (long long excluded_char = 0; excluded_char < 26; ++excluded_char) {
31.         count_map.clear();
33.         for (long long i = 1; i <= n; ++i) {
34.             if ((all_chars[i] >> excluded_char) & 1) continue;
36.             long long target = bitmask[i] ^ FULL_MASK ^ (1 << excluded_char);
37.             ans += count_map[target];
38.             count_map[bitmask[i]]++;
39.         }
40.     }
42.     return ans;
43. }
45. int main() {
46.     ios::sync_with_stdio(0);
47.     cin.tie(0);
49.     cout << solve() << endl;
51.     return 0;
52. }

复制代码