310214: CF1800F. Dasha and Nightmares
Memory Limit：512 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Dasha and Nightmares
题意翻译
给定 $n$ 和 $n$ 个字符串 $s_i$。 问有多少对不同的 $\langle i,j\rangle(1\leq i\leq j\leq n)$，使得 $s_i$ 和 $s_j$ 拼接后的字符串满足下列条件： - 长度为奇数 - 恰好出现 $25$ 个字母 - 每个字母出现次数为奇数 $1\leq n\leq2\times10^5,\sum\limits_{i=1}^n \left\vert s_i\right\vert\leq5\times10^6$ by @Larryyu题目描述
Dasha, an excellent student, is studying at the best mathematical lyceum in the country. Recently, a mysterious stranger brought $ n $ words consisting of small latin letters $ s_1, s_2, \ldots, s_n $ to the lyceum. Since that day, Dasha has been tormented by nightmares. Consider some pair of integers $ \langle i, j \rangle $ ( $ 1 \le i \le j \le n $ ). A nightmare is a string for which it is true: - It is obtained by concatenation $ s_{i}s_{j} $ ; - Its length is odd; - The number of different letters in it is exactly $ 25 $ ; - The number of occurrences of each letter that is in the word is odd. For example, if $ s_i= $ "abcdefg" and $ s_j= $ "ijklmnopqrstuvwxyz", the pair $ \langle i, j \rangle $ 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 $ \langle i, j \rangle $ are different. The pairs $ \langle i_1, j_1 \rangle $ and $ \langle i_2, j_2 \rangle $ are called different if $ i_1 \neq i_2 $ or $ j_1 \neq j_2 $ .输入输出格式
输入格式
The first line contains a single integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the number of words. The following $ n $ lines contain the words $ s_1, s_2, \ldots, s_n $ , consisting of small latin letters. It is guaranteed that the total length of words does not exceed $ 5 \cdot 10^6 $ .
输出格式
Print a single integer — the number of different nightmares.
输入输出样例
输入样例 #1
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz输出样例 #1
5说明
In the first test, nightmares are created by pairs $ \langle 1, 3 \rangle $ , $ \langle 2, 5 \rangle $ , $ \langle 3, 4 \rangle $ , $ \langle 6, 7 \rangle $ , $ \langle 9, 10 \rangle $ .Input
题意翻译
给定 $n$ 和 $n$ 个字符串 $s_i$。 问有多少对不同的 $\langle i,j\rangle(1\leq i\leq j\leq n)$，使得 $s_i$ 和 $s_j$ 拼接后的字符串满足下列条件： - 长度为奇数 - 恰好出现 $25$ 个字母 - 每个字母出现次数为奇数 $1\leq n\leq2\times10^5,\sum\limits_{i=1}^n \left\vert s_i\right\vert\leq5\times10^6$ by @LarryyuOutput
**题意翻译**
给定 $n$ 个字符串 $s_i$。
问有多少对不同的 $\langle i,j\rangle (1\leq i\leq j\leq n)$，使得 $s_i$ 和 $s_j$ 拼接后的字符串满足下列条件：
- 长度为奇数
- 恰好出现 $25$ 个字母
- 每个字母出现次数为奇数
其中 $1\leq n\leq2\times10^5, \sum\limits_{i=1}^n \left\vert s_i\right\vert\leq5\times10^6$
**题目描述**
Dasha是一个优秀的学生，正在国家最好的数学高中学习。最近，一个神秘的陌生人带来了 $n$ 个由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。从那天起，Dasha就开始做噩梦。
考虑一对整数 $\langle i, j \rangle (1 \le i \le j \le n)$。如果通过拼接 $s_{i}s_{j}$ 形成的字符串满足以下条件，则称之为噩梦：
- 它的长度是奇数；
- 不同的字母数正好是 $25$ 个；
- 在这个字符串中出现的每个字母的次数是奇数。
例如，如果 $s_i= "abcdefg"$ 和 $s_j= "ijklmnopqrstuvwxyz"$，那么这对 $\langle i, j \rangle$ 就会形成一个噩梦。
如果Dasha能计算出噩梦的数量，她就会停止做噩梦。因为噩梦太多，Dasha需要你的帮助。计算不同噩梦的数量。
如果对应的 $\langle i, j \rangle$ 不同，那么这些噩梦就被称为不同的。如果 $i_1 \neq i_2$ 或 $j_1 \neq j_2$，那么 $\langle i_1, j_1 \rangle$ 和 $\langle i_2, j_2 \rangle$ 就被称为不同的。
**输入输出格式**
**输入格式**
- 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$) — 单词的数量。
- 接下来的 $n$ 行包含由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。
- 保证单词的总长度不超过 $5 \times 10^6$。
**输出格式**
- 打印一个整数 — 不同噩梦的数量。
**输入输出样例**
**输入样例 #1**
```
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz
```
**输出样例 #1**
```
5
```
**说明**
在第一个测试中，噩梦是由以下几对形成的：$\langle 1, 3 \rangle, \langle 2, 5 \rangle, \langle 3, 4 \rangle, \langle 6, 7 \rangle, \langle 9, 10 \rangle$。**题意翻译** 给定 $n$ 个字符串 $s_i$。 问有多少对不同的 $\langle i,j\rangle (1\leq i\leq j\leq n)$，使得 $s_i$ 和 $s_j$ 拼接后的字符串满足下列条件： - 长度为奇数 - 恰好出现 $25$ 个字母 - 每个字母出现次数为奇数 其中 $1\leq n\leq2\times10^5, \sum\limits_{i=1}^n \left\vert s_i\right\vert\leq5\times10^6$ **题目描述** Dasha是一个优秀的学生，正在国家最好的数学高中学习。最近，一个神秘的陌生人带来了 $n$ 个由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。从那天起，Dasha就开始做噩梦。 考虑一对整数 $\langle i, j \rangle (1 \le i \le j \le n)$。如果通过拼接 $s_{i}s_{j}$ 形成的字符串满足以下条件，则称之为噩梦： - 它的长度是奇数； - 不同的字母数正好是 $25$ 个； - 在这个字符串中出现的每个字母的次数是奇数。 例如，如果 $s_i= "abcdefg"$ 和 $s_j= "ijklmnopqrstuvwxyz"$，那么这对 $\langle i, j \rangle$ 就会形成一个噩梦。 如果Dasha能计算出噩梦的数量，她就会停止做噩梦。因为噩梦太多，Dasha需要你的帮助。计算不同噩梦的数量。 如果对应的 $\langle i, j \rangle$ 不同，那么这些噩梦就被称为不同的。如果 $i_1 \neq i_2$ 或 $j_1 \neq j_2$，那么 $\langle i_1, j_1 \rangle$ 和 $\langle i_2, j_2 \rangle$ 就被称为不同的。 **输入输出格式** **输入格式** - 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$) — 单词的数量。 - 接下来的 $n$ 行包含由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。 - 保证单词的总长度不超过 $5 \times 10^6$。 **输出格式** - 打印一个整数 — 不同噩梦的数量。 **输入输出样例** **输入样例 #1** ``` 10 ftl abcdefghijklmnopqrstuvwxy abcdeffghijkllmnopqrsttuvwxy ffftl aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy thedevid bcdefghhiiiijklmnopqrsuwxyz gorillasilverback abcdefg ijklmnopqrstuvwxyz ``` **输出样例 #1** ``` 5 ``` **说明** 在第一个测试中，噩梦是由以下几对形成的：$\langle 1, 3 \rangle, \langle 2, 5 \rangle, \langle 3, 4 \rangle, \langle 6, 7 \rangle, \langle 9, 10 \rangle$。
给定 $n$ 个字符串 $s_i$。
问有多少对不同的 $\langle i,j\rangle (1\leq i\leq j\leq n)$，使得 $s_i$ 和 $s_j$ 拼接后的字符串满足下列条件：
- 长度为奇数
- 恰好出现 $25$ 个字母
- 每个字母出现次数为奇数
其中 $1\leq n\leq2\times10^5, \sum\limits_{i=1}^n \left\vert s_i\right\vert\leq5\times10^6$
**题目描述**
Dasha是一个优秀的学生，正在国家最好的数学高中学习。最近，一个神秘的陌生人带来了 $n$ 个由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。从那天起，Dasha就开始做噩梦。
考虑一对整数 $\langle i, j \rangle (1 \le i \le j \le n)$。如果通过拼接 $s_{i}s_{j}$ 形成的字符串满足以下条件，则称之为噩梦：
- 它的长度是奇数；
- 不同的字母数正好是 $25$ 个；
- 在这个字符串中出现的每个字母的次数是奇数。
例如，如果 $s_i= "abcdefg"$ 和 $s_j= "ijklmnopqrstuvwxyz"$，那么这对 $\langle i, j \rangle$ 就会形成一个噩梦。
如果Dasha能计算出噩梦的数量，她就会停止做噩梦。因为噩梦太多，Dasha需要你的帮助。计算不同噩梦的数量。
如果对应的 $\langle i, j \rangle$ 不同，那么这些噩梦就被称为不同的。如果 $i_1 \neq i_2$ 或 $j_1 \neq j_2$，那么 $\langle i_1, j_1 \rangle$ 和 $\langle i_2, j_2 \rangle$ 就被称为不同的。
**输入输出格式**
**输入格式**
- 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$) — 单词的数量。
- 接下来的 $n$ 行包含由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。
- 保证单词的总长度不超过 $5 \times 10^6$。
**输出格式**
- 打印一个整数 — 不同噩梦的数量。
**输入输出样例**
**输入样例 #1**
```
10
ftl
abcdefghijklmnopqrstuvwxy
abcdeffghijkllmnopqrsttuvwxy
ffftl
aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy
thedevid
bcdefghhiiiijklmnopqrsuwxyz
gorillasilverback
abcdefg
ijklmnopqrstuvwxyz
```
**输出样例 #1**
```
5
```
**说明**
在第一个测试中，噩梦是由以下几对形成的：$\langle 1, 3 \rangle, \langle 2, 5 \rangle, \langle 3, 4 \rangle, \langle 6, 7 \rangle, \langle 9, 10 \rangle$。**题意翻译** 给定 $n$ 个字符串 $s_i$。 问有多少对不同的 $\langle i,j\rangle (1\leq i\leq j\leq n)$，使得 $s_i$ 和 $s_j$ 拼接后的字符串满足下列条件： - 长度为奇数 - 恰好出现 $25$ 个字母 - 每个字母出现次数为奇数 其中 $1\leq n\leq2\times10^5, \sum\limits_{i=1}^n \left\vert s_i\right\vert\leq5\times10^6$ **题目描述** Dasha是一个优秀的学生，正在国家最好的数学高中学习。最近，一个神秘的陌生人带来了 $n$ 个由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。从那天起，Dasha就开始做噩梦。 考虑一对整数 $\langle i, j \rangle (1 \le i \le j \le n)$。如果通过拼接 $s_{i}s_{j}$ 形成的字符串满足以下条件，则称之为噩梦： - 它的长度是奇数； - 不同的字母数正好是 $25$ 个； - 在这个字符串中出现的每个字母的次数是奇数。 例如，如果 $s_i= "abcdefg"$ 和 $s_j= "ijklmnopqrstuvwxyz"$，那么这对 $\langle i, j \rangle$ 就会形成一个噩梦。 如果Dasha能计算出噩梦的数量，她就会停止做噩梦。因为噩梦太多，Dasha需要你的帮助。计算不同噩梦的数量。 如果对应的 $\langle i, j \rangle$ 不同，那么这些噩梦就被称为不同的。如果 $i_1 \neq i_2$ 或 $j_1 \neq j_2$，那么 $\langle i_1, j_1 \rangle$ 和 $\langle i_2, j_2 \rangle$ 就被称为不同的。 **输入输出格式** **输入格式** - 第一行包含一个整数 $n$ ($1 \le n \le 2 \times 10^5$) — 单词的数量。 - 接下来的 $n$ 行包含由小写拉丁字母组成的单词 $s_1, s_2, \ldots, s_n$。 - 保证单词的总长度不超过 $5 \times 10^6$。 **输出格式** - 打印一个整数 — 不同噩梦的数量。 **输入输出样例** **输入样例 #1** ``` 10 ftl abcdefghijklmnopqrstuvwxy abcdeffghijkllmnopqrsttuvwxy ffftl aabbccddeeffgghhiijjkkllmmnnooppqqrrssttuuvvwwxxyy thedevid bcdefghhiiiijklmnopqrsuwxyz gorillasilverback abcdefg ijklmnopqrstuvwxyz ``` **输出样例 #1** ``` 5 ``` **说明** 在第一个测试中，噩梦是由以下几对形成的：$\langle 1, 3 \rangle, \langle 2, 5 \rangle, \langle 3, 4 \rangle, \langle 6, 7 \rangle, \langle 9, 10 \rangle$。