题解

思路

总共有 $26^m$ 篇长度为 $m$ 的文章。直接统计“至少包含一个给定单词”的文章会重复计数，因此改为统计补集：完全不包含任何给定单词的文章数量，最后用总数减去它。

做法

子任务 1：枚举文本

当 $m\le 3$ 时，长度为 $m$ 的大写字母串至多有 $26^3$ 个。逐个枚举这些文本，再逐个检查是否包含任意已知单词即可。

时间复杂度可写为 $O(26^m\sum |s_i|)$，只适用于这一小规模层级。

子任务 2：AC 自动机与动态规划

把所有单词插入 Trie。一个 Trie 结点若对应某个单词结尾，就把它标记为危险结点。建立失配指针时，如果某个结点的失配指针指向危险结点，那么该结点也必须标记为危险：到达它时，当前文本的某个后缀已经是已知单词。

补全自动机的 26 个转移后，设 $f_{i,u}$ 表示已经生成了 $i$ 个字符、自动机位于非危险结点 $u$，且此前从未出现已知单词的方案数。初始只有 $f_{0,0}=1$。枚举下一个字母并沿自动机转移；若目标结点危险，就丢弃该方案，否则累加到下一层。

完成 $m$ 层后，所有非危险状态的方案数之和就是不可读文本数。答案为

每一步都只依赖上一层，因此可以滚动数组优化空间。

正确性说明

AC 自动机状态唯一表示当前文本后缀中、同时也是某个 Trie 前缀的最长部分。危险标记沿失配指针传播后，一个状态危险当且仅当当前文本已经以某个已知单词结尾。

动态规划只保留从未进入危险状态的路径，所以它与完全不包含任何已知单词的长度为 $m$ 的文本一一对应。全部文本被“可读”和“不可读”两个集合无重无漏地划分，因此用 $26^m$ 减去动态规划所得方案数，恰好得到至少包含一个已知单词的文本数量。

复杂度分析

记 Trie 结点数为 $S\le 1+\sum |s_i|$。建立自动机需要 $O(26S)$ 时间，动态规划需要 $O(26mS)$ 时间；空间复杂度为 $O(26S)$。