题目背景

群星的尽头

题目描述

给定整数 $m$，定义字符集 $\Sigma$ 为前 $m$ 个小写字母，对于两个字符集为 $\Sigma$ 的串 $A, B$，定义 $f(A, B)$ 为如下问题的答案：存在一个有限大小的自动机 $M$，使得输入字符集为 $\Sigma$ 的，任意长度的字符串 $S$，都可以比较 $A$ 与 $B$ 在 $S$ 中的出现次数（返回 $<$, $=$, $>$）。如果存在，则 $f(A, B) = 1$，否则 $f(A, B) = 0$。给定 $n$ 个串 $s_1 \sim s_n$，你要求出 $\sum_{1 \leq i < j \leq n} f(s_i, s_j)$

在本题中，我们定义自动机 $M$ 是一个五元组 $(Q, \Sigma, \delta, q_0, F)$，其中 $Q$ 是状态集合，$\Sigma$ 是字符集，$\delta: Q \times \Sigma \to Q$ 是转移函数，$q_0$ 是起始状态，$F: Q \to \{<, =, >\}$ 表示每个状态对应的结果。定义这个自动机可以比较 $A$ 和 $B$ 在 $S$ 中的出现次数，当且仅当 $F(\delta(\dots\delta(\delta(q_0, S_1), S_2)\dots, S_{|S|})) \in \{<, =, >\}$ 为 $A$ 和 $B$ 在 $S$ 中出现次数的大小关系。

输入格式

第一行两个正整数 $n,m$。

接下来 $n$ 行，第 $i$ 行一个字符串 $s_i$，字符集为前 $m$ 个小写字母。

输出格式

输出一行一个整数，表示答案。

3 26
ct
ctt
cts

2

提示

样例 2~7

见附加文件中的 $\text{ex\_dfa2.in/out}$ 到 $\text{ex\_dfa7.in/out}$，第 $i+1$ 个样例满足子任务 $i$ 的限制。

数据范围

对于所有测试点，$2 \leq n \leq 10^6$, $N = \sum_{i=1}^{n} |s_i| \leq 10^6$, $2 \leq m \leq 26$。

本题开启合理的子任务依赖。