题解

思路

长度为 $m$ 的单词有 $m+1$ 个决策：删除位置 $0,1,\ldots,m-1$，或不删除。令一个决策产生的字符串为“变体”。需要统计从每个单词选一个变体后，整个序列非递减的方案数。

做法

子任务 1：搜索全部决策

按单词顺序递归枚举变体。如果当前变体不小于前一个变体就继续搜索。到达末尾时得到一个方案。复杂度为 $O((L+1)^n\cdot nL)$。

子任务 2：朴素动态规划

令 $dp_{i,x}$ 表示第 $i$ 个单词选择变体 $x$ 的方案数。枚举相邻单词的全部变体对，若前一变体不大于当前变体，就转移：

$$dp_{i,y}=\sum_{x:\,v_{i-1,x}\le v_{i,y}}dp_{i-1,x}.$$

直接构造并比较字符串即可。若单词最大长度为 $L$，复杂度为 $O(nL^3)$。

满分算法：线性排序、双指针与常数次 LCP

同一单词的所有变体可以在线性时间排成字典序。比较“删除 $x$”与“删除 $y$”时，第一个差异只会出现在两个删除位置之间。设 next[x] 为 $x$ 右侧第一个与 $s_x$ 不同的位置：若该字符不大于 $s_x$，删除 $x$ 的变体应放入序列左端，否则放入右端；从左到右处理所有位置即可得到有序变体。删除末字符的变体是真正原串的前缀，因此“不删除”紧随其后。

对相邻两个原单词 $a,b$，预处理三条对角线的最长公共前缀：

• $a_i$ 与 $b_i$ 对齐；
• $a_{i+1}$ 与 $b_i$ 对齐；
• $a_i$ 与 $b_{i+1}$ 对齐。

比较两个各删除至多一个字符的变体时，删除位置之前使用第一条对角线；只跳过一边后使用第二或第三条；两边都跳过后又回到第一条。因此一次比较只需常数次查询，时间为 $O(1)$，且完全确定性。

把相邻两层变体分别按字典序排列。用双指针扫描当前层；前一层中所有不大于当前变体的状态形成前缀，维护此前缀的 $dp$ 和即可完成转移。每层耗时与两个单词长度之和成正比。

另用两组模数的滚动哈希和二分 LCP 实现独立复核，与确定性三对角线实现及小规模朴素 DP 交叉验证。

复杂度

枚举算法为指数级；朴素 DP 为 $O(nL^3)$。满分确定性算法的时间复杂度为 $O(S)$，空间复杂度为 $O(S)$，其中 $S$ 是所有单词长度之和。独立双哈希复核为 $O(S\log L)$。

正确性证明

朴素 DP 的状态完整记录当前单词的删除决策，转移恰好检查相邻字典序约束，所以归纳可知它无重无漏地统计全部合法方案。

线性变体排序依据删除位置后第一个不同字符决定两变体的首次差异；相同字符段内的删除结果相等，端点插入顺序不影响非递减性。因此得到的序列按字典序非递减。三条 LCP 对角线覆盖“尚未删除、仅前词删除、仅后词删除、两词均已删除”四个阶段，故常数次比较结果与显式构造字符串完全相同。双指针加入的恰是前一层所有不大于当前变体的状态，其前缀和等于朴素转移式，所以优化后的 DP 与朴素 DP 等价，答案正确。