Luogu P4255 公主の#18文明游戏 题解
Describe
题目链接
这个游戏里有n个城市，标号1n，有m条双向道路相连，编号1m。
游戏里会系统会添加Ni个人到一个城市Xi，并给定这些人的信仰Ci
系统还会切断一条道路，并给定道路编号Xi
系统还会给定一个城市Xi，询问从Xi出发可以到达的所有城市中选择Ni个人，使得他们信仰都为Ci的概率为多少，对19260817取模。
Solution
首先用并查集搞成各个连通块，然后每个连通块用个map储存信仰为Ci的个数。再开一个vector储存每个连通块有哪些信仰。
那么每次答案就可以求出信仰为Ci的人数C和连通块总人数A。
那么答案就是ans=frac{C_C^Ni}{C_A^Ni}。
那么用快速幂逆元一下就好了。
维护的时候可以用vector的find,erase和并查集启发式合并即可。
技巧：由于断边比较困难，所以时间倒流，断边变成连边，加值变成减值。
Code
代码语言：javascript复制#include<bits/stdc .h>
#define LL long long
#define mod 19260817
using namespace std;
inline int read(){
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
inline void write(int x){
if(x<0) putchar('-'),x=-x;
if(x<10) putchar(x '0');
else write(x/10),putchar(x '0');
}
int n,m,q,fa[400010],vis[400010],A,C,ans[400010],Z[400010];
LL fac[400010*4];
inline LL fpow(LL a,LL b){// 快速幂，求逆元
LL s=1;
while(b){
if(b&1) s*=a,s%=mod;
a*=a;a%=mod;
b>>=1;
}
return s;
}
struct Edge{
int x,y;
}E[400010];
struct Question{
int op,x,y,z;
}Q[400010];
map<int,int> v[400010];
vector<int> g[400010];
inline int getfa(int x){// 并查集启发式合并
int a=x,y;
while(x!=fa[x]) x=fa[x];
while(a!=x) y=a,a=fa[a],fa[y]=x;
return x;
}
inline void merge(int x,int y){
x=getfa(x);y=getfa(y);
if(x==y) return ;
if(v[x].size()<v[y].size()) swap(x,y);// 选择小的合并到大的
fa[y]=x;Z[x] =Z[y];
for(int i:g[y]){// 暴力遍历合并
if(v[x][i]==0&&v[y][i]!=0) g[x].push_back(i);
v[x][i] =v[y][i];
}
Z[y]=0;// 清空
v[y].clear();
g[y].clear();
}
int main(){
n=read(),m=read(),q=read();
fac[0]=1;
for(int i=1;i<=4*400000;i ){
fac[i]=(LL)fac[i-1]*i%mod;// 预处理阶乘
}
for(int x,y,i=1;i<=n;i ){
x=read();y=read();
fa[i]=i;
v[i].clear();
g[i].clear();
g[i].push_back(y);
v[i][y] =x;
Z[i]=x;
}
for(int i=1;i<=m;i ){
E[i].x=read(),E[i].y=read();
}
for(int i=1;i<=q;i ){// 先记录再倒序做
Q[i].op=read();
if(Q[i].op==1){
Q[i].x=read(),Q[i].y=read(),Q[i].z=read();
if(v[Q[i].x][Q[i].z]==0) g[Q[i].x].push_back(Q[i].z);
v[Q[i].x][Q[i].z] =Q[i].y;
Z[Q[i].x] =Q[i].y;
}else if(Q[i].op==2){
Q[i].x=read();
vis[Q[i].x]=1;
}else if(Q[i].op==3){
Q[i].x=read(),Q[i].y=read(),Q[i].z=read();
}
}
for(int i=1;i<=m;i ){// 先连不需要删除的边
if(vis[i]==0) merge(E[i].x,E[i].y);
}
for(int i=q;i>=1;i--){
if(Q[i].op==1){
Q[i].x=getfa(Q[i].x);
v[Q[i].x][Q[i].z]-=Q[i].y;// 减值
Z[Q[i].x]-=Q[i].y;
if(v[Q[i].x][Q[i].z]==0) g[Q[i].x].erase(find(g[Q[i].x].begin(),g[Q[i].x].end(),Q[i].z));// 如果这删完以后是 0 记得删 vector，否则会重复合并
}else if(Q[i].op==2){
merge(E[Q[i].x].x,E[Q[i].x].y);// 连边
}else if(Q[i].op==3){
Q[i].x=getfa(Q[i].x);
A=C=0;A=Z[Q[i].x];C=v[Q[i].x][Q[i].z];
LL tmp1=fac[C]*fac[A-Q[i].y]%mod;
LL tmp2=fac[A]*fac[C-Q[i].y]%mod;
tmp2=fpow(tmp2,mod-2);// 求逆元
LL res=tmp1*tmp2;
res =mod;res%=mod;
ans[i]=res;
}
}
for(int i=1;i<=q;i )
if(Q[i].op==3) write(ans[i]),putchar('n');
} 
