http://www.lydsy.com/JudgeOnline/problem.php?id=1998
题意：
给你6个整数$n，s，q，p，m，d$。
有$n$个位置和$n-1$个盒子，位置编号从$0$开始（盒子编号从$1$开始）。一开始第$i$个盒子在第$i$个位置上，$0$号位置是空位。然后有一个$pos$序列，其中$i$位置上放的盒子是$pos_i$（其中$s$位置上必须是空位）。问：每次只能将一个盒子移动到空位上（然后这个盒子的位置变成空位），求从初始局面移动到$pos$局面的最少步数。
$pos$序列的按以下规则生成：首先生成一个序列$c$，满足$c_0=0, c_i = (c_{i-1}*q+p) mod m$，然后$pos_i = (c_i + d*x_i + y_i) mod n$，其中$x_i、y_i$是需要你来求出。但是必须满足$x_i、y_i$是非负整数，而且得到的$pos_i$不能与之前的求出的$pos$相同。如果有多个$x_i、y_i$满足条件，则优先选择$y_i$最小的；如果$y_i$相等时，则优先选择$x_i$最小的。
数据范围：上述整数均<=100000
#include <bits/stdc++.h>
using namespace std;
const int N=1000005;
typedef long long ll;
bool vis[N];
int c[N], ps[N], cnt[N], g[N], n, s, q, p, m, d;
struct dat {
int next, ok;
};
int find(int x, dat *a) {
if(a[x].ok)
return x;
int nxt=a[x].next, ret=find(nxt, a);
if(nxt!=ret)
a[x].next=a[nxt].next;
return ret;
}
dat a[N], b[N];
void init() {
d%=n;
int gr=0;
if(d==0) d=1;
for(int i=0; i<n; ++i)
a[i].next=(i+d)%n, a[i].ok=1;
for(int i=0; i<d; ++i) if(g[i]==-1) {
++gr;
for(int j=i; g[j]==-1; j=(j+d)%n)
g[j]=i, cnt[i]++;
}
a[s].ok=0;
cnt[g[s]]--;
for(int i=0; i<gr; ++i)
b[i].next=(i+1)%gr, b[i].ok=cnt[i]>0;
for(int i=1; i<n; ++i)
c[i]=((ll)c[i-1]*q+p)%m;
for(int i=1; i<n; ++i) {
c[i]%=n;
int y=(find(g[c[i]], b)+gr-g[c[i]])%gr,
pos=find((c[i]+y)%n, a);
ps[pos]=i;
a[pos].ok=0;
if(!--cnt[g[pos]]) b[g[pos]].ok=0;
}
ps[s]=0;
memset(cnt, 0, sizeof(int)*d);
memset(g, -1, sizeof(int)*n);
}
int main() {
int T; scanf("%d", &T);
memset(g, -1, sizeof g);
while(T--) {
scanf("%d%d%d%d%d%d", &n, &s, &q, &p, &m, &d);
init();
int ans=0;
for(int i=0; i<n; ++i) if(!vis[i]) {
int len=0, flag=0;
for(int j=i; !vis[j]; j=ps[j])
vis[j]=1, ++len, flag=flag+(ps[j]==0);
ans+=len>1?len+(flag?-1:1):0;
}
memset(vis, 0, sizeof(int)*n);
printf("%d
", ans);
}
return 0;
}
好神的题啊..（不是太神，而是我太弱...参考题解：http://blog.163.com/benz_/blog/static/186842030201142352718885/
首先如果得到了$pos$序列，那么我们很容易根据置换群的理论计算出答案。
那么问题的难点在于求出这个$pos$序列。
发现当$c_i+y_i$固定后，所得到的$pos_i$解集是一个环！
如果$c_i+y_i$所在的环被用完了，那么$y_i$应该加上一个数$k$，使得到达一个还有没用过的位置的环！
（于是我自行yy了一个链表= =和参考题解的差不多，可是为何我的那么慢..
首先我们把环分组（每一组都是从左往右找到第一个不是其他环的数，然后一直$+d$，得到的数形成的环为一组（组编号从0开始））。发现这样做得到最多不超过$d$个组。
令最后一个非空组为$j$，第一个组为$i=0$，而由于$j$后面的空组是没用的（即$j$上的数如果$+1$就到达了$i$上的数，并没有经过后面的空组），所以我们只需要看成有$j+1$个组即可。
而又发现，组与组的距离（就是从一个组上的数加这个距离得到了另一个组上的数）其实是模$j+1$的减法！（比如$a$组和$b$组的距离$k$就是满足$a+k equiv b pmod{j+1}$的最小的$k$，那么$a$组上的数加上$k$一定是$b$组上的数）。
而在每一组内，我们同样将环内元素用一个链表来搞，只不过在查找的时候用了类似并查集的路径压缩做法（复杂度应该是均摊$O(n)$的？？QAQ），就是说如果一个点被删除了，而这个点的后继是非空环，那么前驱的后继连到这个点的后继，递归处理一下即可。
（还有发现$d=0$的情况其实可以看做$d=1$的情况，因此特判一下把$d$变成1就行辣～