/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
N 個の六面サイコロがあります。 サイコロには 1 から N までの番号が付けられており、サイコロ i の各面に書かれた数はそれぞれ A_{i,1},A_{i,2},\dots,A_{i,6} です。
今からこれら N 個のサイコロを全て同時に振ります。 各サイコロの上を向いた面に書かれた数の最大値の期待値を \bmod\ 998244353 で求めてください。
なお、いずれのサイコロについても、そのサイコロを振った際に上を向く面は独立かつ一様ランダムに選ばれるものとします。
期待値を \bmod\ 998244353 で求めるとは
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not\equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この R を求めてください。
制約
- 1\leq N \leq 10^5
- 1\leq A_{i,j} \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \dots A_{1,6}
A_{2,1} A_{2,2} \dots A_{2,6}
\vdots
A_{N,1} A_{N,2} \dots A_{N,6}
出力
答えを出力せよ。
入力例 1
2 1 1 4 4 4 4 1 1 1 3 3 3
出力例 1
332748121
サイコロ i の上を向いた面に書かれた数を x_i とします。
- x_1=1,x_2=1 のケース：\frac{2}{6}\times\frac{3}{6}=\frac{1}{6} の確率で発生し、上を向いた面に書かれた数の最大値は 1 です。
- x_1=1,x_2=3 のケース：\frac{2}{6}\times\frac{3}{6}=\frac{1}{6} の確率で発生し、上を向いた面に書かれた数の最大値は 3 です。
- x_1=4,x_2=1 のケース：\frac{4}{6}\times\frac{3}{6}=\frac{1}{3} の確率で発生し、上を向いた面に書かれた数の最大値は 4 です。
- x_1=4,x_2=3 のケース：\frac{4}{6}\times\frac{3}{6}=\frac{1}{3} の確率で発生し、上を向いた面に書かれた数の最大値は 4 です。
よって、求める期待値は \frac{1}{6}\times 1 + \frac{1}{6}\times 3 + \frac{1}{3}\times 4 + \frac{1}{3}\times 4 = \frac{10}{3} \equiv 332748121 \pmod{998244353} です。
入力例 2
2 1 1 1 1 1 1 2 2 2 2 2 2
出力例 2
2
サイコロ 1,2 の上を向いた面に書かれた数はそれぞれ常に 1,2 であり、その最大値は常に 2 です。
入力例 3
8 55 76 80 21 34 28 82 84 2 32 56 17 11 57 37 28 39 18 47 2 97 25 75 29 72 45 22 75 26 81 6 79 16 68 68 40 31 80 68 57 18 55 49 10 63 91 93 40
出力例 3
213725517
Score : 450 points
Problem Statement
There are N six-sided dice. The dice are numbered from 1 to N, and the numbers written on the faces of die i are A_{i,1},A_{i,2},\dots,A_{i,6}.
Now, all N dice will be rolled simultaneously. Find the expected value, modulo 998244353, of the maximum value among the numbers written on the face that comes up on each die.
For any die, the face that comes up when the die is rolled is chosen independently and uniformly at random.
Finding the expected value modulo 998244353
It can be proved that the expected value to be found is always a rational number. Also, under the constraints of this problem, it can be proved that when the value is expressed as an irreducible fraction \frac{P}{Q}, we have Q \not\equiv 0 \pmod{998244353}. Therefore, there exists a unique integer R such that R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353. Find this R.
Constraints
- 1\leq N \leq 10^5
- 1\leq A_{i,j} \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \dots A_{1,6}
A_{2,1} A_{2,2} \dots A_{2,6}
\vdots
A_{N,1} A_{N,2} \dots A_{N,6}
Output
Output the answer.
Sample Input 1
2 1 1 4 4 4 4 1 1 1 3 3 3
Sample Output 1
332748121
Let x_i be the number written on the face that comes up on die i.
- Case x_1=1,x_2=1: Occurs with probability \frac{2}{6}\times\frac{3}{6}=\frac{1}{6}, and the maximum value among the numbers written on the faces that come up is 1.
- Case x_1=1,x_2=3: Occurs with probability \frac{2}{6}\times\frac{3}{6}=\frac{1}{6}, and the maximum value among the numbers written on the faces that come up is 3.
- Case x_1=4,x_2=1: Occurs with probability \frac{4}{6}\times\frac{3}{6}=\frac{1}{3}, and the maximum value among the numbers written on the faces that come up is 4.
- Case x_1=4,x_2=3: Occurs with probability \frac{4}{6}\times\frac{3}{6}=\frac{1}{3}, and the maximum value among the numbers written on the faces that come up is 4.
Thus, the expected value to be found is \frac{1}{6}\times 1 + \frac{1}{6}\times 3 + \frac{1}{3}\times 4 + \frac{1}{3}\times 4 = \frac{10}{3} \equiv 332748121 \pmod{998244353}.
Sample Input 2
2 1 1 1 1 1 1 2 2 2 2 2 2
Sample Output 2
2
The numbers written on the faces that come up on dice 1,2 are always 1,2, respectively, and their maximum value is always 2.
Sample Input 3
8 55 76 80 21 34 28 82 84 2 32 56 17 11 57 37 28 39 18 47 2 97 25 75 29 72 45 22 75 26 81 6 79 16 68 68 40 31 80 68 57 18 55 49 10 63 91 93 40
Sample Output 3
213725517