← 返回题目列表

AtCoder · xmascon20_f

F. 在俄罗斯著名

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

配点 : 100 点

动物们今年也在为圣诞比赛进行编程练习会。

問題文

金丝雀出了如下的问题。


优化大师厨师狐狸

长度 小于或等于 N 整数序列 给出 A = (A_1, \ldots, A_N) 和 按字典顺序比较 B = (B_1, \ldots, B_N) 。

狐狸经营着一家餐厅。现在这家餐厅有,1 减去 N 编号最多为 N 位客人。客人 i 点的菜需要 A_i 单位时间来烹饪,吃菜需 B_i 单位时间。

各整数 k (1 \le k \le N)请解决关于此的问题。

狐狸选择 k 位客人,被未选择的 N - k 位送回家。然后,k 位客人的菜按照自己喜欢的顺序依次制作。2 以上的料理不能同时制作。客人会在自己的料理完成的瞬间开始用餐。狐狸的労働時間是“从开始制作第一道料理,到所有k 位客人用餐结束的时间”。请找出狐狸劳动时间的最小值。


然而,这个问题被发现几乎已经在俄罗斯国内竞赛中出现过。因此,加那利修改了问题如下。


Counting Chef 狐狸

整数 V 和长度 给出了 N 整数序列 给出 B = (B_1, \ldots, B_N) 。

长度是 N 每个元素都有 1 以上 V 以下的整数序列 A = (A_1, \ldots, A_N) 是 您也可以写 V^N 种存在,但对每个 A ,(与给定的 B 一起)解决问题“Optimizing Chef 狐狸”,并对每个整数 k (1 \le k \le N)求出答案的总和。 998244353 求余数。


解决“计数厨师狐狸”问题。

制約

  • 1 \le N \le 30.
  • 1 \le V \le 20.
  • 1 \le B_i \le 600 (1 \le i \le N).

入力

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

N V
B_1 B_2 \cdots B_N

出力

各 k = 1, \ldots, N 的答案,请按照这个顺序用空格分隔输出。考虑


入力例 1

2 2
1 2

出力例 1

10 16

k = 2 的情况。每个 A 对应的原问题的答案如下:

  • A = (1, 1):劳动时间的最小值是 3.
  • A = (1, 2):劳动时间的最小值是 4.
  • A = (2, 1):劳动时间的最小值是 4.
  • A = (2, 2):劳动时间的最小值是 5.

因此, 正确答案是输出3 + 4 + 4 + 5 = 16 。 你只需要砍掉


入力例 2

3 5
1 2 4

出力例 2

448 787 1255

入力例 3

10 10
14 38 45 9 19 18 7 18 33 21

出力例 3

663655052 615617049 323725023 554911324 803518888 499232802 916051842 54293837 639852351 260050903