题解：P15013 FUN!!

nbhs23a28 · 2026-01-26 13:45:58 · 题解

非常好月赛 T2，使我大脑旋转程度胜过 T4。

提供一种不用连边故没有基环树繁琐操作的做法，除 \gcd 瓶颈其余可做到线性。

首先由于每个点恰连一条出边，很难不注意到按题目所述最终会连成内向基环树森林。考察结构，我们发现，没有在 a_i 序列出现过的节点一定不在任意一棵基环树的环上，反之亦然，因为 n+k 步后到达的点一定在环上且任意环上一点总有环上一点能 n+k 步到达。由于这些环外的点可以任意连，即若对于环上点有解，总能找到一种连法使得所有点有解，故我们完全可以忽略这些点。于是我们只记录环上的点，问题简化为能否构建若干个环，使得均符合条件。

考虑接下来怎么做。很难不想到我们可以根据输入构建一个 n+k 步到达环（以下简称虚环），如果这些环有交，直接判无解（一个环上不可能有两个不同点走相同步到达同一点）。接下来，不妨先处理这些虚环各自在一个环上产生，那么对于有 m 个不同节点的虚环，当且仅当 m 与 n+k 互质有解，否则由裴蜀定理与起点距离不能被 \gcd (m,n+k) 整除的点永远到不了，矛盾。

接下来只需考虑多个虚环来自于同一环情形，此时环上节点数与 n+k 不互质。由于同一环上任意两点跳的步数相同，故该环一定由若干个节点数相同的虚环拼接而成。于是我们将节点数相同的虚环打包处理，暴力枚举一个环包含多少个虚环，记虚环节点数为 a，拼接的虚环环数为 b，则要使 (n+k)/b 与 a 互质（显然要能整除），这个 b 显然可表示为一个 b_0 的倍数，故只要该节点数虚环个数不能被 b_0 整除，即无解。b_0 可以直接暴力找，时间复杂度仍然是线性乘上 \gcd 的复杂度的，本题得解。代码不放了。