P3412 仓鼠找sugar II

    • 90通过
    • 323提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 期望 概率论,统计 洛谷原创
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    小仓鼠的和他的基(mei)友(zi)sugar住在地下洞穴中,每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a,是任意的)他的基友卧室(b,还是任意的)。(注意,a有可能等于b。)然而小仓鼠学OI学傻了,不知道怎么怎么样才能最短的走到目的地。于是他只能随便乱走。当他在每一个节点时,等概率到这个点的母亲或者所有孩子节点(例如这个节点有一个母亲节点和两个子节点,那么下一步走到这3个节点的概率都是1/3)。一但走到了他基友的卧室,就会停下。

    现在小仓鼠希望知道,他走到目的地时,走的步数的期望。这个期望本来是一个有理数,但是为了避免误差,我们要求对这个有理数取模,%998244353。

    下面是“分数”模运算的定义:

    b, m互质

    k = a/b (mod m) <=> kb = a (mod m)

    这里求 x = 1/17 (mod 2668)

    <=>
    17x = 1 (mod 2668)
    <=>
    17x = 2668k + 1 (k∈整数)

    取合适的k使得17|(2668k+1) 这里刚好17 | (2668 + 1)

    所以k = 1, x = (2668+1)/17 = 157

    当然,当k = 1 + 17n 时,

    x = (2668 + 17·n·2668 + 1)/17 = 157 + 2668n

    也符合条件(n任意整数)

    但如果限定 2668 > x > 0,x是唯一的。

    小仓鼠那么弱,还要天天被JOHNKRAM大爷虐,请你快来救救他吧!

    输入输出格式

    输入格式:

    第一行一个正整数n,表示这棵树节点的个数。

    接下来n-1行,每行两个正整数u和v,表示节点u到节点v之间有一条边。

    输出格式:

    一个整数,表示取模后的答案。

    输入输出样例

    输入样例#1: 复制
    3
    1 2
    1 3
    
    输出样例#1: 复制
    110916041

    说明

    对于30%的数据 n<=5;

    对于50%的数据 n<=5000;

    对于所有数据 n<=100000。

    样例解释

    期望是16/9

    如果a在叶子 b在根,E1=1。有2种情况。

    如果a在根,b在叶子。E2=1/2+3*1/4+5*1/8...=3。有2种情况。

    如果a和b都在不同的叶子,E3=E2+1。有2种情况。

    如果a=b,E4=0,有3种情况。

    所以期望是16/9,有理数取模后就是输出。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。