CF1535F.String Distance

Suppose you are given two strings $a$ and $b$. You can apply the following operation any number of times: choose any contiguous substring of $a$ or $b$, and sort the characters in it in non-descending order. Let $f(a, b)$ the minimum number of operations you have to apply in order to make them equal (or $f(a, b) = 1337$ if it is impossible to make $a$ and $b$ equal using these operations).

For example:

• $f(\text{ab}, \text{ab}) = 0$;
• $f(\text{ba}, \text{ab}) = 1$ (in one operation, we can sort the whole first string);
• $f(\text{ebcda}, \text{ecdba}) = 1$ (in one operation, we can sort the substring of the second string starting from the $2$-nd character and ending with the $4$-th character);
• $f(\text{a}, \text{b}) = 1337$.

You are given $n$ strings $s_1, s_2, \dots, s_k$ having equal length. Calculate $\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$.

假设你有两个字符串 $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)$。

The first line contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the number of strings.

Then $n$ lines follow, each line contains one of the strings $s_i$, consisting of lowercase Latin letters. $|s_1| = |s_2| = \ldots = |s_n|$, and $n \cdot |s_1| \le 2 \cdot 10^5$. All these strings are pairwise distinct.

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$）—— 字符串的数量。

接下来有 $n$ 行，每行包含一个字符串 $s_i$，由小写拉丁字母组成。满足 $|s_1| = |s_2| = \ldots = |s_n|$，且 $n \cdot |s_1| \le 2 \cdot 10^5$。所有这些字符串两两互不相同。

Print one integer: $\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$.

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