题解 P8852：[JRKSJ R5] Concvssion

· · 题解

\text{Link}

## 题意 给定长度为 $n$ 的序列 $a_{1\sim n},b_{1\sim n}$，满足 $\forall i\in[1,n],a_i,b_i\in[1,n]$。 定义一次操作为，对 $\forall i\in[1,n]$ 执行 $b_i\gets a_{b_i}$。 你需要依次进行 $n$ 次操作，每次操作后求出 $\displaystyle\sum_{i=1}^n b_i$，对 $998244353$ 取模。 $n\le 3\times10^5$。 ## 题解 ### 子问题：$a_{1\sim n}$ 为排列 建出 $(i,a_i)$ 组成的图，可知是若干个环。 对于一个长为 $l$ 的环，我们可以用一次差卷积求出其对答案的第 $1\sim l$ 时刻的贡献，此后的贡献也是以 $l$ 为周期重复。 具体地，记 $p_i,c_i$ 分别为环上第 $i$ 个点的编号与环上第 $i$ 个点处关键点的数量，那么时刻 $k$ 的答案即为： $$f_k=\sum_{i=0}^{l-1} c_ip_{(i+k)\bmod l}$$ 此时将 $p$ 倍长，求出 $0\le k<l$ 的部分即可，当 $k\ge l$ 时，显然有 $f_k=f_{k-l}$。 当存在多个环时，还需要考虑将每个环的贡献求和。 由于环长只有 $O(\sqrt n)$ 种，我们可以将环长相同的答案加起来，并统一贡献至答案，时间复杂度 $O(n\sqrt n)$。 事实上也可以通过分治 FFT 做到 $O(n\log^2 n)$，不过不是必要的，在数据范围下也无法与按环长分类做出区分。 ### 子问题：$1\le a_i\le \max(i-1,1)

建出 (i,a_i) 组成的图，可知会形成一颗带一个自环的树。

一个位于 x 的关键点在执行 dep_x 次操作后会持续贡献 a_1，而两个深度相同的关键点 x,y 在同时到达它们的 \text{LCA} 后将始终贡献同一个值。

如果将 x 处的关键点移动到 y 处，我们只需要修正跳至它们的 \text{LCA} 之前这一段时刻的贡献。

我们对树进行长链剖分，对于 x 的子树，我们将其中在 \bm x 的非长链上的关键点移动至关键点上，其中修正贡献只需要做这条非长链长度的一次差卷积。

最终我们将所有关键点移动到了一条链上，而一条链上的贡献是好做的，可以通过进行前缀差分等方式解决。

时间复杂度 O(n\log n)。

原问题

当不存在特殊性质时，对于一个连通块，我们还需要处理一个环上挂有若干条链的情况。

此时，将环上的点依次写下，直到链的长度，我们就可以用类似的方式将链上的关键点移动到环上对应位置，并用差卷积修正时刻小于等于链长时的贡献。

进行完修正，我们就将所有关键点移动到了环上，问题变为只有环的子问题。

时间复杂度 O(n\log^2 n) 或 O(n\sqrt n)。

实现上述两个复杂度均可通过本题，存在能通过 n\le 10^5 部分的 O(n\sqrt n\log n) 算法。