#P5405. [CTS2019] 氪金手游

[CTS2019] 氪金手游

题目描述

小刘同学是一个喜欢氪金手游的男孩子。

他最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知:

  • 卡池里总共有 NN 种卡,第 ii 种卡有一个权值 WiW_i,小刘同学不知道 WiW_i 具体的值是什么。但是他通过和网友交流,他了解到 WiW_i 服从一个分布。
  • 具体地,对每个 ii,小刘了解到三个参数 pi,1,pi,2,pi,3p_{i,1},p_{i,2},p_{i,3}WiW_i 将会以 pi,jp_{i,j} 的概率取值为 jj,保证 pi,1+pi,2+pi,3=1p_{i,1}+p_{i,2}+p_{i,3}=1

小刘开始玩游戏了,他每次会氪一元钱来抽一张卡,其中抽到卡 ii 的概率为:

WijWj\frac{W_i}{\sum_j W_j}

小刘会不停地抽卡,直到他手里集齐了全部 NN 种卡。

抽卡结束之后,服务器记录下来了小刘第一次得到每张卡的时间 TiT_i。游戏公司在这里设置了一个彩蛋:公司准备了 N1N-1 个二元组 (ui,vi)(u_i,v_i),如果对任意的 ii,成立 Tui<TviT_{u_i}<T_{v_i},那么游戏公司就会认为小刘是极其幸运的,从而送给他一个橱柜的手办作为幸运大奖。

游戏公司为了降低获奖概率,它准备的这些 (ui,vi)(u_i,v_i) 满足这样一个性质:对于任意的 S{1,2,,N}\varnothing\ne S\subsetneq\{1,2,\ldots,N\},总能找到 (ui,vi)(u_i,v_i) 满足:uiS,viSu_i\in S,v_i\notin S 或者 uiS,viSu_i\notin S,v_i\in S

请你求出小刘同学能够得到幸运大奖的概率,可以保证结果是一个有理数,请输出它对 998244353998244353 取模的结果。

输入格式

第一行一个整数 NN,表示卡的种类数。

接下来 NN 行,每行三个整数 ai,1,ai,2,ai,3a_{i,1},a_{i,2},a_{i,3},而题目给出的 pi,j=ai,jai,1+ai,2+ai,3p_{i,j}=\frac{a_{i,j}}{a_{i,1}+a_{i,2}+a_{i,3}}

接下来 N1N-1 行,每行两个整数 ui,viu_i,v_i,描述一个二元组(意义见题目描述)。

输出格式

输出一行一个整数,表示所求概率对 998244353998244353 取模的结果。

2
0 0 1
1 1 0
1 2
524078286

提示

样例 1 解释

W2W_212\frac 12 的概率取 11 或者 22

  • 如果 W2=1W_2=1,那么 T1<T2T_1<T_2 的概率为 34\frac 34
  • 否则 W2=2W_2=2T1<T2T_1<T_2 的概率为 35\frac 35

综合所有情况答案为 $\frac 12\left(\frac 34+\frac 35\right)=\frac{27}{40}$,你可以验证它对 998244353998244353 取模的结果确实是所给答案。

测试数据约定

对于全部的测试数据,保证 N1000N\le 1000ai,j106a_{i,j}\le 10^6

  • 2020 分的数据,N15N\le 15
  • 1515 分的数据,N200N\le 200,且每个限制保证 uivi=1|u_i−v_i|=1
  • 2020 分的数据,N1000N\le 1000,且每个限制保证 uivi=1|u_i−v_i|=1
  • 1515 分的数据,N200N\le 200
  • 3030 分的数据,无特殊限制。