← 返回题目列表

AtCoder · arc134_c

C. 大多数

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

分数: 500 点

问题陈述

有 K 盒子编号 1 to K。最初,所有盒子都是空的。

Snuke 有一些带有整数的球 上面写着 1 to N 。 其中, a_i 球有编号 i。 无法区分写有相同整数的球。

Snuke 决定把他所有的球都放进盒子里。 他想要有号码的球 1 在每个盒子中都拥有多数。 换句话说,每个盒子里的球数 1 应大于其他球的值。

找出将球放入盒子中的这种方法的数量,取模 998244353.

存在一对整数时区分两种方式 (i,j) 满意 1 \leq i \leq K, 1 \leq j \leq N 这样球的数量 盒子里的 j 盒装 i 不同。

约束

  • 输入中的所有值都是整数。
  • 1 \leq N \leq 10^5
  • 1 \leq K \leq 200
  • 1 \leq a_i < 998244353

输入

输入由标准输入按以下格式给出:

N K 
a_1 \cdots a_N

输出

打印路数,模数 998244353,将球放入盒子中,以便具有编号的球 1 在每个方框中都占多数。


示例输入 1

2 2
3 1

示例输出 1

2
  • 有两种方法来放置球,以便使带有数字的球 1 将占大多数。
  • 一种方法是将其中两个球与 1 盒装 1 和盒子里的另一个 2,然后将一个球放入 2 盒装 1.

示例输入 2

2 1
1 100

示例输出 2

0
  • 可能无法将球放入盒子中以满足要求。

示例输入 3

20 100
1073813 90585 41323 52293 62633 28788 1925 56222 54989 2772 36456 64841 26551 92115 63191 3603 82120 94450 71667 9325

示例输出 3

313918676
  • 一定要找到计数模数 998244353.