/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
6 面サイコロ専門店「さいころや」には、N 個のサイコロが売られています。 i 番目のサイコロに書かれている目は A_{i,1},A_{i,2},\ldots,A_{i,6} であり、価格は C_i です。
高橋君はこの中からちょうど K 個のサイコロを選んで購入します。
現在「さいころや」ではキャンペーンが行われており、購入した K 個のサイコロをそれぞれ一度ずつ振り、出た目の総和の二乗のお金を貰えます。なお、どの目が出るかは一様ランダムであり、各サイコロについて独立です。
買う K 個のサイコロを適切に決めることで、(キャンペーンで貰えるお金 )-( 購入した K 個のサイコロの価格の合計) の期待値を最大化し、最大化した際の期待値を \bmod 998244353 で求めてください。
期待値 \bmod 998244353 の定義
この問題で求める期待値は必ず有理数になることが証明できます。 また、この問題の制約下では、求める期待値を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この 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
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