[HNOI2010]物品调度 **题

· · 题解

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

这个 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;
}