← 返回题目列表

AtCoder · abc257_h

Ex. 骰子总和 2

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

分数: 600 点

问题陈述

六面骰子专卖店“Saikoroya”出售 N 骰子。 的 i-th die(骰子的单数)有 其每一面均写有 A_{i,1},A_{i,2},\ldots,A_{i,6} ,价格为 C_i.

高桥将准确选择 K 其中并购买它们。

目前,“Saikoroya”正在进行促销:高桥可以将购买的每个骰子掷一次,并领取骰子所显示数字之和的平方的金钱。 在这里,每个骰子均匀、随机、独立地显示六个数字之一。

最大化(他要求的金额)-(他为购买的商品支付的金额)的期望值 K 骰子)通过正确选择 K 骰子购买。 打印最大期望值模 998244353.

期望值模的定义 998244353

我们可以证明所求的期望值始终是有理数。 此外,在该问题的约束下,所寻求的期望值可以用不可约分数来表示 \frac{y}{x} 其中 x 不可整除 998244353.

在这种情况下,我们可以唯一确定整数 z 之间 0 和 998244352 (含)使得 xz \equiv y \pmod{998244353}。 打印这样的 z.

约束

  • 1 \leq N \leq 1000
  • 1 \leq K \leq N
  • 1 \leq C_i \leq 10^5
  • 1 \leq A_{i,j} \leq 10^5
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
C_1 C_2 \ldots C_N
A_{1,1} A_{1,2} \ldots A_{1,6}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,6}

输出

打印答案。


示例输入 1

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

示例输出 1

20

如果他购买 2-nd 和 3-rd 骰子,(他声称的金额)的期望值 - (他为购买的物品支付的金额) K 骰子) 等于 (2 + 3)^2 - (2 + 3) = 20,这是最大期望值。


示例输入 2

10 5
2 5 6 5 2 1 7 9 7 2
5 5 2 4 7 6
2 2 8 7 7 9
8 1 9 6 10 8
8 6 10 3 3 9
1 10 5 8 1 10
7 8 4 8 6 5
1 10 2 5 1 7
7 4 1 4 5 4
5 10 1 5 1 2
5 1 2 3 6 2

示例输出 2

1014