群星的尽头
题目大意
给定整数 $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\limits_{1\le i< j\le n}f(s_i,s_j)$
在本题中，我们定义自动机 $M$ 是一个五元组 $(Q,\Sigma,\delta,q_0,F)$，其中 $Q$ 是状态集合，$\Sigma$ 是字符集，$\delta: Q\times \Sigma\rightarrow Q$ 是转移函数，$q_0$ 是起始状态，$F:Q\rightarrow\{<,=,>\}$ 表示每个状态对应的结果。定义这个自动机可以比较 $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$ 个小写字母
输出格式
输出一行一个整数，表示答案。
样例输入 1
3 26 ct ctt cts
样例输出 1
2
样例 2~7
见附加文件中的 ex_dfa2.in/out 到 ex_dfa7.in/out，第 $i+1$ 个样例满足子任务 $i$ 的限制。
数据范围
对于所有测试点，$2\le n\le 10^6$，$N=\sum\limits_{i=1}^n|s_i|\le 10^6$，$2\le m\le 26$。
| 子任务编号 | $N\le $ | 特殊性质 | 分数 |
|---|---|---|---|
| $1$ | $1000$ | $\lvert s_i\rvert\le 3$，$m\le 3$ | $10$ |
| $2$ | $5000$ | $m=10$ | $10$ |
| $3$ | $10^6$ | $m=10$ | $20$ |
| $4$ | $500$ | 无 | $20$ |
| $5$ | $5000$ | 无 | $10$ |
| $6$ | $10^6$ | 无 | $30$ |
本题开启合理的子任务依赖