102577: [AtCoder]ABC257 Ex - Dice Sum 2
Description
Score : $600$ points
Problem Statement
The six-sided dice speciality shop "Saikoroya" sells $N$ dice. The $i$-th die (singular of dice) has $A_{i,1},A_{i,2},\ldots,A_{i,6}$ written on its each side, and has a price of $C_i$.
Takahashi is going to choose exactly $K$ of them and buy them.
Currently, "Saikoroya" is conducting a promotion: Takahashi may roll each of the purchased dice once and claim money whose amount is equal to the square of the sum of the numbers shown by the dice. Here, each die shows one of the six numbers uniformly at random and independently.
Maximize the expected value of (the amount of money he claims) - (the sum of money he pays for the purchased $K$ dice) by properly choosing $K$ dice to buy. Print the maximized expected value modulo $998244353$.
Definition of the expected value modulo $998244353$
We can prove that the sought expected value is always a rational number. Moreover, under the Constraints of this problem, the sought expected value can be expressed by an irreducible fraction $\frac{y}{x}$ where $x$ is indivisible by $998244353$.
In this case, we can uniquely determine the integer $z$ between $0$ and $998244352$ (inclusive) such that $xz \equiv y \pmod{998244353}$. Print such $z$.
Constraints
- $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$
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
$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}$
Output
Print the answer.
Sample Input 1
3 2 1 2 3 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3
Sample Output 1
20
If he buys the $2$-nd and $3$-rd dice, the expected value of (the amount of money he claims) - (the sum of money he pays for the purchased $K$ dice) equals $(2 + 3)^2 - (2 + 3) = 20$, which is the maximum expected value.
Sample Input 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
Sample Output 2
1014
Input
题意翻译
存在 $ n $ 个正六面体骰子，第 $ i $ 个骰子六个面的数值分别为 $ A_{i, 1}, A_{i, 2}, \cdots, A_{i, 6} $，购买第 $ i $ 个骰子的花费为 $ C_i $。你要在其中购买 $ k $ 个骰子，以最大化收益的期望。定义收益为将购买的 $ k $ 个骰子各扔一遍，其朝上的数的和的平方减去买 $ k $ 个骰子花费的总费用。输出模 $ 998244353 $ 意义下的收益期望最大值。Output
分数：$600$分
问题描述
六面骰子专卖店"Saikoroya"出售$N$个骰子。第$i$个骰子（骰子的单数形式）的每一面分别标有$A_{i,1},A_{i,2},\ldots,A_{i,6}$，价格为$C_i$。
高桥打算从中选择正好$K$个并购买。
目前，"Saikoroya"正在进行促销：高桥可以对每个购买的骰子掷一次，并获得金额等于骰子所示数字之和的平方的奖金。在这里，每个骰子会随机、独立地显示六个数字中的一个。
通过适当地选择购买的$K$个骰子，使（他获得的奖金金额）-（他为购买的$K$个骰子支付的总金额）的期望值最大。将最大化的期望值对$998244353$取模后输出。
对$998244353$取模的期望值的定义
我们可以证明所求期望值总是一个有理数。 此外，在本问题的约束下，所求期望值可以用一个不可约分数$\frac{y}{x}$表示，其中$x$被$998244353$整除。
在这种情况下，我们可以唯一确定$0$到$998244352$（含）之间的整数$z$，使得$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$个和第$3$个骰子，（他获得的奖金金额）-（他为购买的$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