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