配点 : 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