自动搬运

查看原文

来自洛谷，原作者为

	赫鲁老七 **

搬运于2025-08-24 21:46:30，当前版本为作者最后更新于2018-12-28 16:14:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为毛出题人不好好出数据啊 ...

这个 $pos_i=(c_i+d\times x_i+y_i)\operatorname{mod}n$ 看上去很有迷惑性啊，感觉是一个xjb写的式子然而并不是这样。

首先它这个 $d$ 是个定值，也就是说当我们确定了一个 $y_i$ 的时候，可选的位置一定是 $y_i+c_i,y_i+c_i+d,y_i+c_i+2\cdot d \dots$ 抽象点看的话发现每个点都有一个出边，其中 $x$ 指向 $(x+d)\operatorname{mod} n$。

因为每个点都有一个出边而且固定步长为 $d$，所以这本质上是 $\gcd(n,d)$ 个长度为 $\frac n{\gcd (n,d)}$ 的环。

所以 $y_i$ 实际上就确定了要在哪个环中找空位置，$x_i$ 就是确定了要在当前的环中找第几个空位。

所以一个暴力做法就是从小到大枚举 $y_i$，然后从小到大枚举 $x_i$，如果当前位置能放就放，否则找 $x_i+d$ 。如果当前环满了就将 $y_i+1$，然后继续找。

因为在同一个环内的步长固定为 $d$，所以在同一个环内找的时候可以拿并查集优化，每个点的祖先是这个点加若干个 $d$ 之后的第一个空位。最开始每个点的祖先是自己，如果点 $x$ 被占用，那就让 $father[x]=(x+d)\operatorname{mod} n$。

然而只优化找 $x_i$ 的过程是不够的， $n$ 个长度为 $1$ 的环就能卡掉了。所以还要优化找 $y_i$ 的过程，因为找 $y_i$ 的步长固定为 $1$，所以我们也对每个环弄一个并查集，每个环的祖先是从这个环加若干个 $1$ 之后第一个还有空位的环。最开始每个点的祖先是自己，如果环 $x$ 被填满，那就让 $father[x]=(x+1)\operatorname{mod} n$。

大体思路就是这样，但是还有一点小细节。假设 $p$ 是我们找到的第一个有空位的环，这时候 $y_i$ 就已经确定了对吧，所以我们要做的就是让 $x_i$ 最小。所以算出当 $x_i=0$ 时那个式子的值就是 $c_i+p-belong[c_i] \operatorname{mod} tot$，其中 $belong[i]$ 表示位置 $i$ 所在的环的编号，$tot$ 表示总环数，然后从这个值再往下找就吼了。

#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N=1e5+5;

int pos[N],vis[N];
int c[N],belong[N];
int n,q,p,m,d,s,tot;

struct bcj{
    int father[N];

    void init(){for(int i=0;i<n;i++) father[i]=i;}

    int find(int x){return father[x]==x?x:father[x]=find(father[x]);}

}A,B;

int getint(){
    int X=0,w=0;char ch=getchar();
    while(!isdigit(ch))w|=ch=='-',ch=getchar();
    while( isdigit(ch))X=X*10+ch-48,ch=getchar();
    if(w) return -X;return X;
}

void rem(int x){
    int r1=A.find(x),r2=A.find((r1+d)%n);
    if(r1!=r2) A.father[r1]=r2;
    else{
        r1=B.find(belong[x]),r2=B.find((r1+1)%tot);
        B.father[r1]=r2;
    }
}

int calc(int x,int y){
    return (x-y+tot)%tot;
}

signed main(){
    int T=getint();
    while(T--){
        n=getint(),s=getint(),q=getint(),p=getint(),m=getint(),d=getint()%n;
        A.init(),B.init();tot=0;
        for(int i=1;i<n;i++) c[i]=(1ll*c[i-1]*q+p)%m;
        memset(belong,-1,sizeof belong);
        for(int i=0;i<n;i++){
            if(belong[i]==-1){
                for(int j=i;belong[j]<0;j=(j+d)%n)
                    belong[j]=tot;
                tot++;
            }
        } 
        rem(s);pos[0]=s;
        for(int i=1;i<n;i++){ 
            c[i]%=n;
            int pp=B.find(belong[c[i]]);
            int qq=A.find((c[i]+calc(pp,belong[c[i]]))%n);
            pos[i]=qq;rem(qq);
        } 
        int ans=0;memset(vis,0,sizeof vis);
        for(int i=0;i<n;i++){
            if(!vis[i]){
                vis[i]=1;int now=i;
                int cnt=1,flag=now==s;
                while(!vis[pos[now]]){
                    now=pos[now];vis[now]=1;
                    cnt++;if(now==s) flag=1;
                }
                if(flag) ans+=cnt-1;
                else if(cnt>1) ans+=cnt+1;
            }
        } printf("%d\n",ans);
    } return 0;
}