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