[JZOJ5987] 仙人掌毒题

Solution

套路题...

全他娘的是套路...

首先如何处理仙人掌，可以在线拿 \(lct\) 维护，或者离线之后树剖。（\(lct\) 维护太毒了写不来，就离线树剖了又好写又不用调

离线树剖的意思就是按加边时间为权值建出一棵最小生成树（或者生成森林），这就是最终的仙人掌的一棵生成树了。

加边的时候如果这是条树边那就直接加上，如果不是树边，那就在线段树上查一下这个环是否有边被覆盖，只要有一条边被覆盖那就不满足仙人掌性质，那就不能加这条边进去，否则加进去然后线段树区间赋值就好了。

然后怎么求期望联通块数？

如果这是个森林的话，期望联通块数=期望点数-期望边数

那要是个沙漠呢？

考虑一下森林的这个式子是怎么来的，就是最开始有点数个联通块，然后每加一条边就合并两个联通块，所以是点数-边数。

那放到仙人掌上，发现每条形成环的非树边都被多减了一次，那再加回来就好了。而成环的非树边就恰好等于仙人掌的环数，因为一条边最多只会出现在一个环里。所以沙漠的期望联通块数=期望点数-期望边数+期望环数。

然后分开考虑就好了，因为点还有颜色，那我们规定一条边是白的当且仅当两端点都是白色，一个环是白的当且仅当环上的所有点都是白色。黑色同理。

先算点数。根据期望的线性性，一个点是白色点的概率就是 \((\frac{n-1}n)^t\)，那对期望的贡献就是 \(1\cdot (\frac{n-1}n)^t\) ，黑色点拿 \(1\) 减一下就行了。

再算边数。一条边是白色边的概率是 \((\frac{n-2}n)^t\) ，是黑色边的概率容斥一下，就是 \(2\cdot(1-(\frac{n-1}n)^t)-(1-(\frac{n-2}n)^t)=1+(\frac{n-2}n)^t-2\cdot (\frac{n-1}n)^t\) ，含义画一个Venn图就很清楚了。

然后是环数，白色环的概率很好算，就是 \((\frac{n-len}n)^t\)，其中 \(len\) 是环长。那黑色环呢，也是容斥一下，枚举至少有 \(j\) 个白点，所以 \(f(len)=\sum\limits_{j=0}^{len} (-1)^j \cdot C_{len}^j\cdot (\frac{n-j}n)^t\) 。

嗯然后就做完了。

Code #pragma GCC optimize(2) #include<bits/stdc++.h> using std::swap; typedef long long ll; #define int long long const int N=3e5+5; const int mod=998244353; int n,m,t,w; int fac[N],ifac[N]; int cnt,head[N],is[N]; int father[N],ques[N][2]; struct Edge{ int to,nxt; }edge[N<<1]; void add(int x,int y){ edge[++cnt].to=y; edge[cnt].nxt=head[x]; head[x]=cnt; } namespace slpf{ #define ls x<<1 #define rs x<<1|1 #define lss ls,l,mid,ql,qr #define rss rs,mid+1,r,ql,qr int sze[N],son[N],fa[N]; int flag[N<<2],sum[N<<2]; int tot,dfn[N],top[N],d[N]; void dfs(int now){ sze[now]=1; for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(sze[to]) continue; fa[to]=now;d[to]=d[now]+1; dfs(to);sze[now]+=sze[to]; son[now]=sze[to]>sze[son[now]]?to:son[now]; } } void dfs2(int now,int low){ dfn[now]=++tot;top[now]=low; if(son[now]) dfs2(son[now],low); for(int i=head[now];i;i=edge[i].nxt){ int to=edge[i].to; if(dfn[to]) continue; dfs2(to,to); } } void pushup(int x){ sum[x]=sum[ls]|sum[rs]; } void pushdown(int x){ if(!flag[x]) return; flag[ls]=flag[rs]=sum[ls]=sum[rs]=1; flag[x]=0; } void modify(int x,int l,int r,int ql,int qr){ if(ql<=l and r<=qr) return flag[x]=sum[x]=1,void(); pushdown(x);int mid=l+r>>1; if(ql<=mid) modify(lss); if(mid<qr) modify(rss); pushup(x); } int query(int x,int l,int r,int ql,int qr){ if(ql<=l and r<=qr) return sum[x]; pushdown(x);int mid=l+r>>1,ans=0; if(ql<=mid) ans|=query(lss); if(mid<qr) ans|=query(rss); return ans; } int ask(int x,int y){ int ans=0; while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); ans|=query(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]<d[y]) swap(x,y); if(x!=y) ans|=query(1,1,n,dfn[y]+1,dfn[x]); return ans; } int change(int x,int y){ while(top[x]!=top[y]){ if(d[top[x]]<d[top[y]]) swap(x,y); modify(1,1,n,dfn[top[x]],dfn[x]); x=fa[top[x]]; } if(d[x]<d[y]) swap(x,y); if(x!=y) modify(1,1,n,dfn[y]+1,dfn[x]); return y; } } int ksm(int a,int b=mod-2,int ans=1){ while(b){ if(b&1) ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int getint(){ int X=0,w=0;char ch=getchar(); while(!isdigit(ch))w|=ch=='-',ch=getchar(); while( isdigit(ch))X=X*10+ch-48,ch=getchar(); if(w) return -X;return X; } int find(int x){ return father[x]==x?x:father[x]=find(father[x]); } int dec(int x,const int &y){ return x-y<0?x-y+mod:x-y; } int C(int n,int m){ return fac[n]*ifac[m]%mod*ifac[n-m]%mod; } signed main(){ freopen("cactus.in","r",stdin);freopen("cactus.out","w",stdout); gi(n),gi(m),gi(t),gi(w); fac[0]=ifac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod; ifac[n]=ksm(fac[n]); for(int i=n-1;i;i--) ifac[i]=ifac[i+1]*(i+1)%mod; for(int i=1;i<=n;i++) father[i]=i; int invn=ksm(ksm(n),t),baid=ksm(n-1,t)*invn%mod,baib=ksm(n-2,t)*invn%mod,heib=(baib-baid*2%mod+1+mod)%mod; for(int i=1;i<=m;i++){ gi(ques[i][0]),gi(ques[i][1]); int r1=find(ques[i][0]),r2=find(ques[i][1]); if(r1!=r2) father[r1]=r2,is[i]=1,add(ques[i][0],ques[i][1]),add(ques[i][1],ques[i][0]); } for(int i=1;i<=n;i++) if(!slpf::dfn[i]) slpf::d[i]=1,slpf::dfs(i),slpf::dfs2(i,i); int ans=(w==1?n:baid*n%mod); for(int i=1;i<=m;i++){ if(is[i]){ ans=dec(ans,baib); if(w==1) ans=dec(ans,heib); } else{ if(!slpf::ask(ques[i][0],ques[i][1])){ int z=slpf::change(ques[i][0],ques[i][1]); ans=dec(ans,baib); if(w==1) ans=dec(ans,heib); int len=slpf::d[ques[i][0]]+slpf::d[ques[i][1]]-slpf::d[z]*2+1; (ans+=ksm(n-len,t)*invn%mod)%=mod; if(w==1){ int res=0; for(int j=0;j<=len;j++) (res+=(j&1?mod-C(len,j):C(len,j))*ksm(n-j,t)%mod*invn%mod)%=mod; (ans+=res)%=mod; } } } print(ans),putc('\n'); } return io::flush(),0; }