【搬运于2026-4-26】【原文写于2025-11-22】
听说 noip 前写题解可以增加 rp 咕咕？
感觉是道并查集维护连通性的好题。题解采用引导式，因为自己弄了很久才明白，希望尽量解释详细，所以比较长。思路大体上和其他题解差不多，但是补充了更多细节。
:::::info[ \(x\) 和 \(y\) 序列怎么确定？]
首先要明确：\(x_i\) 和 \(y_i\) 不是让你任意选择的，在序列 \(c\) 确定时 \(x\) 和 \(y\) 序列是唯一的。先考虑 \(y_i\) 尽量小，再考虑 \(x_i\) 尽量小，有空位就占用。
注意到 \(c_i\) 和 \(y_i\) 固定时，\(x_i\) 每增加 \(1\)，最终位置就增加 \(d\) 然后再放到取模意义下。设 \(c_i + y_i = x\)，则可以抽象为 \(x\) 有一条出边 \((x + d) \bmod n\)。每个 \(x\) 都有一条出边，一条入边，所以这些边形成若干个环。\(x_i\) 增加 \(1\) 相当于在环上沿边跳一步。
找空位时先从 \((c_i+y_i) \bmod n\) 所在的环上找，看环上有没有空位，如果没有空位就增加 \(y_i\)，如果有空位则在环上找到能使 \(x_i\) 的最小的空位。
显然有一种暴力做法是先枚举 \(y_i\)，再枚举 \(x_i\)。但是这样太慢了。能不能加速呢？
::::info[加速]
枚举太慢了，因为很多已经被占的位置都会被枚举到。为了跳过这些位置，可以使用并查集维护连通性。这里就是维护一个环上的已被占有的连续段，这样可以在枚举 \(x_i\) 的时候跳过连续段。总共枚举 \(x_i\) 只用了 \(O(n)\) 次。
但是枚举 \(y_i\) 还是很慢啊？如果环长为 \(1\)，时间就被卡飞了。
:::info[再加速]
已满的环的也可以用并查集维护连续段。具体的，维护的连续段内的任意元素所在的环内都满了。称其为环间并查集。之前那个成为环内并查集。
多个点属于一个环没关系，如果是添加到某一个点的时候，这个环满了，我们在环间并查集标记了这个点，但是这个环里其他点也要在环间并查集标记，这是处理的一个细节。我的程序中采用其他点先不标记，等到后面再处理到这个环时，如果满了但还没有标记，就顺手标记了再往下搜。
:::
::::
:::::
到这里，我们确定了 \(x\) 序列和 \(y\) 序列，从而确定了所有盒子的最终位置 \(pos\)。这是第一步，下一步我们要确定怎么移动盒子。
:::warning[一个错误的想法：每次把目标位置在当前空位的盒子移过去]
反例：\(n=5\)，\(s=1\)，编号 \(1\) 到 \(4\) 的盒子最终位置为 \(2,0,4,3\)，你会发现按这种办法则编号 \(3\) 和 \(4\) 的盒子无法归位。
:::
:::info[如何移动]
这里有个小 trick，把 \(0\) 位置上看做有一个虚盒子（实际不存在），它的目标位置为 \(s\)。盒子移到空位转换为和 \(0\) 号盒子交换位置。原问题变成了一个置换问题。
现在每个初始位置和目标位置都能一一对应了。现在把初始位置编号向对应的目标位置编号连一条边，就会发现每个编号入度 \(1\)，出度 \(1\)，形成了若干个环。注意这一步的环和上一步确定 \(pos_i\) 时的环没有任何关系。不要弄混了。
对于包含 \(0\) 节点的环，每次把目标位置在当前空位的盒子移过去，也就是顺着环移动，移动次数为 \((环长-1)\)。
对于不包含 \(0\) 节点的环，因为交换必须借助 \(0\) 号箱子，所以先用一次交换把 \(0\) 节点换进来，再和上面那种情况一样方法操作即可。最后用一次交换把 \(0\) 节点换出去。移动次数为 \((环长+1)\)，比上面那种情况多了头尾两次交换。
当然对于自环需要特判。自环不需要任何交换。
:::
完成了，下面是代码。感觉细节挺多。
:::success[代码]
#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) % nint 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=0while(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;
}
:::