CF1787F - Inverse Transformation 题解

· · 题解

题意简化

*2500

对于一个排列，每天会将其 p_i\gets p_{p_i}。给出 k 天后的排列，求原排列最少有几个轮换。

题解

操作比较抽象，手动刻画一下。

对于一个原轮换，一次操作后 i\to p_i 会变成 i\to p_{p_i}，也就是原图中向前走两步的结果。

规律性非常强，进一步的，我们有以下两个结论：

  1. 对于置换 (a_1~a_2~\cdots~a_n)，若 n 为偶数，则该置换进行一步变换后会变成 (a_1~a_3~\cdots~a_{n-1})(a_2~a_4~\cdots~a_n)。
  2. 对于置换 (a_1~a_2~\cdots~a_n)，若 n 为奇数，则该置换进行一步变换后会变成 (a_1~a_3~\cdots~a_n~a_2~\cdots~a_{n-1})。

不难发现长度为奇数的轮换长度不会改变，长度为偶数的会被一直除 2 直到变为奇数。

原题是给定最后的结果，要求反推 k 次前的最小轮换数。

感觉就不用多说了，先把结果的排列分解成若干个轮换，然后挑选两个大小相等的轮换合并。

还要考虑无解的情况。对于结果排列，如果存在一个长度为偶数的轮换，则前 k 次其都必须被合并到，换句话说必须存在 2^k 个长度和其一样的轮换（包括自己），如果不存在直接输出无解。

考虑掉上面这个情况后，剩下的轮换我们按长度分类，统计长度相同的轮换数量。显然问题变成对其分组，并且每组的大小都要是 2 的幂次。

把数量拆分为两部分考虑，对于小于等于 2^k 的部分，则直接拆分成每个二进制 bit 即可，对于大于 2^k 的部分，拆分成若干个 2^k 即可。最优性显然。

对于分到一组的轮换，随便钦定一个顺序轮流放即可，正确性显然。

总时间复杂度 O(n)。