BZOJ1998 - Click Here
Description
现在找工作不容易，Lostmonkey费了好大劲才得到fsk公司基层流水线操作员的职位。流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。 规则由5个数描述，q,p,m,d,s，s表示空位的最终位置。
首先生成一个序列$c$，$c_0=0,c_{i+1}=(c_i \times q + p) \, mod \, m$。接下来从第一个盒子开始依次生成每个盒子的最终位置$pos_i$，$pos_i = (c_i+d \times x_i + y_i) \, mod \, n$，$x_i,y_i$是为了让第i个盒子不与之前的盒子位置相同的由你设定的非负整数，且$pos_i$还不能为s。如果有多个$x_i,y_i$满足要求，你需要选择$y_i$最小的，当$y_i$相同时选择$x_i$最小的。 这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数。
Input
第一行包含一个整数t，表示数据组数。接下来t行，每行6个数，n,s,q,p,m,d意义如上所述。
所有数字的范围均<=1e5
Output
对于每组数据输出一个数占一行，表示最少移动步数。
Solutions
这题弄了好久，一开始以为是对剩余类分析，后来发现其实是对循环分析。
这题有两个问题要处理，一是求$pos_i$，二是求最小步数。
问题二：
根据$pos_i$，我们可以得到盒子的置换。
接着考虑置换的每个循环，若循环长度为1，则不需要交换；若循环内不包括空位，则需要$L+1$次交换；若循环内包含空位，则需要$L-1$次交换。
问题一：
由于题目是要求在$y_i$最小的情况下，$x_i$最小。因此可以固定一个变量，分析另外一个变量。另外，$c_i$计算过程独立于$pos_i$的计算过程，可以认为$c_i$是一个初始值。
在$y_i$固定的情况下，$x_i$的变换会使得初始值$+d$，也就是$a \rightarrow a+d$。显然，对于不同的$a$，其$a+d$也是不同的。换言之，这个过程是一个$0…n-1$向自身的双射，也就是一个置换！
如果将这个置换循环分解，那么$x_i$的作用实际是寻找某个循环内还未被选择的元素，$y_i$的作用则是跳到下一个循环内。基于这个意义，寻找最小的$y_i$等价于寻找第一个含有未被选择的元素的循环，寻找最小的$x_i$等价于在循环内寻找第一个未被选择的元素。
因此，我们需要某种数据结构去维护这些循环，且要求能够快速的寻找后继元素。
平衡树显然能完成这个操作，直接套用std::set即可解决。
时间复杂度$O(TN \, log \, N)$
CODE
CODE - Click Here