Предположим, вам даны две строки $$$a$$$ и $$$b$$$. Вы можете применить следующую операцию любое количество раз: выбрать любую непрерывную подстроку $$$a$$$ или $$$b$$$ и отсортировать символы в ней в порядке неубывания. Пусть $$$f(a, b)$$$ — минимальное количество операций, которое необходимо применить, чтобы сделать строки равными (или $$$f(a, b) = 1337$$$, если невозможно сделать $$$a$$$ и $$$b$$$ равными с помощью этих операций).
Например:
Вам задано $$$n$$$ строк $$$s_1, s_2, \dots, s_k$$$ одинаковой длины. Вычислите $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.
Первая строка содержит одно целое число $$$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$$$. Все заданные строки попарно различны.
Выведите одно целое число: $$$\sum \limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} f(s_i, s_j)$$$.
4 zzz bac abc acb
4015
2 a b
1337
Название |
---|