题解 CF1400F x-prime Substrings

Alex_Wei · 2021-03-13 10:48:13 · 题解

• Update on 2022.11.7：重写题解。

*CF1400F x-prime Substrings

不错的题目。

题目限制出现 “不能出现某字符串”，首先考虑将所有非法字符串拎出来建 ACAM。因为 x 的真因数均不能作为数码，所以 1 不可以作为数码，这样一来非法字符串的数量就很少了。爆搜发现对于 x = 19，建出的字典树总大小为 S = 4852，可以接受。

因此，设 f_{i, j} 表示将 s[1, i] 删去若干字符后合法，且在 ACAM 上匹配到状态 j 的最小代价。枚举是否删去当前字符转移即可。时间复杂度 \mathcal{O}(|s|S)。代码。