P5689 [CSP-S2019 江西] 多叉堆

本文主要是介绍P5689 [CSP-S2019 江西] 多叉堆，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

试着推了一下静态树的做法，推挂了。。。
考虑一个点接到另一个点会怎么样。
肯定要乘上两边的答案 \(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;
} 

这篇关于P5689 [CSP-S2019 江西] 多叉堆的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！