CF1553E Permutation Shift 做题记录

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

对其进行下列操作：

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

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

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

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

$3 \leq n \leq 3 \times 10^5$，$0 \leq m \leq \dfrac{n}{3}$，$1 \leq p_i \leq n$ ，每个 $1 \sim n$ 的整数均只出现一次。

首先不难想到枚举每一个 $k$，求出循环移位之后的排列 $a$，快速判断能否在 $m$ 次交换内让 $p=a$。

若我们交换 $m$ 次，最多能让 $p$ 中 $2m$ 个数归位。也就是说，$p$ 中至少要有 $n-2m$ 个数不用交换就已经归位。

因为对于每个 $i$，不交换就让 $p_i=a_i$ 的 $a$ 只会有一个，所以每个 $i$ 都只会有一个 $k$ 能让 $p_i$ 不交换就已经归位，设这个 $k$ 为 $k_i$。

由于 $m\le \frac{n}{3}$，所以 $n-2m\ge \frac{n}{3}$。也就是说，我们枚举的 $k=k'$ 要满足至少有 $\frac n 3$ 个 $k_i=k$，所以满足条件的 $k'$ 最多只有 $3$ 个。

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

这是一个经典问题，建立 $n$ 个点，对于每一个 $p_i$，都从 $i$ 向满足 $p_j=a_i$ 的 $j$ 连一条有向边，最少交换次数即为 $n-\text{环个数}$。

其实也可以从 $i$ 向满足 $p_j=a_i$ 的 $j$ 连一条无向边，最少交换次数即为 $n-\text{连通块个数}$。

解释：

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

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