提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

YbtOJ 735「动态树」毒瘤染色

动态 YbtOJ 染色
2023-06-13 09:12:49 时间

YbtOJ 735「动态树」毒瘤染色

题目链接：YbtOJ #735

对于一个无向图，若图中的每条边 至多处于一个无向环中，则称这个图为一个 毒瘤图。

小 A 有一个图 G，初始包含 n 个点，没有边。显然它是一个毒瘤图。

接下来小 A 会进行 q 次操作，每次操作给出两个正整数 x,y，要求判断往 G 中加入 (x,y) 后该图是否仍然是毒瘤图，若是则加入这条边，否则不加入。

在所有操作进行前，小 A 会确定一个非负整数 k。在每次操作后，小 A 都会针对当前图进行询问：假设初始所有点为白色，进行 k 次染色，每次等概率随机选择一个点将它染成黑色（一个点可能被重复选择多次），求 k 次染色后图中 仅保留白点时的连通块个数+仅保留黑点时的连通块个数 的 期望值（向 998244353 取模）。

为了让你有更多的得分空间，小 A 还会给定一个辅助变量 \omega。若 \omega=1，你需要回答上述询问。若 \omega=0，对于每次询问你只需要求出 仅保留白点时的连通块个数 的 期望值。

因为一些奇怪的原因，本题 强制在线。

1\le n\le10^5，1\le q\le 3\times10^5，0\le k\le 10^9。

Solution

在仙人掌中，连通块个数=点数-边数+环数

由于期望的线性性，E(连通块个数)=E(点数)-E(边数)+E(环数)

所以将权值为 0 的点与 1 的点分开求期望即可。

下面不妨称权值为 0 为白点，1 为黑点。

点

一个点为白点概率为 (\frac{n-1}n)^k。

一个点为黑点概率为 1-(\frac{n-1}n)^k。

边

一条边为白边的概率为 (\frac{n-2}n)^k。

一条边为黑边的概率为 1-Pr(x \text{为白点})-Pr(y \text{为白点})+Pr(x \text{为白点且}y\text{为白点})=1-2(\frac{n-1}n)^k+(\frac{n-2}n)^k。

环

一个大小为 m 的白环的概率为 (\frac{n-m}n)^k。

一个大小为 m 的黑环的概率有两种做法：

法一：分治 NTT

设 f_i 表示大小为 i 的环在 k 次操作后全黑的概率，g_i 表示包含 i 个点的集合在 k 次操作后全白的概率。

。

f_i=1-Pr(\text{不是全黑})=1-\sum_{j=0}^{i-1}f_jg_{i-j}\binom ij

直接分治 NTT 就可以 O(n\log^2n) 求出 f_i。

法二：容斥

f_m=\sum_{i=0}^m(-1)^i\binom mi(\frac{n-i}n)^k

其中 i 枚举的是环中至少有 i 个白点，由于所有环只算一次，于是这部分复杂度为 O(\sum m\log k)=O(n\log k)。

Code

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define LL long long
#define Cn const
#define CI Cn int&
using namespace std;
namespace Debug{
    Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
    Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
    Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
    #define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
    #define FS 100000
    #define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
    #define pc(c) (FC==FE&&(clear(),0),*FC++=c)
    int OT;char oc,FI[FS],FO[FS],OS[FS],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
    I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
    Tp I void read(Ty& x) {x=0;RI f=1;W(!isdigit(oc=tc())) f=oc^'-'?1:-1;W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));x*=f;}
    Ts I void read(Ty& x,Ar&... y) {read(x),read(y...);}
    Tp I void write(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);}
    Tp I void writeln(Ty x) {x<0&&(pc('-'),x=-x);W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
Cn int N=5e3+10;
int T,p,n,Ans,fac[N],ifac[N],g[N],f[N],s[N];
I int QP(RI a,RI b){if(b<0) return 0;RI s=1;W(b) b&1&&(s=1LL*s*a%p),a=1LL*a*a%p,b>>=1;return s;}
I int C(CI n,CI m){return n<m?0:1LL*fac[n]*ifac[n-m]%p*ifac[m]%p;}
int main(){
    freopen("forest.in","r",stdin),freopen("forest.out","w",stdout);
    RI i,j,o;read(T,p);for(fac[0]=1,i=1;i<N;i++) fac[i]=1LL*fac[i-1]*i%p;for(ifac[N-1]=QP(fac[N-1],p-2),i=N-2;~i;i--) ifac[i]=1LL*ifac[i+1]*(i+1)%p;
    for(f[1]=1,i=2;i<N;i++) f[i]=QP(i,i-2)%p;
    for(g[0]=1,i=1;i<N;i++) for(j=1;j<=i;j++) g[i]+=1LL*C(i-1,j-1)*g[i-j]%p*f[j]%p,g[i]%=p;
    for(i=2;i<N;i++) for(o=1,j=i-1;j;j--) s[i]+=1LL*C(i-2,j-1)*o%p*j%p*j%p,s[i]%=p,o=1LL*o*(i-1)%p;W(T--){
        for(read(n),Ans=0,i=1;i<=n;i++) Ans+=1LL*C(n-1,i-1)*g[n-i]%p*s[i]%p,Ans%=p;
        writeln(1LL*Ans*n%p);
    }return clear(),0;
}

相关文章