P15013 FUN!! 题解

· · 题解

可能更好的阅读体验

题意简述

给出长度为 n 的数组 a 以及非负整数 k，你需要判断是否存在一张有向图满足以下要求：

此题多测，对所有数据，保证 1 \le a_i \le n \le 5 \times 10^5，0 \le k \le 10^9，1 \le \sum n \le 3 \times 10^6。

算法 1

爆搜。

时间复杂度：\mathcal O(n^{n + 1})。

注意到 k 可以对 60（1 到 n 的 LCM）取模，取模之后直接写 \mathcal O(n^{n + 1}(n + k)) 适当剪枝也能过。

期望得分：15。

算法 2

所求的图是一片内向基环森林。那么所有点在走 n + k 步后都会走到其所在的内向基环树的环上。

如果 i \to a_i 连边建一张新图，这张新图所有不在环上的点都要连到环上的点，否则方案不合法。

不在环上的 i 的要求是一定可以满足的，只需要确定了所求的图中环的形态就可以找到环上 a_i 往后退 n + k - 1 步的点 b_i，把 i 连向 b_i 即可。接下来我们忽略这些点。

于是新图变成了一些环，我们只需要判断环长的可重集是否合法即可。所求的图显然也应该是一些环，所求的图的一个长度为 d 的环会在新图上会被拆分为 \gcd(d, n + k) 个大小为 \frac d{\gcd(d, n + k)} 的环。

开 n 个完全背包，枚举 d，把 \gcd(d, n + k) 加入到第 \frac d{\gcd(d, n + k)} 个背包。最后假设有 c_i 个长度为 i 的环，判断第 i 个背包是否能凑出 c_i 即可。

时间复杂度：\mathcal O(\sum n^2)。

期望得分：40。

算法 3

给可能存在的和 n + k 因数个数有关的做法，或者是加以优化的背包。

有一个做法是，因为 c_i \le \frac ni，我们对于第 i 个背包可以只开到 \frac ni。并且一个背包里最多只会有 d(n + k) 个数，于是我们有一个很松的上界是 \mathcal{O}(n d(n + k) \ln n)。

期望得分：70。

算法 4

注意到一个结论：若 \frac x{\gcd(x, n + k)} = \frac y{\gcd(y, n + k)} = g，那么令 z = \gcd(x, y)，有 \frac z{\gcd(z, n + k)} = g。

证明是简单的，分别考虑每一个质因子 p，记 cx, cy, cz, c' 分别表示这个质因子在 x, y, z, n + k 里的出现次数，那么有 cx - \min(cx, c') = cy - \min(cy, c')。这可以导出 cx = cy 或 cx, cy \le c'。令 cz = \min(cx, cy)，两种情况都能进一步推出 cx - \min(cx, c') = cy - \min(cy, c') = cz - \min(cz, c')。

那么从该结论可以推出上述的每个背包中的所有数都是最小数的倍数，否则选出一个不是最小数倍数的数，它与最小数的 \gcd 更小。所以我们只保留背包中最小的数即可。

由于 \gcd(i, n + k) 是关于 i 的积性函数，可以做到线性。直接暴力求 \gcd 可能也能过。

时间复杂度：\mathcal O(\sum n) 或 \mathcal O(\sum n \log n)。

期望得分：100。