CF1553E Permutation Shift 做题记录

一个长度为 nn 的初始排列为 [1,2,3,4,,n][1,2,3,4,\ldots,n]

对其进行下列操作:

  • 首先,我们将其循环移动 kk 位, kk 为一个未知数 (0kn1)(0 \leq k \leq n-1)

将一个长度为 nn 的数组循环移动k位就是将原数组最后 kk 位移动到第 1k1 \sim k 位,并将其余 nkn-k 位移动到第 k+1nk+1 \sim n 位。比如说,我们将 [1,2,3,4,5,6][1,2,3,4,5,6] 循环移动两位,就是 [5,6,1,2,3,4][5,6,1,2,3,4]

  • 然后,我们将数组中任意两个数交换,最多进行 mm 次。

给定 n,mn,m 和最后的结果,你需要找出所有可能的 kk 值。

3n3×1053 \leq n \leq 3 \times 10^50mn30 \leq m \leq \dfrac{n}{3}1pin1 \leq p_i \leq n ,每个 1n1 \sim n 的整数均只出现一次。

首先不难想到枚举每一个 kk,求出循环移位之后的排列 aa,快速判断能否在 mm 次交换内让 p=ap=a

若我们交换 mm 次,最多能让 pp2m2m 个数归位。也就是说,pp 中至少要有 n2mn-2m 个数不用交换就已经归位。

因为对于每个 ii,不交换就让 pi=aip_i=a_iaa 只会有一个,所以每个 ii 都只会有一个 kk 能让 pip_i 不交换就已经归位,设这个 kkkik_i

由于 mn3m\le \frac{n}{3},所以 n2mn3n-2m\ge \frac{n}{3}。也就是说,我们枚举的 k=kk=k' 要满足至少有 n3\frac n 3ki=kk_i=k,所以满足条件的 kk' 最多只有 33 个。

但是这个条件只是必要条件,不是充分条件,所以我们还要作进一步的判断。设循环移位 kk' 位之后的排列是 aa,那么问题就转化为求让 p=ap=a 的最少交换次数。

这是一个经典问题,建立 nn 个点,对于每一个 pip_i,都从 ii 向满足 pj=aip_j=a_ijj 连一条有向边,最少交换次数即为 n环个数n-\text{环个数}

其实也可以从 ii 向满足 pj=aip_j=a_ijj 连一条无向边,最少交换次数即为 n连通块个数n-\text{连通块个数}


解释:

考虑这样构造出来的图,显然每个点都有且仅有一个入度和一个出度,那么最后的图一定是由若干个环组成的。

考虑一次交换操作,显然只有交换同一个环内的点是有用的,交换 pi,pjp_i,p_j 就相当于把 ii 的出边和 jj 的出边交换,相当于把大环断成两个小环,那么总共需要断 环的大小1\text{环的大小}-1 次,所以做法成立。