题解：AT_arc201_c [ARC201C] Prefix Covering

ylch · 2025-10-05 23:02:22 · 题解

引用名言：在提高组，看到字符串的相关题目，几乎可以闭眼建字典树，然后通过分析性质与建模将问题转化为树上 dp 问题。

题目感觉翻译得有点抽象，判断子集 X 合法的核心条件应该是：无论这个长为 10^{100} 的 AB 字符串 S 形态如何，都一定有一个 s_i \in X，满足 s_i 是 S 的前缀。

对于本题，首先考虑如果固定 k 怎么做。

思考题目中说的“任意长度为 10^{100} 的 AB 字符串”如果建成字典树就可以近似认为是一棵无限深度的完全二叉树，要满足“X 中有至少一个串是它的前缀”其实意思是把 X 中所有字符串放到树上后，所有根到叶子的路径上都有串结尾标记。

这其实可以抽象为：在一棵完全二叉树上，可以给其中 k 结点任意黑白染色，求最终每条根到叶子的路径上都至少有一个黑色点的方案数。

这样就是一个经典的树形 dp 问题了。设 f_i 表示以 i 为根的子树的合法染色方案数，c_i 表示以 i 为根的子树中可以染色的点个数（就是字符串结尾标记的个数），结点 i 的左右儿子分别为 l_i,r_i，则转移如下：

• 若 i 是某个字符串的结尾：f_i=f_{l_i} \times f_{r_i} + 2^{c_i-1}（两个加数分别为结点 i 不染黑/染黑的方案数）；

• 否则，f_i=f_{l_i} \times f_{r_i}。

考虑从 1 \sim n 枚举 k，每次把新的 S_k 加入字典树中，每次只需要修改与 S_k 有关的结点的 f 值即可，可以用数组记录并回溯（事实上有关结点是从新加入串的结尾结点到根结点这一条连续路径上的所有点）。

由于保证 \sum |S_i| \le 5 \times 10^5，所以这样不超时。

感觉整体思路还是很顺畅的~

提交记录