310870: CF1902E. Collapsing Strings
Memory Limit：256 MB
Time Limit：2 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
E. Collapsing Stringstime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
You are given $n$ strings $s_1, s_2, \dots, s_n$, consisting of lowercase Latin letters. Let $|x|$ be the length of string $x$.
Let a collapse $C(a, b)$ of two strings $a$ and $b$ be the following operation:
- if $a$ is empty, $C(a, b) = b$;
- if $b$ is empty, $C(a, b) = a$;
- if the last letter of $a$ is equal to the first letter of $b$, then $C(a, b) = C(a_{1,|a|-1}, b_{2,|b|})$, where $s_{l,r}$ is the substring of $s$ from the $l$-th letter to the $r$-th one;
- otherwise, $C(a, b) = a + b$, i. e. the concatenation of two strings.
Calculate $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$.
InputThe first line contains a single integer $n$ ($1 \le n \le 10^6$).
Each of the next $n$ lines contains a string $s_i$ ($1 \le |s_i| \le 10^6$), consisting of lowercase Latin letters.
The total length of the strings doesn't exceed $10^6$.
OutputPrint a single integer — $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$.
ExamplesInput3 aba ab baOutput
20Input
5 abab babx xab xba babOutput
126
Output
题目大意：
这个题目是关于字符串的“塌缩”操作。给定n个由小写拉丁字母组成的字符串s1, s2, …, sn。定义两个字符串a和b的塌缩操作C(a, b)如下：
- 如果a为空，则C(a, b) = b；
- 如果b为空，则C(a, b) = a；
- 如果a的最后一个字母与b的第一个字母相同，则C(a, b) = C(a[1,|a|-1], b[2,|b|])，这里a[l,r]表示从a的第l个字母到第r个字母的子串；
- 否则，C(a, b) = a + b，即两个字符串的连接。
计算∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|。
输入输出数据格式：
输入：
- 第一行包含一个整数n（1 ≤ n ≤ 10^6）。
- 接下来的n行，每行包含一个字符串si（1 ≤ |si| ≤ 10^6），由小写拉丁字母组成。
- 字符串的总长度不超过10^6。
输出：
- 输出一个整数，即∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|的值。
示例：
输入：
3
aba
ab
ba
输出：
20
输入：
5
abab
babx
xab
xba
bab
输出：
126题目大意： 这个题目是关于字符串的“塌缩”操作。给定n个由小写拉丁字母组成的字符串s1, s2, …, sn。定义两个字符串a和b的塌缩操作C(a, b)如下： - 如果a为空，则C(a, b) = b； - 如果b为空，则C(a, b) = a； - 如果a的最后一个字母与b的第一个字母相同，则C(a, b) = C(a[1,|a|-1], b[2,|b|])，这里a[l,r]表示从a的第l个字母到第r个字母的子串； - 否则，C(a, b) = a + b，即两个字符串的连接。 计算∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|。 输入输出数据格式： 输入： - 第一行包含一个整数n（1 ≤ n ≤ 10^6）。 - 接下来的n行，每行包含一个字符串si（1 ≤ |si| ≤ 10^6），由小写拉丁字母组成。 - 字符串的总长度不超过10^6。 输出： - 输出一个整数，即∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|的值。 示例： 输入： 3 aba ab ba 输出： 20 输入： 5 abab babx xab xba bab 输出： 126
这个题目是关于字符串的“塌缩”操作。给定n个由小写拉丁字母组成的字符串s1, s2, …, sn。定义两个字符串a和b的塌缩操作C(a, b)如下：
- 如果a为空，则C(a, b) = b；
- 如果b为空，则C(a, b) = a；
- 如果a的最后一个字母与b的第一个字母相同，则C(a, b) = C(a[1,|a|-1], b[2,|b|])，这里a[l,r]表示从a的第l个字母到第r个字母的子串；
- 否则，C(a, b) = a + b，即两个字符串的连接。
计算∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|。
输入输出数据格式：
输入：
- 第一行包含一个整数n（1 ≤ n ≤ 10^6）。
- 接下来的n行，每行包含一个字符串si（1 ≤ |si| ≤ 10^6），由小写拉丁字母组成。
- 字符串的总长度不超过10^6。
输出：
- 输出一个整数，即∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|的值。
示例：
输入：
3
aba
ab
ba
输出：
20
输入：
5
abab
babx
xab
xba
bab
输出：
126题目大意： 这个题目是关于字符串的“塌缩”操作。给定n个由小写拉丁字母组成的字符串s1, s2, …, sn。定义两个字符串a和b的塌缩操作C(a, b)如下： - 如果a为空，则C(a, b) = b； - 如果b为空，则C(a, b) = a； - 如果a的最后一个字母与b的第一个字母相同，则C(a, b) = C(a[1,|a|-1], b[2,|b|])，这里a[l,r]表示从a的第l个字母到第r个字母的子串； - 否则，C(a, b) = a + b，即两个字符串的连接。 计算∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|。 输入输出数据格式： 输入： - 第一行包含一个整数n（1 ≤ n ≤ 10^6）。 - 接下来的n行，每行包含一个字符串si（1 ≤ |si| ≤ 10^6），由小写拉丁字母组成。 - 字符串的总长度不超过10^6。 输出： - 输出一个整数，即∑(i=1 to n) ∑(j=1 to n) |C(si, sj)|的值。 示例： 输入： 3 aba ab ba 输出： 20 输入： 5 abab babx xab xba bab 输出： 126