题解：P3207 [HNOI2010] 物品调度

#include <bits/stdc++.h>
#define int long long
using namespace std;
int fa[100010],fac[100010],c[100010],pos[100010],vis[100010];
int n,s,q,p,m,d;
int root(int x){//环内并查集，维护x位置是否被占
	if(fa[x] == x)return x;
	fa[x] = root(fa[x]);
	return fa[x];
}
int rootc(int x){//环间并查集，维护x所在环是否已满
	if(fac[x] == x)return x;
	fac[x] = rootc(fac[x]);
	return fac[x];
}
void init(){
	for(int i = 0; i <= n; i++)fa[i] = fac[i] = c[i] = pos[i] = vis[i] = 0;
}
void solve(){
	scanf("%lld%lld%lld%lld%lld%lld",&n,&s,&q,&p,&m,&d);
	for(int i = 0; i < n; i++){
		if(i == 0)c[i] = 0;
		else c[i] = (c[i - 1] * q + p) % m;
		pos[i] = -1;
	}
	c[0] = s % n;//反正是第一个考虑，都是空位，直接把它记为s，它肯定会占用s位置
	//但是不能在其他i之前赋值，因为会影响后面的c[i]
	for(int i = 0; i <= n + 5; i++)fa[i] = fac[i] = i;
	for(int i = 0; i < n; i++){
		//j = (c[i] + y) % n,k = (c[i] + yi + xi * d) % n
		int j = c[i] % n;//m不一定小于n，即c[i]不一定小于n，记得取模
		while(rootc(j) != j || root(j) == n){//j所在环已经跑完，直接跳过
			if(rootc(j) == j)fac[j] = rootc((j + 1) % n);
			//这里连边是因为如果j所在的环已经满了，
			//但是最后一个被占的点为环上另一点k，
			//那么k在环间并查集标记了而j没有标记，
			//这里需要补标记
			j = rootc(j);
		}
		int k = j;//x_min=0
		while(root(k) != k)k = root(k);//找到j所在环的空位置
		pos[i] = k;
		if(k != root((k + d) % n)){
			fa[k] = root((k + d) % n);
		}else{
			fac[j] = rootc((j + 1) % n),fa[k] = n;
		//再跳一步就从环上连续段的尾调到头了，说明这个环满了
		}
	}
	//注意概念上置换形成的环与处理pos时每次跳d单位的环不同
	int ans = 0;
	for(int i = 1; i < n; i++){
		if(vis[i] || pos[i] == i)continue;//i所在环已经处理或者自环情况就不用再处理了
		int now = i,fl = 0,cnt = 0;
		while(!vis[now]){
			vis[now] = 1,cnt++;
			if(now == s)fl = 1;
			now = pos[now];
		}
		if(fl)ans += cnt - 1;
		else ans += cnt + 1;
	}
	printf("%lld\n",ans);
}
signed main(){
	int T;
	scanf("%lld",&T);
	while(T--){
		init(),solve();
	}
	return 0;
}