#2125. 氪金手游

    ID: 2125 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTS赛事:contest302来源:qoj.ac数据:公开样例概率期望组合数学

氪金手游

氪金手游

题目描述

第二试氪金手游(fgo) IOI 2019 中国国家队选拔 氪金手游(fgo) 【题目描述】 小刘同学是一个喜欢氪金手游的男孩子。 他最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知: • 卡池里总共有N 种卡,第i 种卡有一个权值Wi,小刘同学不知道Wi 具体的值 是什么。但是他通过和网友交流,他了解到Wi 服从一个分布。 • 具体地,对每个i ,小刘了解到三个参数pi,1, pi,2, pi,3,Wi 将会以pi,j 的概率取 值为j,保证pi,1 + pi,2 + pi,3 = 1。 小刘开始玩游戏了,他每次会氪一元钱来抽一张卡,其中抽到卡i 的概率为: Wi ∑ . j Wj 小刘会不停地抽卡,.直.到他手里集齐了全部N 种卡。 抽卡结束之后,服务器记录下来了小刘.第.一.次得到每张卡的时间{Ti}。游戏公司 在这里设置了一个彩蛋:公司准备了N −1 个二元组(ui, vi),如果对任意的i,成立 Tui < Tvi,那么游戏公司就会认为小刘是极其幸运的,从而送给他一个橱柜的手办作为 幸运大奖。 游戏公司为了降低获奖概率,它准备的这些(ui, vi) 满足这样一个性质:对于任意 的∅, S ⊊{1, 2, . . . , N},总能找到(ui, vi) 满足:ui ∈S, vi < S .或.者ui < S, vi ∈S . 请你求出小刘同学能够得到幸运大奖的概率,可以保证结果是一个有理数,请输出 它对998244353 取模的结果。 【输入格式】 从文件fgo.in 中读入数据。 第一行一个整数N,表示卡的种类数。 ai,j 接下来N 行,每行三个整数ai,1, ai,2, ai,3,而题目给出的pi,j = ai,1+ai,2+ai,3 . 接下来N −1 行,每行两个整数ui, vi,描述一个二元组(意义见题目描述)。 【输出格式】 输出到文件fgo.out 中。 输出一行一个整数,表示所求概率对998244353 取模的结果。 【样例1 输入】 2 0 0 1 第8 页 共9 页 第二试氪金手游(fgo) IOI 2019 中国国家队选拔 1 1 0 1 2 【样例1 输出】 524078286 【样例1 解释】 W2 以1 2 的概率取1 或者2: • 如果W2 = 1,那么T1 < T2 的概率为3 4。 • 否则W2 = 2,T1 < T2 的概率为3 5。 ( ) 综合所有情况答案为1 40,你可以验证它对998244353 取模的结果确实 3 4 + 3 = 27 2 5 是所给答案。 【样例2】 见选手目录下的fgo/fgo2.in 与fgo/fgo2.ans。 【测试数据约定】 对于全部的测试数据,保证N ≤1000,ai,j ≤106 . • 20 分的数据,N ≤15 。 • 15 分的数据,N ≤200 ,且每个限制保证|ui −vi| = 1。 • 20 分的数据,N ≤1000,且每个限制保证|ui −vi| = 1。 • 15 分的数据,N ≤200。 • 30 分的数据,无特殊限制。 第9 页 共9 页

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

2
0 0 1
1 1 0
1 2
524078286

样例 2

15
6 8 9
5 8 8
9 9 6
7 10 9
4 2 2
5 7 3
0 9 10
2 3 6
7 4 4
5 9 6
1 4 3
0 9 1
6 5 10
1 2 9
9 4 10
14 9
2 3
6 7
9 10
8 3
11 10
2 5
13 15
2 1
9 5
4 1
6 1
9 13
9 12
610532288