← 返回题目列表

AtCoder · pakencamp_2023_day2_g

G. 减少 x K

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

配点 : 800 点

問題文

正整数 N 和长度 给出了 N 的非负整数序列 A 。只需进行以下操作即可 考虑重复 K 次。 从

  • A 中选择一个正元素。所选元素 x 并将其转换为 满足 0 \leq y < x 的整数 选择 y 置换为。

K 操作后 可能的事物数量为 A 除以 998244353 求余数。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 10^5
  • 0 \leq A_i \leq 10^9
  • 所有输入均为整数

配点

分数由以下子作业确定。

  1. (200 点) N, K \leq 100
  2. (400 点) N, K \leq 1000
  3. (200 点)没有额外的限制。

入力

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

N K
A_1 A_2 \cdots A_N

出力

答案请在一行中输出。


入力例 1

3 2
1 2 3

出力例 1

14

K 操作后 下面列出了可能的 A : (1, 2, 1), (1, 2, 0), (1, 1, 2), (1, 1, 1), (1, 1, 0), (1, 0, 3), (1, 0, 2), (1, 0, 1), (1, 0, 0), (0, 2, 2), (0, 2, 1), (0, 2, 0), (0, 1, 3), (0, 0, 3) 可以得到第 14 街道。


入力例 2

5 3
1 2 3 4 5

出力例 2

306