专栏文章

ARC150D Removing Gacha 题解

CCoffee_zzz/xin
AT_arc150_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minmf7cf
此快照首次捕获于
2025/12/02 04:47
3 个月前
此快照最后确认于
2025/12/02 04:47
3 个月前
查看原文
显然总期望操作次数等于每个点期望操作次数之和，于是考虑对于每个点 uu，计算点 uu 被操作次数的期望。
设点 uu 的深度为 dud_u，那么点 uu 是否还需要被操作只和点 uu 到根路径上的 dud_u 个点的状态有关，所以我们可以只考虑这 dud_u 个点。
于是现在问题转化为了，有 dud_u 个点，每次随机选择一个点，直到每个点都被选择过为止，求第 dud_u 个点被选择次数的期望。
设当前已经选择了 kk 个点，那么有 du−kdu\frac {d_u-k}{d_u} 的概率选择到一个新点，也就是期望 dudu−k\frac {d_u}{d_u-k} 次选择到一个新点。相加可以得到总的期望选择次数等于 ∑k=0du−1dudu−k=du∑k=1du1k\sum\limits_{k=0}^{d_u-1}\frac {d_u}{d_u-k}=d_u\sum\limits_{k=1}^{d_u}\frac {1}{k}，而每个点被选择到的概率相等，所以第 dud_u 个点期望被选择 ∑k=1du1k\sum\limits_{k=1}^{d_u}\frac {1}{k} 次。
将所有点期望操作次数相加，得到答案为 ∑u=1n∑k=1du1k\sum\limits_{u=1}^n \sum\limits_{k=1}^{d_u}\frac {1}{k}。直接计算即可，时间复杂度 O(n)\mathcal O(n)。
C
const int N=2e5+5,mod=998244353;
int n,p[N],d[N],ans,fac[N],infac[N],inv[N],pre[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 solve(){
	cin>>n;
	for(int i=2;i<=n;i++) cin>>p[i];
	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>0;i--) infac[i]=1ll*infac[i+1]*(i+1)%mod;
	for(int i=1;i<=n;i++) inv[i]=1ll*fac[i-1]*infac[i]%mod;
	for(int i=1;i<=n;i++) pre[i]=(pre[i-1]+inv[i])%mod;
	for(int i=1;i<=n;i++) d[i]=d[p[i]]+1,ans=(ans+pre[d[i]])%mod;
	cout<<ans<<endl;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...