CF1902E Collapsing Strings

给定 $n$ 个字符串 $s_1, s_2, \dots, s_n$，每个字符串均由小写拉丁字母组成。记 $|x|$ 为字符串 $x$ 的长度。 定义两个字符串 $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|})$，其中 $s_{l,r}$ 表示字符串 $s$ 的第 $l$ 个字母到第 $r$ 个字母组成的子串； - 否则，$C(a, b) = a + b$，即将两个字符串直接拼接。 请计算 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$。

第一行包含一个整数 $n$（$1 \le n \le 10^6$）。 接下来的 $n$ 行，每行包含一个字符串 $s_i$（$1 \le |s_i| \le 10^6$），均由小写拉丁字母组成。 所有字符串的总长度不超过 $10^6$。

输出一个整数，表示 $\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$。

由 ChatGPT 4.1 翻译