BZOJ 1998: [Hnoi2010]Fsk物品调度 [置换群并查集]

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

传送门

流水线上有n个位置，从0到n-1依次编号，一开始0号位置空，其它的位置i上有编号为i的盒子。Lostmonkey要按照以下规则重新排列这些盒子。规则由5个数描述，q，p，m，d，s，s表示空位的最终位置。首先生成一个序列c，c0=0，ci+1=(ci*q+p) mod m。接下来从第一个盒子开始依次生成每个盒子的最终位置posi，posi=(ci+d*xi+yi) mod n，xi,yi是为了让第i个盒子不与之前的盒子位置相同的由你设定的非负整数，且posi还不能为s。如果有多个xi，yi满足要求，你需要选择yi最小的，当yi相同时选择xi最小的。这样你得到了所有盒子的最终位置，现在你每次可以把某个盒子移动到空位上，移动后原盒子所在的位置成为空位。请问把所有的盒子移动到目的位置所需的最少步数。

研究了好长时间那个并查集是怎么用的，照着黄学长的代码一直看，最后得出一个结论：这也太乱搞了...

首先知道$pos$后就太容易做了置换群套路题

对于$len>1$的循环按有没有$0$分类

怎么算$pos$？

容易发现$y$最多$n$种取值，$x$每$+1$就是在环上移动$d$个位置

然后用并查集黑科技维护这个东西.....$fa$指向下一个可用位置，这个$y$上没可用位置就到$y+1$上去

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

const int N=1e5+;

typedef long long ll;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,s,q,p,m,d;

ll c[N];

int pos[N],fa[N],cir[N];

bool vis[N],full[N];

int find(int x){

    if(!full[cir[x]]) return x==fa[x]?x:fa[x]=find(fa[x]);

    else return find(fa[x]=(x+)%n);

}

void solve(){

    for(int i=;i<n;i++) c[i]=(c[i-]*q+p)%m;

    for(int i=;i<n;i++) c[i]%=n,fa[i]=i,cir[i]=-,vis[i]=,full[i]=;

    for(int i=;i<n;i++)

        for(int j=i;cir[j]==-;j=(j+d)%n) cir[j]=i;

    fa[s]=(s+d)%n;

    pos[]=s;

    if(d==) full[cir[s]]=;

    for(int i=;i<n;i++){

        int x=find(c[i]),y=find((x+d)%n);

        pos[i]=x;

        if(x==y) full[cir[x]]=;

        else fa[x]=y;

    }

    int ans=;

    for(int i=;i<n;i++) if(!vis[i]){//printf("\nhi %d ",i);

        int u=pos[i],len=;

        while(u!=i){//printf("%d ",u);

            vis[u]=;

            len++;

            u=pos[u];

        }

        //printf("len %d\n ",len);

        if(len>){

            if(i==) ans+=len-;

            else ans+=len+;

        }

    }

    printf("%d\n",ans);

}

int main(){

    freopen("in","r",stdin);

    int T=read();

    while(T--){

        n=read();s=read();q=read();p=read();m=read();d=read()%n;

        solve();

    }

}