CF1896E Permutation Sorting 题解

link T2です

$n$ 个人编号 $1 \dots n$，家编号 $1 \dots n$ 顺时针围成圈。
初始时编号为 $a_i$ 的人位于家 $i$ 的位置。

每轮，令所有未回家的人按顺时针排为 $b_1,b_2,\dots,b_k$，令 $b_j$ 移动到 $b_{j\bmod k+1}$ 的位置。如图所示。

求每个人第一次回到家所需的轮数。

---

这题不是模拟题。

这题其实是针对人的。

考虑在圆上每个人需要从 $s$ 走到 $t$，在圆上画出这个弧。

那么这个人走的轮数应该为：弧长减去其包含的弧的数量。

为什么？

考虑一个人 $i$，考虑某个人 $j$ 能使 $i$ 行走的距离变短的条件。

1. $s_j>s_i$。因为如果 $s_j<s_i$，那么 $j$ 时刻都在 $i$ 的身后，不能使 $i$ 距离变短。

2. $t_j<t_i$。因为如果 $t_j>t_i$，假如 $j$ 比 $i$ 早到，那也是在 $t_i$ 之外了，不会出现在 $i$ 的路径中。

   假如 $j$ 比 $i$ 晚到，那更不可能了。

那么断环为链后就是简单的二维数点。

sub