题解：P13702 [NWERC 2023] Chair Dance

· · 题解

题目本身和解法都很有意思的题喵。

我们发现如果没有发生“抢椅子”，这个题能很简单的维护。具体的，我们可以发现一个人最初的位置 pos_1 和当前位置 pos_2 总是满足一个关系式 pos_1 \times mul + add = pos_2，其中 mul 与 add 都是很好维护的。

:::info

对于 + x 操作，add \leftarrow add + x。

对于 * x 操作，mul \leftarrow mul \times x, add \leftarrow add \times x。

:::

那么我们只需考虑与维护“抢椅子”即可。首先我们发现一个性质：“抢椅子”不会发生超过 \log n 轮。感性理解即可我们发现无论何时剩下的人的位置整除 \gcd(mul,n) 的结果能够取便 \left[0,\dfrac n{\gcd(mul,n)}\right) 中的每个值，所以对于一个 * x 操作，若 \gcd(x,n) \neq \gcd(mul,n) 且 \gcd(x,n) \neq 1，这轮结束后每个人的位置都应为 \gcd(x,n) 的倍数，那么容易发现将会发生“抢椅子”且人数将会除以 \gcd(x,n)。由于每次人数至少减半，那么最多发生 \log n 轮“抢椅子”就会只剩下一个人。

这个性质十分良好，我们希望在发生一轮“抢椅子”时能够使用 \mathcal{O}(n) 的时间复杂度进行维护。我们考虑我们是如何计算答案的：pos_1 \equiv (pos_2 - add) \times mul^{-1} \pmod n，这里我们会发现一些问题：pos_1 的解可能不止一个。我们考虑其实际意义，发现其不同解对应着一些抢椅子的人，而我们需要快速的维护这些抢椅子的人中最终抢到椅子的那个是谁。

这个有很多方法维护，这里笔者选择了并查集。具体的，让被抢椅子的人在并查集上的父亲指向抢到椅子的人（这些可以在模拟抢椅子的过程中完成），每次只需要找到 pos_1 的一个解后求其在并查集上的祖先即可。

具体实现要注意椅子是 (0,n] 而非 [0,n)，求解可以使用扩展欧几里得算法完成。

inline int gcd(int x,int y) {
    return !y?x:gcd(y,x%y);
}
inline int exgcd(int a,int b,int &x,int &y) {
    if(!b) return x=1,y=0,a;
    int k=exgcd(b,a%b,y,x);
    return y-=a/b*x,k;
}
inline int find(int x) {
    return (x==fa[x])?x:(fa[x]=find(fa[x]));
}

int main() {
    dt=n=read(),q=read();
    for(int i=1;i<=n;i++) fa[i]=i;
    auto df=[](int x)->int {return (x<0)?x+n:x;};
    auto dg=[](int x)->int {return !x?n:x;};
    for(int i=1;i<=q;i++) {
        char ch=getchar();
        while(ch!='?'&&ch!='+'&&ch!='*') ch=getchar();
        if(ch=='+') {
            add+=read();
            if(add>=n) add-=n;
        }
        if(ch=='?') {
            // x * mul + add = pos
            int pos=df(read()-add);
            int x,y,g=exgcd(mul,n,x,y);
            if(pos%g) printf("-1\n");
            else {
                int k=dg(((ll)x*(pos/g)%n+n)%n);
                printf("%d\n",find(k));
            }
        }
        if(ch=='*') {
            int v=read();
            if(gcd(v,dt)<2) {
                mul=(ll)mul*v%n,add=(ll)add*v%n;
                continue ;
            }
            dt/=gcd(v,dt);
            memset(dis,-1,sizeof(int)*(n+2));
            memset(from,-1,sizeof(int)*(n+2));
            for(int i=1;i<=n;i++) {
                if(fa[i]!=i) continue ;
                int p=dg(((ll)i*mul+add)%n),q=dg((ll)p*v%n),d=df(q-p);
                if(from[q]<0) {dis[q]=d,from[q]=i; continue ;}
                if(d<dis[q]) dis[q]=d,from[q]=fa[from[q]]=i;
                else fa[i]=from[q];
            }
            mul=(ll)mul*v%n,add=(ll)add*v%n;
        }
    }
    return 0;
}