#3124. 「CTS2019 | CTSC2019」氪金手游

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

小刘同学是一个喜欢氪金手游的男孩子。
他最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知:

  • 卡池里总共有 N 种卡,第 i 种卡有一个权值 W_i ,小刘同学不知道 W_i 具体的值是什么。但是他通过和网友交流,他了解到 W_i 服从一个分布。

  • 具体地,对每个 i ,小刘了解到三个参数 p_{i,1},p_{i,2},p_{i,3} W_i 将会以 p_{i,j} 的概率取值为 j ,保证 p_{i,1}+p_{i,2}+p_{i,3}=1

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

\frac{W_i}{\sum_j W_j}

小刘会不停地抽卡,直到他手里集齐了全部 N 种卡。
抽卡结束之后,服务器记录下来了小刘第一次得到每张卡的时间 T_i 。游戏公司在这里设置了一个彩蛋:公司准备了 N−1 个二元组 (u_i,v_i) ,如果对任意的 i ,成立 T_{u_i}<T_{v_i} ,那么游戏公司就会认为小刘是极其幸运的,从而送给他一个橱柜的手办作为幸运大奖。
游戏公司为了降低获奖概率,它准备的这些 (u_i,v_i) 满足这样一个性质:对于任意的 \varnothing\ne S\subsetneq\{1,2,\ldots,N\} ,总能找到 (u_i,v_i) 满足: u_i\in S,v_i\notin S 或者 u_i\notin S,v_i\in S
请你求出小刘同学能够得到幸运大奖的概率,可以保证结果是一个有理数,请输出它对 998244353 取模的结果。

输入格式

第一行一个整数 N ,表示卡的种类数。
接下来 N 行,每行三个整数 a_{i,1},a_{i,2},a_{i,3} ,而题目给出的 p_{i,j}=\frac{a_{i,j}}{a_{i,1}+a_{i,2}+a_{i,3}}
接下来 N−1 行,每行两个整数 u_i,v_i ,描述一个二元组(意义见题目描述)。

输出格式

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

样例

样例输入 1

2
0 0 1
1 1 0
1 2

样例输出 1

524078286

样例解释 1

W_2 \frac 12 的概率取 1 或者 2

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

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

样例 2

见附加文件中的 fgo2.infgo2.ans

数据范围与提示

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

  • 20 分的数据, N\le 15
  • 15 分的数据, N\le 200 ,且每个限制保证 |u_i−v_i|=1
  • 20 分的数据, N\le 1000 ,且每个限制保证 |u_i−v_i|=1
  • 15 分的数据, N\le 200
  • 30 分的数据,无特殊限制。