本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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$ 都二分，其他过程就都一样了。