2316 . 中卷遊戲
TopCoder
Tags
Description
有一天建國中學的中餅在大掃除時意外發現了「中卷遊戲」的入場券，於是他與國中同學中明一同前往中巨蛋觀看比賽。
中餅和中明從主持人口中得知總共有 $n$ 個參賽者，編號為 $1\sim n$，編號 $i$（$1\leq i\leq n$） 的參賽者養了 $m_i$ 隻中卷，這些中卷因為有中二病，所以會魔法，第 $j$（$1\leq j\leq m_i$）隻中卷的魔力值為 $a_{i,j}$。
在整個「中卷遊戲」中會有 $q$ 次決鬥，每次決鬥會由編號 $x$ 與編號 $y$ 的參賽者對戰（$x\neq y$）。
編號 $x$ 的參賽者會從 $m_x$ 隻中卷裡挑出一隻中卷，每隻被挑到的機率都是 $\frac{1}{m_x}$；編號 $y$ 的參賽者則會從 $m_y$ 隻中卷裡挑出一隻，每隻被挑到的機率是 $\frac{1}{m_y}$。
若參賽者 $x,y$ 分別挑出了魔力值為 $A,B$ 的中卷，那這兩隻中卷會進行魔力的比拼，如果 $A>B$，代表參賽者 $x$ 的中卷比較會魔法，那這輪參賽者 $x$ 獲勝，否則為平手或參賽者 $x$ 落敗。
所謂贏了有獎金，沒贏沒獎金，若此次決鬥參賽者 $x$ 獲勝了，那他能獲得 $\frac{B}{A}$ 元的獎金，否則獲得 $0$ 元。
中餅因為覺得比賽太無聊了，所以想計算每次決鬥參賽者 $x$ 能拿到獎金的期望值 $E$ 是多少，請在每次的決鬥，輸出 $E\text{ mod }998244353$。
若 $E$ 化成最簡分數為 $\frac{P}{Q}$，那麼輸出 $E\text{ mod }998244353$ 代表要輸出 $PQ^ {-1}\text{ mod }998244353$（$Q^ {-1}$ 為 $Q$ 的模逆元，滿足 $QQ^ {-1}≡1\ (\text{mod }998244353)$）。
保證 $E$ 為有理數，且不會出現 $Q≡0\ (\text{mod }998244353)$ 的情況。
Input Format
第一行有兩個正整數 $n,q$，代表參賽者數量與有幾次決鬥。
接下來 $n$ 行，第 $i$ 行的第一個正整數為 $m_i$，代表編號 $i$ 的參賽者養了幾隻中卷，同一行接著會有 $m_i$ 個正整數 $a_{i,1}\sim a_{i,m_i}$，代表每隻中卷的魔力值。
接下來 $q$ 行，每行有兩個正整數 $x,y$，代表此次決鬥的參賽者編號。
對於所有測試資料：
- $2\leq n\leq 10^ 5$
- $1\leq q\leq 10^ 5$
- $1\leq m_i\leq 10^ 5$
- $\sum\limits_{i=1}^ n m_i\leq 2\times 10^ 5$
- $1\leq a_{i,j}< 998244353$
- $1\leq x,y\leq n,x\neq y$
Output Format
每次決鬥，輸出參賽者 $x$ 能拿到獎金的期望值 $E\text{ mod }998244353$。
Sample Input 1
2 3 1
3 2 2 1
1 2
2 1
Sample Output 1
166374059
Sample Input 2
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
677881860
641371997
736862175
89482937
679206098
201431450
979230175
731996343
845070522
174820742
2513894
Hints
在範例測資一中，第一次決鬥 $x=1,y=2$，參賽者 $1$ 可以拿到獎金的期望值 $E$ 為 $\frac{5}{18}$，$5\times 18^ {-1}\equiv 5\times 720954255\equiv 610038216\ (\text{mod }998244353)$，故輸出 $610038216$。
第二次決鬥 $x=2,y=1$，參賽者 $2$ 可以拿到獎金的期望值 $E$ 為 $\frac{1}{6}$，
$6^ {-1}\equiv 166374059\ (\text{mod }998244353)$，故輸出 $166374059$。
Problem Source
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~6 | $m_i\leq 10$ | 21 |
| 3 | 0, 2, 7~9 | $q\leq 10$ | 28 |
| 4 | 0~50 | 無其他限制 | 51 |