TopCoder

fatman
2024北市賽rk.4不是我

User's AC Ratio

52.6% (10/19)

Submission's AC Ratio

20.2% (22/109)

Tags

Description

有一天建國中學的中餅在大掃除時意外發現了「中卷遊戲」的入場券,於是他與國中同學中明一同前往中巨蛋觀看比賽。
中餅和中明從主持人口中得知總共有 n 個參賽者,編號為 1n,編號 i1in) 的參賽者養了 mi 隻中卷,這些中卷因為有中二病,所以會魔法,第 j1jmi)隻中卷的魔力值為 ai,j

在整個「中卷遊戲」中會有 q 次決鬥,每次決鬥會由編號 x 與編號 y 的參賽者對戰(xy)。
編號 x 的參賽者會從 mx 隻中卷裡挑出一隻中卷,每隻被挑到的機率都是 1mx;編號 y 的參賽者則會從 my 隻中卷裡挑出一隻,每隻被挑到的機率是 1my

若參賽者 x,y 分別挑出了魔力值為 A,B 的中卷,那這兩隻中卷會進行魔力的比拼,如果 A>B,代表參賽者 x 的中卷比較會魔法,那這輪參賽者 x 獲勝,否則為平手或參賽者 x 落敗。
所謂贏了有獎金,沒贏沒獎金,若此次決鬥參賽者 x 獲勝了,那他能獲得 BA 元的獎金,否則獲得 0 元。

中餅因為覺得比賽太無聊了,所以想計算每次決鬥參賽者 x 能拿到獎金的期望值 E 是多少,請在每次的決鬥,輸出 E mod 998244353

E 化成最簡分數為 PQ,那麼輸出 E mod 998244353 代表要輸出 PQ1 mod 998244353Q1Q 的模逆元,滿足 QQ11 (mod 998244353))。
保證 E 為有理數,且不會出現 Q0 (mod 998244353) 的情況。

Input Format

第一行有兩個正整數 n,q,代表參賽者數量與有幾次決鬥。
接下來 n 行,第 i 行的第一個正整數為 mi,代表編號 i 的參賽者養了幾隻中卷,同一行接著會有 mi 個正整數 ai,1ai,mi,代表每隻中卷的魔力值。
接下來 q 行,每行有兩個正整數 x,y,代表此次決鬥的參賽者編號。

對於所有測試資料:

  • 2n105
  • 1q105
  • 1mi105
  • i=1nmi2×105
  • 1ai,j<998244353
  • 1x,yn,xy

Output Format

每次決鬥,輸出參賽者 x 能拿到獎金的期望值 E mod 998244353

Sample Input 1

2 2
2 3 1
3 2 2 1
1 2
2 1

Sample Output 1

610038216
166374059

Sample Input 2

4 12
5 15 6 9 5 12
5 13 15 10 9 16
6 1 14 5 14 3 8
4 7 13 15 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

Sample Output 2

471836831
677881860
641371997
736862175
89482937
679206098
201431450
979230175
731996343
845070522
174820742
2513894

Hints

在範例測資一中,第一次決鬥 x=1,y=2,參賽者 1 可以拿到獎金的期望值 E5185×1815×720954255610038216 (mod 998244353),故輸出 610038216

第二次決鬥 x=2,y=1,參賽者 2 可以拿到獎金的期望值 E16
61166374059 (mod 998244353),故輸出 166374059

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~6 mi10 21
3 0, 2, 7~9 q10 28
4 0~50 無其他限制 51

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 2 3 4
1 3000 524288 65536 1 2 4
2 3000 524288 65536 2 3 4
3 3000 524288 65536 2 4
4 3000 524288 65536 2 4
5 3000 524288 65536 2 4
6 3000 524288 65536 2 4
7 3000 524288 65536 3 4
8 3000 524288 65536 3 4
9 3000 524288 65536 3 4
10 3000 524288 65536 4
11 3000 524288 65536 4
12 3000 524288 65536 4
13 3000 524288 65536 4
14 3000 524288 65536 4
15 3000 524288 65536 4
16 3000 524288 65536 4
17 3000 524288 65536 4
18 3000 524288 65536 4
19 3000 524288 65536 4
20 3000 524288 65536 4
21 3000 524288 65536 4
22 3000 524288 65536 4
23 3000 524288 65536 4
24 3000 524288 65536 4
25 3000 524288 65536 4
26 3000 524288 65536 4
27 3000 524288 65536 4
28 3000 524288 65536 4
29 3000 524288 65536 4
30 3000 524288 65536 4
31 3000 524288 65536 4
32 3000 524288 65536 4
33 3000 524288 65536 4
34 3000 524288 65536 4
35 3000 524288 65536 4
36 3000 524288 65536 4
37 3000 524288 65536 4
38 3000 524288 65536 4
39 3000 524288 65536 4
40 3000 524288 65536 4
41 3000 524288 65536 4
42 3000 524288 65536 4
43 3000 524288 65536 4
44 3000 524288 65536 4
45 3000 524288 65536 4
46 3000 524288 65536 4
47 3000 524288 65536 4
48 3000 524288 65536 4
49 3000 524288 65536 4
50 3000 524288 65536 4