ARC165E Random Isolation 题解

由于每个点最多只会被删除一次，且每个连通块不会增大，所以可以将题意转化为：随机一个排列

p

，从

1

到

n

依次考虑每个点

p_i

，如果点

p_i

所处的连通块大小大于

k

则删除点

p_i

，否则不进行操作，求期望删除次数。

设

P(G)

表示原树的子图

G

作为一个完整的连通块的出现概率。如果图

G

包含大于

k

个点，那么当图

G

作为一个完整的连通块出现时，一定会进行恰好一次删除操作。所以，期望删除次数就等于每个包含大于

k

个点的子图

G

作为一个完整的连通块的出现概率之和，即

\sum\limits_{|G|>k} P(G)

。

接下来考虑怎么计算

P(G)

。设图

G

包含

a

个点，原树中有

b

个点与图

G

中的点相连，那么要求只有这

b

个点在排列中的顺序均在这

a

个点前，所以

P(G)

等于

\dfrac{a!b!}{(a+b)!}

。

于是可以进行树形 dp：设

f_{u,i,j}

表示，满足图

G

中深度最小的点为

u

，包含

i

个点，以

u

为根的子树中有

j

个点与图

G

中的点相连的原树的子图

G

的数量。直接从儿子处转移即可。

时间复杂度

\mathcal O(n^4)

。

const int N=105,mod=998244353;
int n,k,siz[N],fac[N],infac[N],f[N][N][N],g[N][N],ans;
vector <int> ve[N];
int ksm(int a,int b){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%mod;
		b>>=1;
		a=1ll*a*a%mod;
	}
	return res;
}
void add(int &a,int b){
	a+=b;
	if(a>=mod) a-=mod;
}
int ad(int a,int b){
	a+=b;
	if(a>=mod) a-=mod;
	return a;
}
void dfs(int u,int fa){
	f[u][1][0]=1,siz[u]=1;
	for(auto v:ve[u]){
		if(v==fa) continue;
		dfs(v,u);
		memset(g,0,sizeof g);
		for(int i=0;i<=siz[u];i++) for(int j=0;i+j<=siz[u];j++) for(int p=0;p<=siz[v];p++) for(int q=0;p+q<=siz[v];q++) add(g[i+p][j+q],1ll*f[u][i][j]*f[v][p][q]%mod);	
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];i++) for(int j=0;j<=siz[u];j++) f[u][i][j]=g[i][j];
	}
	f[u][0][1]=1;
}
void solve(){
	cin>>n>>k;
	for(int i=1,u,v;i<n;i++) cin>>u>>v,ve[u].pb(v),ve[v].pb(u);
	fac[0]=infac[0]=1;
	for(int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%mod;
	infac[n]=ksm(fac[n],mod-2);
	for(int i=n-1;i>=1;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
	dfs(1,0);
	for(int u=1;u<=n;u++){
		for(int i=k+1;i<=siz[u];i++){
			for(int j=0;i+j<=siz[u];j++){
				int p=j+(u!=1);
				add(ans,1ll*f[u][i][j]*fac[i]%mod*fac[p]%mod*infac[i+p]%mod);
			}
		}
	}
	cout<<ans<<endl;
}

ARC165E Random Isolation 题解

文章操作

相关推荐

评论

ARC165E Random Isolation 题解