看似很难
其实很水
仔细观察其实是两问。
第一问确定xi,yi,
posi=(ci+d*xi+yi) mod n不是白给的。
其实是同一个d*x+c的环上的所有点通过xi调整找到，yi的作用是更新到另一个环上去。
暴力枚举yi，每个环上用并查集维护紧跟着下一个可选择的
如果下一个被删除了，那么这个环已经用完，++yi
可以过。（因为数据水，zhoutb2333 dalao已经卡掉）
所以，考虑对环和环之间也用并查集维护一下，这样总的复杂度就是O(N)了
第二问更水
类似置换的问题做过很多次了。
找到置换环之后，由于必须和空位交换，所以含空位的len-1次，不含空位的len+1次（要把空位换进来多一次）
环与环之间交换是没有必要的。
一些值得注意的坑是：
对于这种取模的问题，ci,d上来直接对n取模了事。。
否则可能比n大，而并查集中未定义，或者直接RE
代码：（暴力枚举y）
#include<bits/stdc++.h> #define reg register int #define il inline #define numb (ch^'0') #define int long long using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=100000+5; int n,t,s; int pos[N]; int q,p,m,d; int c[N]; int fa[N]; int fin(int x){ return fa[x]==x?x:fa[x]=fin(fa[x]); } bool dele[N]; bool vis[N]; int len; int kil; void init(){ for(reg i=0;i<n;++i) fa[i]=i; memset(dele,0,sizeof dele); memset(pos,0,sizeof pos); memset(vis,0,sizeof vis); int go=(s+d)%n; fa[s]=go;dele[s]=1; ++kil; len=0; } int query(int st){ int k=fin(st); // cout<<" kk "<<st<<" "<<d<<" : "<<k<<" "<<dele[k]<<" "<<(k+d)%n<<" "<<fin((k+d)%n)<<endl; if(!dele[k]){ int lp=fin((k+d)%n); if(lp!=k) fa[k]=lp; dele[k]=1; ++kil; return k; } return -1; } void dfs(int x){ vis[x]=1;++len; if(!vis[pos[x]]) dfs(pos[x]); } int main(){ rd(t); while(t--){ rd(n);rd(s);rd(q);rd(p);rd(m);rd(d); d%=n; init(); c[0]=0; for(reg i=1;i<n;++i) c[i]=((ll)c[i-1]*q+p)%m; for(reg i=1;i<n;++i){ c[i]%=n; // cout<<" ii "<<i<<" "<<kil<<" "<<c[i]<<endl; int y=0; int tmp=0; while((tmp=query((c[i]+y)%n))==-1){ ++y; //cout<<tmp<<" "<<y<<endl; } pos[i]=tmp; } pos[0]=s; int ans=0; for(reg i=0;i<n;++i){ //cout<<pos[i]<<" "; if(!vis[i]) { len=0; if(pos[i]!=i){ dfs(i); //cout<<" len "<<len<<endl; if(i==0) ans+=len-1; else ans+=len+1; } } }//cout<<endl; printf("%lld ",ans); } return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2018/12/27 14:17:54 */