[luogu4255]公主の#18文明游戏

luogu

发现没有连边,只有删边?

考虑倒着做

开map记M[i][j]表示编号为i的并查集,信仰j的人数

s[i]表示编号为i的并查集的总人数

首先询问的答案就是$$\frac{\binom{M[x][c]}{N}}{\binom{s[x]}{N}}$$

map可以暴力启发式合并,复杂度$qlog^2n$

#include<bits/stdc++.h>

using namespace std;

const int _=400005,mod=19260817;

int re(){

	int x=0,w=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

	while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*w;

}

int n,m,q;

int t[_],fa[_],ans[_],s[_],jc[_*10];

bool del[_];

vector<int>r[_];

map<int,int>M[_];

map<int,int>::iterator it;

struct edge{int u,v;}e[_];

struct node{int x,y,c,op;}p[_];

int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

void merge(int x,int y){

	x=find(x);y=find(y);

	if(x==y)return;

	if(M[x].size()<M[y].size())swap(x,y);

	fa[y]=x;s[x]+=s[y];

	for(it=M[y].begin();it!=M[y].end();++it)

		M[x][(*it).first]+=(*it).second;

}

int ksm(int x,int y){

	int s=1;

	while(y){if(y&1)s=1ll*x*s%mod;x=1ll*x*x%mod;y>>=1;}

	return s;

}

int C(int x,int y){

	if(x<y)return 0;

	return 1ll*jc[x]*ksm(jc[y],mod-2)%mod*ksm(jc[x-y],mod-2)%mod;

}

int main(){

	n=re(),m=re(),q=re();

	jc[0]=1;

	for(int i=1;i<=4000000;i++)

		jc[i]=1ll*jc[i-1]*i%mod;

	for(int i=1;i<=n;i++)

		s[i]=re(),M[i][re()]=s[i];

	for(int i=1;i<=m;i++){

		int u=re(),v=re();

		e[i]=(edge){u,v};t[i]=q;

	}

	for(int i=1;i<=q;i++){

		int op,x,y,c;

		op=re();

		if(op==1){

			x=re(),y=re(),c=re();

			p[i]=(node){x,y,c};

			s[x]+=y;M[x][c]+=y;

		}

		if(op==2){

			x=re();t[x]=min(t[x],i);del[i]=1;

		}

		if(op==3){

			x=re(),y=re(),c=re();

			p[i]=(node){x,y,c,1};

		}

	}

	for(int i=1;i<=m;i++)

		r[t[i]].push_back(i);

	for(int i=1;i<=n;i++)fa[i]=i;

	for(int i=q;i>=1;i--){

		for(int j=0,sz=r[i].size();j<sz;j++){

			int id=r[i][j];

			merge(e[id].u,e[id].v);

		}

		if(del[i])continue;

		if(!p[i].op){

			int x=find(p[i].x);

			s[x]-=p[i].y;

			M[x][p[i].c]-=p[i].y;

		}

		else{

			int x=find(p[i].x);

			ans[i]=1ll*C(M[x][p[i].c],p[i].y)*ksm(C(s[x],p[i].y),mod-2)%mod;

		}

	}

	for(int i=1;i<=q;i++)

		if(p[i].op)printf("%d\n",ans[i]);

	return 0;

}

巴特西

[luogu4255]公主の#18文明游戏

[luogu4255]公主の#18文明游戏

最新文章

热门文章