竞赛讨论区 > 牛客网练习赛23F托米的游戏题解
头像
Stump
编辑于 2018-07-28 21:25
+ 关注

牛客网练习赛23F托米的游戏题解

题意:
给定n个点的一棵树,根为1。每次操作随机选点,把选中的点的子树删去。当所有点被删去则停止。求操作次数的期望。
思路:
按照套路,根据期望的线性性,和的期望等于期望的和,
,期望步数可以等价于对每个点的期望贡献单独算后求和。
考虑一个点被删除时只有两种情况(默认根的深度为1):
(1).选中自己被删除,此时贡献为1,概率为
(2).选中该点的祖先,此时贡献为0,贡献应该被算在祖先处,概率为
PS:删除其他点并不会导致该点被删除,不会对它的概率产生影响。
因此单点的期望贡献为
所以
复杂度O(nlog mod),dfs求出所有点的深度,再求一下乘法逆元
内容板块
数学 :期望 乘法逆元

#include<cstdio>
#define rep(i,s,t) for(register int i=s;i<=t;++i)
#include<vector>
using namespace std;
const int N=100005,mod=998244353;
vector<int>to[N];
inline int fp(int a,int b){  int res=1;
    for(;b;b>>=1,a=1ll*a*a%mod)
        if(b&1)
            res=1ll*res*a%mod;  return res;
}
int dep[N],n;
inline void dfs(int u,int fa,int deep){
    dep[u]=deep;
    for(auto v:to[u]){
        if(v==fa)continue;
     dfs(v,u,deep+1);  }
}
#define pb push_back
int main(){
    scanf("%d",&n);
    rep(i,2,n){  int x,y;
          scanf("%d%d",&x,&y);
          to[x].pb(y),to[y].pb(x);
      }
      dep[1]=1;
    dfs(1,1,1);
    int ans=0;
    rep(i,1,n)
        ans=(ans+fp(dep[i],mod-2))%mod;
    printf("%d\n", ans);
    return 0;
}

全部评论

(2) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐