试着推了一下静态树的做法,推挂了。。。
考虑一个点接到另一个点会怎么样。
肯定要乘上两边的答案 \(ans_x\times ans_y\)。
然后发现有一部分分在新子树上,其余部分分在其他子树上。由于只考虑大小关系,所以 \(1 2 3\) 和 \(233 114514 1919810\) 本质上是一样的。对于两种堆不同当且仅当存在某个结点填入的值不同,可以依靠 \(C(sze_x,sze_x+sze_y-1)\) 解决。
所以可以解决合并的。
#include<bits/stdc++.h> using namespace std; const int maxn=3e5+5; #define int long long int fa[maxn]; int fd(int x){ return x==fa[x]?x:fa[x]=fd(fa[x]); } int n,q,Ans=0; int sze[maxn],ans[maxn],jc[maxn]; const int mod=1e9+7; int ksm(int a,int b){ if(b==1)return a; int ans=ksm(a,b>>1); if(b&1)return ans*ans%mod*a%mod; else return ans*ans%mod; } int ny(int x){ return ksm(x,mod-2); } int C(int n,int m){ return jc[m]*ny(jc[n])%mod*ny(jc[m-n])%mod; } signed main(){ cin>>n>>q; for(int i=1;i<=q;i++)fa[i]=i; for(int i=1;i<=n;i++)ans[i]=1,sze[i]=1; jc[0]=1; for(int i=1;i<=n;i++)jc[i]=jc[i-1]*i,jc[i]%=mod; for(int i=1;i<=q;i++){ int ch,x,y; cin>>ch>>x; if(ch==1){ cin>>y; x=(x+Ans)%n;y=(y+Ans)%n; x++,y++; int fx=fd(x),fy=fd(y); ans[fy]=ans[fx]*ans[fy]%mod*C(sze[fx],sze[fx]+sze[fy]-1)%mod; sze[fy]+=sze[fx];fa[fx]=fy; } else{ x=(x+Ans)%n; cout<<ans[fd(x+1)]<<endl; Ans=ans[fd(x+1)]; } } return 0; }