题解

思路

因为每个数字至少为 $1$，数字和为 $x$ 的字符串长度至多为 $x$。可以 DFS 枚举所有由 $1$ 到 $9$ 组成、数字和恰为 $x$ 的字符串，再检查它的每个真子串：若某个真子串的数字和整除 $x$，该字符串就不是 $x$-prime。$x\le20$ 时留下的模式串数量很少。

子任务 1 枚举原串的所有子序列，直接判断其中是否出现任一 $x$-prime 模式，取删除数最小值。

子任务 2 收集所有模式串的真前缀。状态是当前保留串的最长后缀，并且该后缀是某个模式串的前缀。保留一个字符后，枚举后缀找到新状态；若形成完整模式则禁止。删除字符则状态不变且代价加一。

满分算法把所有 $x$-prime 模式插入 Aho-Corasick 自动机。失败指针上的终止标记向下传播后，只要自动机状态不是终止状态，当前保留串就不含任何禁用模式。

设 $dp_v$ 为处理当前前缀后自动机处于状态 $v$ 的最少删除数。对下一个字符有两种转移：

• 删除它：仍在 $v$，代价加一；
• 保留它：沿自动机转移，若目标状态不是终止状态则代价不变。

最终所有状态的最小值就是答案。

做法

1. DFS 枚举所有数字和为 $x$ 的字符串并筛出 $x$-prime 模式。
2. 把模式串插入 Aho-Corasick 自动机，构建失败指针和完整转移表。
3. 传播失败链上的终止标记。
4. 扫描原串，用滚动数组进行“删除或保留”的最短路式 DP。
5. 输出最后一层状态的最小值。

复杂度

子任务 1 的时间复杂度为 $O(2^{|s|}|s|x^2)$，空间复杂度为 $O(|s|)$。

子任务 2 设显式前缀状态数为 $P$，时间复杂度为 $O(|s|Px)$，空间复杂度为 $O(P)$。

满分算法设 Aho-Corasick 自动机节点数为 $A$，时间复杂度为 $O(|s|A)$，空间复杂度为 $O(A)$。