← 返回题目列表

AtCoder · 1202Contest_f

F. K 中位数聚类

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

分数: 100 点

问题陈述

给你正整数 N, M, K,以及一系列 K 正整数 c=(c_1, c_2, \dots, c_K).

A 多套 S 组成 N 小于或等于的正整数 M 被称为 好,如果存在至少一个序列 K 多套 (S_1, S_2, \dots, S_K) 满足以下条件。

  • 没有一个 S_1, S_2, \dots, S_K 为空。
  • 的中位数 S_i 等于 c_i,对于所有 i=1, 2, \dots, K.
  • S_1, S_2, \dots, S_K 正好有 总共 N 个元素。由这些组成的多重集 N 元素符合 S.

请注意,我们定义了多重集的中位数 T 与 n\ (\geq 1) 元素作为 \lceil n / 2 \rceil第一个元素 T 按升序排列。例如,中位数为 T=\lbrace 1, 2, 3, 4 \rbrace is 2,以及 T=\lbrace 1, 3, 5, 7, 7 \rbrace is 5.

求模的良好多重集的数量 998244353.

约束

  • 1 \leq N, M \leq 10^7
  • 1 \leq K \leq \min(2 \times 10^5, N)
  • 1 \leq c_i \leq M
  • 所有输入值均为整数。

输入

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

N \ M \ K
c_1 \ c_2 \ \dots \ c_K

输出

打印良好的多重集模数 998244353.


示例输入 1

8 5 3
4 1 5

示例输出 1

105

例如, S=\lbrace 1,1,1,2,3,4,5,5 \rbrace 是一个很好的多重集,因为存在 (S_1, S_2, S_3) 满足如下条件。

  • S_1 = \lbrace 1, \mathbf{4}, 5 \rbrace
  • S_2 = \lbrace 1, \mathbf{1}, 2, 3 \rbrace
  • S_3 = \lbrace \mathbf{5} \rbrace

示例输入 2

10000000 2 2
1 2

示例输出 2

9999999

示例输入 3

30 10 5
3 1 4 1 5

示例输出 3

38446044