1000ms

Difficulty: 4

所属公司 : 极兔速递

时间 :2025年9月26日

算法与标签>思维

会员或题库专享

请先，开通会员或购买题库极兔速递编程题库，可解锁完整内容。

购买极兔速递编程题库开通会员

会员专享

请先登录，登录后可使用今日免费解锁；开通会员，或购买该题目所属题库（极兔速递编程题库），可解锁完整内容。

购买题库开通会员

解题思路

设数组重排为 $a'$ ，定义 $b_i=\mathrm{MEX}(a'_1,\dots,a'_i)$ 。记多重集合的全局 $\mathrm{mex}$ 为

R=\min\{x\ge 0\mid \text{数组中 }x\text{ 的出现次数 }=0\}.

显然，任何前缀的 $\mathrm{MEX}\le R$ ，且当已在前缀中出现了 $0,1,\dots,R-1$ 时， $\mathrm{MEX}=R$ 并将一直保持（因为整个数组中没有 $R$ ）。

题目内容

包含有一个长度为 $n$ 的数组 $a$ 。你可以将 $a$ 任意重排，得到一个新的数组，我们称之为 $a'$ 。定义一个长度为 $n$ 的数组 $b$ ，其中 $b_i = MEX(a'_1, a'_2, …, a'_i)$ 。你需要最大化数组 $b$ 中的元素之和。

你需要输出最大的元素和，以及有多少种可能的重排 $a$ ，使得 $b$ 中的元素和最大化。由于重排方案数可能很大，你只需要输出其对 $998244353$ 取模后的结果。