专栏文章

题解：P13702 [NWERC 2023] Chair Dance

LLinkCatTree
P13702题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min6eg4r
此快照首次捕获于
2025/12/01 21:19
3 个月前
此快照最后确认于
2025/12/01 21:19
3 个月前
查看原文
题目本身和解法都很有意思的题喵。
我们发现如果没有发生“抢椅子”，这个题能很简单的维护。具体的，我们可以发现一个人最初的位置 pos1pos_1 和当前位置 pos2pos_2 总是满足一个关系式 pos1×mul+add=pos2pos_1 \times mul + add = pos_2，其中 mulmul 与 addadd 都是很好维护的。
Info
对于 + x 操作，add←add+xadd \leftarrow add + x。
对于 * x 操作，mul←mul×x,add←add×xmul \leftarrow mul \times x, add \leftarrow add \times x。
那么我们只需考虑与维护“抢椅子”即可。首先我们发现一个性质：“抢椅子”不会发生超过 log⁡n\log n 轮。感性理解即可我们发现无论何时剩下的人的位置整除 gcd⁡(mul,n)\gcd(mul,n) 的结果能够取便 [0,ngcd⁡(mul,n))\left[0,\dfrac n{\gcd(mul,n)}\right) 中的每个值，所以对于一个 * x 操作，若 gcd⁡(x,n)≠gcd⁡(mul,n)\gcd(x,n) \neq \gcd(mul,n) 且 gcd⁡(x,n)≠1\gcd(x,n) \neq 1，这轮结束后每个人的位置都应为 gcd⁡(x,n)\gcd(x,n) 的倍数，那么容易发现将会发生“抢椅子”且人数将会除以 gcd⁡(x,n)\gcd(x,n)。由于每次人数至少减半，那么最多发生 log⁡n\log n 轮“抢椅子”就会只剩下一个人。
这个性质十分良好，我们希望在发生一轮“抢椅子”时能够使用 O(n)\mathcal{O}(n) 的时间复杂度进行维护。我们考虑我们是如何计算答案的：pos1≡(pos2−add)×mul−1(modn)pos_1 \equiv (pos_2 - add) \times mul^{-1} \pmod n，这里我们会发现一些问题：pos1pos_1 的解可能不止一个。我们考虑其实际意义，发现其不同解对应着一些抢椅子的人，而我们需要快速的维护这些抢椅子的人中最终抢到椅子的那个是谁。
这个有很多方法维护，这里笔者选择了并查集。具体的，让被抢椅子的人在并查集上的父亲指向抢到椅子的人（这些可以在模拟抢椅子的过程中完成），每次只需要找到 pos1pos_1 的一个解后求其在并查集上的祖先即可。
具体实现要注意椅子是 (0,n](0,n] 而非 [0,n)[0,n)，求解可以使用扩展欧几里得算法完成。
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...