题目大意

给定长度 $N$ 和 $M$ 条约束，每条约束形如 $T_{A_j} \le T_{B_j}$，其中 $T_i$ 表示原串 $S$ 删去第 $i$ 个字符后得到的字符串。求满足所有约束的、由小写字母构成的字符串 $S$ 的数量，对 $10^9+7$ 取模。

$N, M \le 5\times 10^5$。

关键思路

1. 转化约束条件

考虑两个字符串 $T_u$ 和 $T_v$ 的字典序比较（假设 $u < v$）：

• $T_u = S[1..u-1] + S[u+1..N]$
• $T_v = S[1..v-1] + S[v+1..N]$

比较过程：

• 先比较 $S[1]$ 与 $S[1]$（相同）
• 继续比较，直到位置 $u-1$ 之前都相同
• 在位置 $u$，$T_u$ 的下一个字符是 $S[u+1]$，$T_v$ 的下一个字符是 $S[u]$
• 如果 $S[u+1] \neq S[u]$，这里就能分出大小
• 如果相等，继续比较，直到位置 $v-1$ 时，$T_u$ 的下一个字符是 $S[v]$，$T_v$ 的下一个字符是 $S[v+1]$
• 如果这里还相等，那么后面就完全相同

重要结论：
$T_u \le T_v$ 的约束实际上只与 $S$ 中少数几个位置的字符相对大小有关，具体来说与位置 $u, u+1, v, v+1$ 等相关。

2. 建立字符间关系

通过分析可以发现，每条约束 $T_{A_j} \le T_{B_j}$ 实际上转化为 $S$ 中某些相邻位置字符的偏序关系：

• 如果 $u < v$，约束等价于：
  要么 $S[u] = S[u+1]$，要么在第一个不同位置满足 $S[u+1] < S[u]$ 的情况不会发生（实际上需要细致分类讨论）
• 更精确地，可以推导出：约束 $T_u \le T_v$ 等价于 $S$ 满足某个关于 $S[u], S[u+1], ..., S[v], S[v+1]$ 的不等式条件

最终模型：每条约束会在字符序列上建立一些 相邻字符的相对大小关系。

3. 图论建模

将 26 个小写字母看作值域，我们在 $N$ 个位置之间建立有向边表示偏序关系：

• 如果位置 $i$ 的字符必须 ≤ 位置 $j$ 的字符，则连边 $i \to j$
• 特别地，相邻位置可能被要求相等或不等

但直接对 $N$ 个位置建图，每个位置有 26 种可能，状态数太大。

4. 关键观察

通过进一步分析，可以发现所有约束实际上只影响相邻字符的关系。也就是说，我们只需要考虑 $S[i]$ 和 $S[i+1]$ 之间的关系。

最终问题转化为：确定每个相邻对 $(S[i], S[i+1])$ 是 $<$、$=$ 还是 $>$，并且满足所有约束推导出的相邻字符关系。

5. 动态规划解法

设 $dp[i][c]$ 表示考虑前 $i$ 个字符，且第 $i$ 个字符为 $c$ 时的方案数。

转移时，枚举下一个字符 $c'$，检查 $(c, c')$ 这个相邻对是否满足所有涉及位置 $i$ 和 $i+1$ 的约束。

优化：
由于 $N$ 很大，直接 $O(N \cdot 26^2)$ 不可行。但我们可以预处理出每个位置 $i$ 的字符 $c$ 可以转移到哪些 $c'$，这个转移图对于所有 $i$ 是相同的（除了边界情况）。

实际上，经过约束推导后，可能的转移边会大大减少。

6. 最终算法框架

1. 解析所有约束，推导出相邻字符间允许的关系（<, =, >）
2. 建立 26 个字母之间的转移图
3. 用动态规划计算方案数：
   • 初始：$dp[1][c] = 1$ 对所有字母 $c$
   • 转移：$dp[i+1][c'] += dp[i][c]$ 如果 $(c, c')$ 允许
   • 答案：$\sum_c dp[N][c]$

时间复杂度：$O(N \cdot 26 + M)$

代码实现要点

• 使用邻接表存储约束
• 预处理每个位置受哪些约束影响
• 推导出全局的字符转移矩阵
• 滚动数组优化 DP 空间

总结

这道题的核心难点在于 将复杂的字符串字典序约束转化为简单的相邻字符关系，一旦完成这个转化，问题就变成了经典的计数 DP。

思维难度很高，但算法实现相对简洁，体现了 JOISC 题目「思维重于编码」的特点。

难度评价：8.5/10（省选/NOI- 难度）
关键技能：问题转化、图论建模、动态规划、组合计数