AT_abc257_h [ABC257Ex] Dice Sum 2

题目描述

在六面骰子专卖店“さいころや”中，有 $N$ 个骰子在售。第 $i$ 个骰子上的点数分别为 $A_{i,1},A_{i,2},\ldots,A_{i,6}$，其价格为 $C_i$。

高桥君将从中恰好选出 $K$ 个骰子购买。

目前“さいころや”正在举办一项活动，购买的 $K$ 个骰子各掷一次，掷出的点数之和的平方即为你获得的奖金。每个骰子的掷出结果是独立且等概率的。

请通过合理选择要购买的 $K$ 个骰子，使得“（活动获得的奖金）减去（所购 $K$ 个骰子的总价格）”的期望值最大，并求出最大化时的期望值对 $998244353$ 取模的结果。

期望值 $\bmod\ 998244353$ 的定义：本题中要求的期望值一定是有理数，并且在本题的约束下，若将期望值表示为最简分数 $\frac{y}{x}$，则 $x$ 不会被 $998244353$ 整除。

此时，满足 $xz \equiv y \pmod{998244353}$ 的 $0$ 到 $998244352$ 之间的整数 $z$ 唯一确定。请输出这个 $z$。

输入格式

输入按以下格式从标准输入给出。

$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

输入 #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

输入 #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

说明/提示

约束

• $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$
• 所有输入均为整数

样例解释 1

如果选择购买第 $2$ 个和第 $3$ 个骰子，则“（活动获得的奖金）减去（所购 $K$ 个骰子的总价格）”的期望值为 $(2+3)^2-(2+3)=20$，这是期望值的最大值。

由 ChatGPT 4.1 翻译