分数: 450 点
问题陈述
有 N 六面骰子。 骰子的编号是从 1 to N,以及骰子表面上写的数字 i 是 A_{i,1},A_{i,2},\dots,A_{i,6}.
现在,所有 N 骰子将同时掷出。 求期望值,取模 998244353,每个骰子上出现的面上所写数字的最大值。
对于任何骰子,滚动骰子时出现的面是独立且均匀随机选择的。
求期望值模 998244353
可以证明,要找到的期望值总是有理数。 并且,在该问题的约束下,可以证明当该值表示为不可约分数时 \frac{P}{Q},我们有 Q \not\equiv 0 \pmod{998244353}。 因此,存在唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353。 找到这个 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
让 x_i 是骰子表面上写的数字 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