Expected Diameter
如果你有为竞赛准备题目的经历,下面这个事实可能显得反直觉:从所有有 n 个节点的无根带标号树中均匀随机选一棵,它的期望直径是 Θ(n)。
为什么这很反直觉呢?如果你准备过树上的题目,可能知道一种很简单的随机树生成方式(但它不保证均匀),这里称为“偏斜随机生成器”:
- 对每个 i=2,3,…,n,均匀随机选择一个 1≤j<i,加入边 (i,j)。
- 最后,随机选择 1,2,…,n 的一个排列,用它重新标号所有节点。
这当然并非从全部 nn−2 棵无根带标号树中均匀选择——nn−2 来自 Cayley 公式。但直觉上,你可能认为这个分布已经“足够接近”均匀,应该能给出正确的期望直径。用这个过程生成的树,其期望直径为 Θ(logn)(原作者附注:至少他认为如此)。然而,这个直觉并不正确:偏斜生成器在 nn−2 棵树上产生的分布偏差,足以改变期望直径。
现在用下面这个随机过程来检验这一认识。随机生成一棵有 n 个节点的带权无根带标号树:
- 首先,在全部 nn−2 棵无权无根带标号树中,均匀随机选一棵。特别强调:不使用上面背景介绍的偏斜生成器。
- 然后,对每条边独立赋权:以概率 p1 赋权 1,以概率 p2 赋权 2,其中 p1+p2=1。
给定 n,求这样选出的树的期望直径,并将结果“模 998244353”输出。具体地:
- 令 m=998244353。
- 当 p1,p2 为有理数时,答案也是有理数。
- 将答案约分成 u/v,其中 v>0。
- 在本题的约束下,存在唯一整数 r 满足 0≤r<m 且 rv≡u(modm)。你需要输出这个 r。
定义:
- 有 n 个节点的无根带标号树,是顶点恰为 1,2,…,n 的连通、无环、无向图。
- 带权图的直径,是其中所有简单路径的最大权值。
- 简单路径是一列互不相同的节点 s0,s1,…,sk,相邻节点之间都有边。
- 路径的权值,是它经过的全部边权之和。单节点树的直径为 0。
输入格式
输入只有一行,包含三个整数 n,x,y。概率定义为
p1=yx,p2=1−p1.
约束为 1≤n≤2000,0≤x≤y≤1000,并且上述分式有定义,即 1≤y≤1000。
概率范围说明: p1=x/y 是有定义的有理概率,因此除 0≤x≤y≤1000 外,还须满足 y≥1;0/0 不定义为概率,也不指定相应答案。
输出格式
输出一行一个整数,表示所求期望直径模 998244353 的结果,范围为 [0,998244353)。
原样例 1
2 1 3
665496237
原样例 2
3 2 3
665496238
原样例说明
n=2 时,只有 20=1 棵无权树,以及 2 种带权树。它们的直径分别为 1、2,对应概率为 1/3、2/3,期望直径为 5/3。答案 665496237 是唯一满足 0≤r<998244353 及 3r≡5(mod998244353) 的整数。
n=3 时,有 31=3 棵无权树,以及 12 种带权树。