410709: GYM104081 J 瑞士轮

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

J. 瑞士轮time limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

​在一些竞技性比赛中,常在队伍数量较多时采用瑞士轮赛制,既保证了一定的公平稳定性,又让赛程不至于太长。

​YahAHa 最近在观看一个瑞士轮赛制的竞技比赛,这个比赛共有 32 支队伍,每个队伍按 1 到 32 编号。所有队伍的积分都可以表示成 $$$x - y$$$ 的形式,表示累计 $$$x$$$ 个胜场和 $$$y$$$ 个负场,一开始所有队伍的积分都是 0 - 0 。比赛有若干轮,若一支队伍累计积满 2 个胜场,将直接晋级,不再参与后续比赛;同样若累计积满 2 个负场,将直接淘汰,也不再参与后续比赛。

​在比赛的每一轮中,同一种积分的队伍按编号排序,例如在第 R 轮中,1 - 1 的队伍有 $$$2N$$$ 支,将他们按编号排序后,第 1 和 第 2、第 3 和 第 4 、…… 、第 $$$2N-1$$$ 和 第 $$$2N$$$ ,各进行一场比赛。保证 32 支队伍按这样的规则进行比赛,每一轮中每一种积分的队伍数都是偶数,且最终会有 16 支队伍晋级。

​单纯这样的比赛当然不够刺激,于是比赛方出了一个竞猜活动。如果要参与竞猜,要提交一份竞猜表,竞猜表包含三个部分,第一部分和第二部分要各填入 1 个队伍,第三部分要填入 7 个队伍。三个部分总共要填入 9 支队伍,并且这 9 支队伍互不相同。

​当第一部分中的队伍 2-0 晋级时,算作正确预测。

​当第二部分中的队伍 0-2 淘汰时,算作正确预测。

​第三部分的队伍,每有一个晋级(最终得分为 2-0 或 2-1 ),就算作一个正确预测。 一个竞猜表的正确预测队伍数量,是其三个部分的正确预测数量之和。

​每个队伍有一个实力值 $$$a_i$$$ ,如果第 $$$i$$$ 支队伍和第 $$$j$$$ 支队伍对阵比赛,第 $$$i$$$ 支队伍有 $$$a_i/(a_i+a_j)$$$ 的概率获胜,第 $$$j$$$ 支队伍有 $$$a_j/(a_i+a_j)$$$ 的概率获胜。YahAHa 对竞猜非常谨慎,他现在有好几份竞猜表,他想问问聪明的你,每一个竞猜表正确预测队伍数量的期望。为防止精度误差,请输出期望对 $$$998,244,353$$$ 取模的结果。

Input

一开始四行,每行 8 个数,第 $$$i$$$ 个数 $$$a_i(1\leq a_i< 998,244,353)$$$ 表示编号为 $$$i$$$ 的队伍的实力值。保证对于任意不相等的 $$$i,j$$$,$$$a_i+a_j\neq 998,244,353$$$。

接下来一行一个数 $$$m(1\leq m\leq 10^5)$$$ 表示竞猜表的数量。

接下来 $$$m$$$ 行,每行 9 个数,第一个数表示第一部分预测队伍的编号,第二个数表示第二部分预测队伍的编号,接下来 7 个数表示第三部分预测队伍的编号。保证对于任意的 $$$b_i$$$, $$$1\leq b_i\leq 32$$$ 。

Output

一共 $$$m$$$ 行,第 $$$i$$$ 行一个整数 $$$x_i$$$ 表示第 $$$i$$$ 份竞猜表的正确预测数量的期望。

ExamplesInput
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1
1
1 2 3 4 5 6 7 8 9
Output
4
Input
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
4
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27
28 29 30 31 32 1 2 3 4
Output
526205442
233631779
899336506
198951272

加入题单

上一题 下一题 算法标签: