P5689 [CSP-S2019 江西] 多叉堆

小h话说有人知道这些特殊性质和特殊的数据规模怎么用吗？

这道题涉及了当年的一场事故。jx的考生比较少，因此只有一个考点。恰逢停电，选手们的代码都丢失了，因此才单独出题。

这道题只需并查集和费马小定理。

首先，预处理出n以下的阶乘以及阶乘关于1000000007的逆元。定义一个并查集，还要维护该并查集每一个根的树的大小和填充方案数。

对于每一次操作1，先把x的根连接到y的根下，此时y的siz要加上x的siz。然后求y的res。利用乘法原理，首先把res x和res y相乘。因为根一定最小，因此还有siz y-1个节点不确定，而y自己本来的子树和x无关，因此可以随便分配数字，所以是C（siz y -1，siz x）。

对于操作2，直接输出答案即可。不要忘记强制在线。

正解#include<bits/stdc++.h> definemod 1000000007ll defineLL long long defineN 300005 using namespace std; LL ksm(LL x,LL y=mod-2){ LL res=1; while(y){ if(y&1) res=res*x%mod; x=x*x%mod; y>>=1; } return res; } LL n,qwq,opt,ans,jc[N],ni[N],fa[N],siz[N],res[N]; LL find(LL x){ if(x==fa[x]) return x; fa[x]=find(fa[x]); return fa[x]; } LL C(LL x,LL y){ return (jc[x]*ni[x-y]%mod)*ni[y]%mod; } int main(){ //freopen("1.in","r",stdin); scanf("%lld%lld",&n,&qwq); LL x,y; jc[0]=1; ni[0]=1; for(x=1;x<=n;x++){ fa[x]=x; jc[x]=jc[x-1]*x%mod; ni[x]=ksm(jc[x]); res[x]=1; siz[x]=1; } while(qwq--){ scanf("%lld%lld",&opt,&x); x=find((x+ans)%n+1); if(opt==1){ scanf("%lld",&y); y=find((y+ans)%n+1); fa[x]=y; siz[y]+=siz[x]; res[y]=(res[x]*res[y]%mod)*C(siz[y]-1,siz[x])%mod; } else{ ans=res[x]; printf("%lld\n",ans); } } return 0; }

小h

小h哪里看不懂可以提问，不要认为我在灌水。