置换群的部分水得一比,据说是经典的置换群理论(然而我并不知道这理论是啥).
重点就在于怎么求pos!!!
容易发现这个东西是这样的:每次寻找pos,先在本环里找,找不到再往下一个环里找,直到找到为止……
一开始我想二分或者是set,但是感觉会T,然后想了很久之后想到用并查集:
就是维护每一个被占用的位置的下一个位置,因为这个位置被占用之后就会转向下一个位置,当然下一个位置有在环内部和在下一个环里两种情况,这两种情况都我都是用并查集维护的,但是一定要注意,不要把这两种情况写成一个并查集,这样路径压缩之后会出事,所以要对于这两种情况分别维护两个并查集.
#include <cstdio>
#include <cstring>
#include <algorithm>
typedef long long LL;
const int N=;
int n,d,c[N],pos[N],f1[N],f2[N];
bool vis[N];
inline int find1(int x){return f1[x]==x?x:f1[x]=find1(f1[x]);}
inline int find2(int x){return f2[x]==x?x:f2[x]=find2(f2[x]);}
inline int get(int x){
int ret=find2(find1(x));
if(find2((ret+d)%n)==ret){
f1[ret]=(ret+)%n;
for(int i=(ret+d)%n;i!=ret;i=(i+d)%n)
f1[i]=(i+)%n;
}else f2[ret]=find2((ret+d)%n);
return ret;
}
int main(){
register int i;
int s,q,p,m,T,j,ans,size;
bool yeah;
scanf("%d",&T);
while(T--){
scanf("%d%d%d%d%d%d",&n,&s,&q,&p,&m,&d);
c[]=,pos[]=s,ans=,d%=n;
for(i=;i<n;++i)c[i]=((LL)c[i-]*q+p)%m;
for(i=;i<n;++i)c[i]%=n,vis[i]=false,f1[i]=f2[i]=i;
get(s);
for(i=;i<n;++i)pos[i]=get(c[i]);
for(i=;i<n;++i){
if(vis[i])continue;
vis[i]=true,yeah=i==,size=;
for(j=pos[i];j!=i;j=pos[j])
vis[j]=true,++size,yeah=(yeah||(j==));
if(size!=)ans+=size+(yeah?-:);
}
printf("%d\n",ans);
}
return ;
}