← 返回题目列表

AtCoder · abc411_e

H. E [最大]

中文机器翻译题面 查看原题

分数: 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