P14356 [集训队互测 2025] 第二基地

群星的尽头

给定整数 $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$ 个小写字母。

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

### 样例 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$。 | 子任务编号 | $N \leq$ | 特殊性质 | 分数 | | :--: | :--: | :--: | :--: | | 1 | $1000$ | $\lvert s_i\rvert \leq 3$, $m \leq 3$ | $10$ | | 2 | $5000$ | $m = 10$ | $10$ | | 3 | $10^6$ | $m = 10$ | $20$ | | 4 | $500$ | 无 | $20$ | | 5 | $5000$ | 无 | $10$ | | 6 | $10^6$ | 无 | $30$ | 本题开启合理的子任务依赖。