ARC150D Removing Gacha 题解

Coffee_zzz · 2025-10-13 09:15:23 · 题解

显然总期望操作次数等于每个点期望操作次数之和，于是考虑对于每个点 u，计算点 u 被操作次数的期望。

设点 u 的深度为 d_u，那么点 u 是否还需要被操作只和点 u 到根路径上的 d_u 个点的状态有关，所以我们可以只考虑这 d_u 个点。

于是现在问题转化为了，有 d_u 个点，每次随机选择一个点，直到每个点都被选择过为止，求第 d_u 个点被选择次数的期望。

设当前已经选择了 k 个点，那么有 \frac {d_u-k}{d_u} 的概率选择到一个新点，也就是期望 \frac {d_u}{d_u-k} 次选择到一个新点。相加可以得到总的期望选择次数等于 \sum\limits_{k=0}^{d_u-1}\frac {d_u}{d_u-k}=d_u\sum\limits_{k=1}^{d_u}\frac {1}{k}，而每个点被选择到的概率相等，所以第 d_u 个点期望被选择 \sum\limits_{k=1}^{d_u}\frac {1}{k} 次。

将所有点期望操作次数相加，得到答案为 \sum\limits_{u=1}^n \sum\limits_{k=1}^{d_u}\frac {1}{k}。直接计算即可，时间复杂度 \mathcal O(n)。

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;
}