自动搬运

查看原文

来自洛谷，原作者为

	Ratio_Y 善于隐藏自己的精明，才称得上是最大的精明。——拉罗什福科《道德箴言录》||主页跳转https://www.luogu.com.cn/paste/gaajjpsj

搬运于2025-08-24 23:05:54，当前版本为作者最后更新于2024-11-11 19:30:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

是题解区目前唯一的 $\mathcal{O(n)}$ 做法！

思路

我们先不管扩展后的串，考虑只将字符在原串中的位置连边，容易发现形成了一个内向基环树森林。而我们要求的，就是求出给定的点在树上走 $k$ 条边后路径的总长加上原来下标对 $10^9+7$ 取模的值。

先考虑一个点如果最后会落在环上怎么做。我们可以提前 $\mathcal{O(n)}$ 处理出每个环外点到环的距离和步数，以及连向环的哪个点；同时环的大小、长度也是可以处理出来的。这样我们就可以将原来的跳跃轨迹砍成三段：走到环 $\rightarrow$ 走完整环 $\rightarrow$ 走部分环。前两段求法比较平凡，对于最后一段，我们可以在环上断边处理出出前缀和，同样可以实现 $\mathcal{O(1)}$ 查询。

再考虑如果没走到环上怎么办。如果依然倍增处理到环距离那么和 $\mathcal{O(n\log n)}$ 的做法相比就没有优势了，因此我们考虑另一种处理到 $k$ 级祖先距离的方法：离线后将询问挂在点上做。实现上，我们反向建一棵外向基环树，从环上点向外 dfs，此时每个深度一定只对应一个点，容易根据当前点的深度差分求出其到 $k$ 级祖先的距离。

那么就做完了！理论复杂度 $\mathcal{O(n)}$，可能带有较大的常数。

8.2k 的代码

完结撒花~

Welcome to my blog