CF1787F Inverse Transformation 题解

· · 题解

2023/2/21 Update 修复笔误并增加了我的 std

出题人来背锅了

题目大意

给定长度为 n 的排列 a。定义 \sigma(x) = a_x。定义 f(x) 等于最小的 m，满足 \sigma^m(x) = \underbrace{\sigma(\sigma(\ldots \sigma}_{m \text{ 个 } \sigma}(x) \ldots)) = x。

每一天 a 中的每个元素 x 都会变成 \sigma(x)，\sigma(x) 随 a 变动。给出第 k 天的排列 a'，找出 \sum\limits_{i=1}^n \dfrac{1}{f(i)} 最小的一个排列 a。

这是原来的题面，由于易引起歧义故改成现在的版本（虽然没啥大区别

思路

先思考若知道了 a 如何求 a'。

对于 i 和 a_i 之间建立有向边，这样能更好展现变化过程。容易发现，得到的图由若干个环组成，接下来研究这些环在变化中呈现出的规律。

对于一个长度为 l 的环 c（c 内按顺序对元素重新标号），a_x 在第一天后会变成 x 后面的元素，即 x 会指向之后的两个元素；第二天，同理 x 会指向新图中其之后的第二个元素，也就是原图中 x 之后的第 4 个元素……这样下去，我们会发现，x 在第 k 天会指向其之后的第 2^k 个元素，也就是 c_{(X + 2^k)\bmod l}（X 为 x 新的标号，下标为 0 则为 l）。举个栗子，对于环 2\rightarrow 1\rightarrow 3(\rightarrow 2)，我们按顺序重新标号（2 标为 1 以此类推），得到 2(\texttt{1})\rightarrow 1(\texttt{2})\rightarrow 3(\texttt{3})(\rightarrow 2(\texttt{1}))（括号内为标号）。第二天时，2 会指向其之后的第 2^2 = 4 个元素，即 c_{(1 + 4)\bmod 3} = c_2 = 1。

但是真的是这样吗？对于奇数的 l，2^k \bmod l\neq 0，故会像上述那样不断循环。但是，若 l 为偶数，我们发现，在第一天后，c_1 指向 c_3，c_3 指向 c_5，……，c_{n-1} 指向 c_1；c_2 指向 c_4，c_4 指向 c_6，……，c_{n-2} 指向 c_2。于是，我们发现原图分裂成了两个大小相等（均为 \dfrac{l}{2}）的小环。于是，一个大小为 l = 2^q\cdot p 的环在 q 天后会得到 2^q 个大小为 p 的环。如下图，一个大小为 12 的环经过两天分裂为了 4 个大小为 3 的环（感谢 rsj 为题解配的图）：

所以，对于 a，我们可以暴力跑至少 \log n 天把所有偶环分裂掉，然后使用上述结论得到最终结果。

接下来我们考虑这题。

显然 f(x) 即为 x 所在环的大小，故 \sum\limits_{i=1}^n \dfrac{1}{f(i)} 即为图中环的个数。为了让原图中环的个数最小化，我们可以将大小相同的环不断合并。对于 a' 中奇数大小的环，可以不断将 2^q（q\le k）个合并；对于偶数大小的环，只能恰好将 2^k 个合并，若个数不是 2^k 的倍数则输出 NO。

现在我们知道了原图的形态，现在要做的就是填数。方法很多，可以使用数学方法（参考 CF 题解中 rsj 的 std），也可以像我一样暴力跑然后映射（码量有点大，很容易寄）。

总体来说，这题出得不是特别满意，结论不难想但是码量有点大。再次为大家道歉了。

我的代码在这里（太难理解了，若有需要请移步 CF 看 rsj 的代码。

最后感谢大家捧场我们的 CF（虽然出了一堆问题....