题解

思路

对单词 $s_i$，用 $d=0,1,\ldots,|s_i|-1$ 表示删除位置 $d$，用 $d=|s_i|$ 表示不删除。每个单词恰有 $|s_i|+1$ 个带位置编号的候选项；即使两个候选字符串相同，也必须分别计数。

子任务 1 枚举所有单词的候选项笛卡尔积，逐一检查整个序列。

子任务 2 设 $f_i(d)$ 为前 $i$ 个单词合法且第 $i$ 个单词选择 $d$ 的方案数。枚举相邻两行的候选对，只要前一个候选串不大于当前候选串就转移。

子任务 3 先显式构造每个单词的全部候选串并稳定排序。相邻两行都已排序后，用双指针维护前一行不大于当前候选串的 DP 前缀和，每个候选只进入前缀和一次。

满分算法不显式构造候选串。对于同一个原串的所有“删一位”结果，可以按连续相同字符段和删除位置在线性时间内得到字典序顺序；不删除的候选插在删除末位的候选之后。相邻两行仍使用双指针 DP。

比较两个带一个删除位置的候选串时，用双模滚动哈希计算任意候选前缀的哈希值。二分最长公共前缀后，只需比较第一个不同字符或候选长度，一次比较为 $O(\log L)$。

做法

1. 为每个原串预处理双模前缀哈希和删除候选的字典序顺序。
2. 第一行每个候选的方案数均为 $1$。
3. 从第二行开始，按当前候选的字典序扫描。
4. 双指针加入前一行所有不大于当前候选的状态，并维护方案数前缀和。
5. 最后一行全部状态求和并对 $10^9+7$ 取模。

复杂度

设所有单词总长度为 $S$，最大单词长度为 $L$。

子任务 1 的时间复杂度与 $\prod_i(|s_i|+1)$ 成正比，空间复杂度为 $O(S)$。

子任务 2 的时间复杂度为 $O\!\left(\sum_i |s_{i-1}||s_i|L\right)$，空间复杂度为 $O(SL)$。

子任务 3 的时间复杂度为 $O(SL\log L)$，空间复杂度为 $O(SL)$。

满分算法的时间复杂度为 $O(S\log L)$，空间复杂度为 $O(S)$。