CF177G2 题解

__vector__ · 2025-10-08 08:58:34 · 题解

差不多就是对着题解复述了一遍，自己重新记录，没啥原创性，所以不申请题解了。

仅考虑单次询问怎么做。

令 F_i 表示 s 在 f_i 中的出现次数，G_i 表示 f_i 中有多少 s 跨越了 f_{i-1} 与 f_{i-2} 的交点。

那么，先预处理 F_1,F_2。

对于 i \ge 3，满足 F_i = F_{i-1}+F_{i-2}+G_i。

注意到 G_i 的取值仅取决于 f_{i-1} 的最后 |s|-1 个字符，以及 f_{i-2} 的最前的 |s|-1 个字符。

有两个性质：

• 若 |f_i| \ge |s|，那么 f_{i+1} 与 f_i 的前 |s| 个字符一致。
• 若 |f_i| \ge |s|，那么 f_{i+2} 与 f_i 的后 |s| 个字符一致。

令 x 表示最小的满足 |f_x| \ge |s| 的整数。

那么对于 \forall y \ge x+4，满足 G_y = G_{y-2}。

注意到 x 只有 O(\log |s|) 级别，可以暴力计算。

对于 \forall y \ge x+4，满足 F_y = F_{y-1}+F_{y-2}+G_{y} = F_{y-1}+F_{y-2}+G_{y-2}=F_{y-1}+F_{y-2}+(F_{y-2}-F_{y-3}-F_{y-4}) = F_{y-1}+2F_{y-2}-F_{y-3}-F_{y-4}。

然后暴力算出 F_x,F_{x+1},F_{x+2},F_{x+3}，用矩阵快速幂暴力递推接下来的就可以了。

对于多次询问怎么办？

暴力预处理前 35\sim 40 个 f_i，每次求 x 都二分，其他过程就都一样了。