CF1535F String Distance

给定两个字符串 $a$ 和 $b$，你可以对它们进行如下操作任意次：选择 $a$ 或 $b$ 的任意一个连续子串，并将该子串中的字符按非递减顺序排序。记 $f(a, b)$ 为将 $a$ 和 $b$ 变为相同所需的最小操作次数（如果无法通过上述操作使 $a$ 和 $b$ 相同，则 $f(a, b) = 1337$）。 例如： - $f(\text{ab}, \text{ab}) = 0$； - $f(\text{ba}, \text{ab}) = 1$（一次操作可以将第一个字符串整体排序）； - $f(\text{ebcda}, \text{ecdba}) = 1$（一次操作可以将第二个字符串从第 $2$ 个字符到第 $4$ 个字符的子串排序）； - $f(\text{a}, \text{b}) = 1337$。 现在给定 $n$ 个长度相同的字符串 $s_1, s_2, \dots, s_n$。计算 $\sum\limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$。

第一行包含一个整数 $n$（$1 \le n \le 2 \times 10^5$），表示字符串的数量。 接下来 $n$ 行，每行包含一个字符串 $s_i$，由小写拉丁字母组成。$|s_1| = |s_2| = \ldots = |s_n|$，且 $n \cdot |s_1| \le 2 \times 10^5$。所有字符串两两不同。

输出一个整数：$\sum\limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$。

由 ChatGPT 4.1 翻译